12

I am soon to start my compulsory military service. I applied to the Cyber Warfare Unit of Finnish army. There was a test for applicants. Since the test is done the questions have now been published here: http://erityistehtavat.puolustusvoimat.fi/cyberchallenge.html

Here is question 4:

Two completely isolated programs get one random bit each from different hardware random number generators. After getting the bit each program guesses what the other program's random bit was. Programs can be different and use different strategies for guessing. After running them once, if at least one program guessed correctly, the author of the programs receives a prize.

Is it possible to devise a strategy that provides a 100% chance of winning the prize? If yes, explain the strategy.

I answered no because I couldn't figure out winning strategy. Was that the right answer or did I miss something?

closed as off-topic by Eric G, Xander, Iszi, Gilles 'SO- stop being evil', D.W. Jul 17 '15 at 21:44

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about Information security within the scope defined in the help center." – Xander, Iszi, Gilles 'SO- stop being evil', D.W.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    Might want to ask this on the Cryptography SE. – ztk Jul 17 '15 at 15:07
  • 1
    Probability of success is 75% is both programs answer randomly (since the prize is obtained when either or both guesses correctly). – Tom Leek Jul 17 '15 at 15:14
  • No way, zero chance – user45139 Jul 17 '15 at 15:18
  • 2
    Considering the answer I gave, the puzzle can been reformulated to be completely unrelated to computer science. For this reason I think that puzzling.stackexchange.com probably would have been the fastest SE site to give the correct answer. – helm Jul 17 '15 at 16:10
  • 3
    That questionnaire is pretty cool, and chance there is an answer sheet somewhere? – Reinstate Monica Jul 17 '15 at 17:58
68

There is actually a solution that will always succeed: Program A will guess the opposite of the value it receives, program B will guess the same value as the one it receives.

You can also think of that as such: A guesses that they will receive different numbers; B guesses they receive the same. One of them is bound to be correct. If you look at the following table (r for receive, g for guess), you will see that either A or B is always right (* denotes correct response):

rA | rB | gA | gB
0     0    1    0*
0     1    1*   1
1     0    0*   0
1     1    0    1*
  • 8
    And this is 100% the right answer :) – stanko Jul 17 '15 at 15:45
  • 10
    @pineappleman and this Q&A is a textbook example why the green checkbox of accepted answers mean less and less in SE sites. – Mindwin Jul 17 '15 at 17:51
  • 1
    @Mindwin OP was rather quick with selecting the accepted answer and had done so before I posted mine. – helm Jul 17 '15 at 17:58
  • 2
    Never has an answer felt so wrong, but been so right. – Jeff Meden Jul 17 '15 at 20:14
  • 2
    @Dancrumb: See Lynxy's answer. This will fail if A receives 1 and B receives 0. – helm Jul 17 '15 at 21:54
5

Since this looks like a trick question, here is a trick answer (i.e. it is "cheating").

Let program A do the following:

  • If it receives a 0, then output "1" and exit.
  • Otherwise, loop forever, until a "Ctrl-C" signal is received, in which case the program outputs "0" and exits.

Let program B do the following:

  • If it receives a 0, then output "0" and exit.
  • Otherwise, loop forever, until a "Ctrl-C" signal is received, in which case the program outputs "1" and exits.

Analysis:

  • If both programs get a 0, program B outputs "0", which is correct -> win.
  • If program A gets a 0 and program B gets a 1, then program A outputs "1", which is correct -> win.
  • If program A gets a 1 and program B gets a 0, then program A loops forever while program B outputs "0" (which is wrong); at some point, the operator who runs the experiment loses patience, types Ctrl-C in the terminal running program A, and sees "0" which is a correct answer -> win.
  • If both programs get a 1, then both programs loop forever. The operator tries to kill both with Ctrl-C, at which point program A outputs 0 and program B outputs 1; the latter is correct -> win.

And voilà! a 100% winning strategy.

Edit: and if you forget the whole "wait until Ctrl-C" thing, then you get essentially @Helm's answer, which is correct and a lot less tricky. The only point of that waiting process is to get a side-channel by which a program may not only guess the value, but also "know" that it guessed the value (which is not part of the challenge anyway).

  • 1
    "at some point, the operator who runs the experiment loses patience" +1 for using the operator :) – mikeazo Jul 17 '15 at 18:03
  • 3
    Yeah, I was so pleased with myself for thinking about this (I mean, even more pleased that I usually am) that I failed to notice that without this side-channel I actually had the correct answer. – Tom Leek Jul 17 '15 at 18:12
-3

You are correct. The closest you could get would be a 75% chance of at least one of them being correct, with both computers always guessing the negation of the other.

  • 5
    Can you explain how you got to 75%? – schroeder Jul 17 '15 at 15:08
-3

Since this is information warfare, I wonder if scenarios with "cheating" are allowed. There may be a system level artifact which the programs can check after the random number is generated or one of the programs could hook into that process, monitor it.

The requirements say the programs are isolated from each other, but are not necessarily on separate systems. You may be able to detect or influence the seed value used by the other application as well if these are both on the same system. If you are writing both applications, you could have each application even print out the value and let the other system read that value in. Even if these are on separate boxes, you could theoretically propose a solution that used some type of heat or acoustic monitoring.

I think the word "guessing" is a throw off, you cannot have any certainty if you are just guessing. This question sounds more like a way of thinking about different ways of breaking of influencing the system and also about understanding how to influence or predict random values.

  • 5
    This is the first time I've ever seen an answer with negative score marked as the correct answer. – Derek 朕會功夫 Jul 17 '15 at 20:36
  • @Derek朕會功夫, maybe the OP doesn't realize you can change which answer is accepted. – cjm Jul 17 '15 at 21:47
-3

NO it is not possible to guess a randomly generated bit, with 100% accuracy, you will be right on average half of the time.

Edit: I agree I'm wrong, I read the question as only owning one of the programs. If you own both, each will be correct half of the time, thus on average always.

  • 2
    The correct answer has already been given, and explained how to be right 100% of the time. – Xander Jul 17 '15 at 21:56
  • If you still want to assert your 50% even after a clear answer has been demonstrated, then you need to explain how you arrived at your conclusion. – schroeder Jul 17 '15 at 22:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.