11

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?

Improve this question
8
  • 2
    Might want to ask this on the Cryptography SE. Commented Jul 17, 2015 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). Commented Jul 17, 2015 at 15:14
  • No way, zero chance Commented Jul 17, 2015 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. Commented Jul 17, 2015 at 16:10
  • 3
    That questionnaire is pretty cool, and chance there is an answer sheet somewhere? Commented Jul 17, 2015 at 17:58

5 Answers 5

Reset to default
67

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*
Improve this answer
11
  • 8
    And this is 100% the right answer :) Commented Jul 17, 2015 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. Commented Jul 17, 2015 at 17:51
  • 1
    @Mindwin OP was rather quick with selecting the accepted answer and had done so before I posted mine. Commented Jul 17, 2015 at 17:58
  • 2
    Never has an answer felt so wrong, but been so right. Commented Jul 17, 2015 at 20:14
  • 2
    @Dancrumb: See Lynxy's answer. This will fail if A receives 1 and B receives 0. Commented Jul 17, 2015 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).

Improve this answer
2
  • 1
    "at some point, the operator who runs the experiment loses patience" +1 for using the operator :) Commented Jul 17, 2015 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. Commented Jul 17, 2015 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.

Improve this answer
1
  • 5
    Can you explain how you got to 75%? Commented Jul 17, 2015 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.

Improve this answer
2
  • 5
    This is the first time I've ever seen an answer with negative score marked as the correct answer. Commented Jul 17, 2015 at 20:36
  • @Derek朕會功夫, maybe the OP doesn't realize you can change which answer is accepted. Commented Jul 17, 2015 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.

Improve this answer
2
  • 2
    The correct answer has already been given, and explained how to be right 100% of the time. Commented Jul 17, 2015 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. Commented Jul 17, 2015 at 22:57

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.