Skip to main content
added 351 characters in body
Source Link
Tom Leek
  • 174.7k
  • 29
  • 353
  • 485

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).

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.

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).

Source Link
Tom Leek
  • 174.7k
  • 29
  • 353
  • 485

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.