Using your Head is Permitted

May 2014 riddle

UPDATE (1 June): No correct solutions have been submitted so far to this riddle. The riddle will therefore run one extra month. However, this time credit will be given both to solvers of all three questions (as was the original problem definition) and to solvers of only the first two questions. This riddle will continue to run in parallel with a new June riddle.

Two players play the following game:

Player One chooses an n-bit string and shows it to Player Two.

Player Two then chooses a different n-bit string.

Now, a random bit generator generates bits, one after the other, independently, with equal probability for "0"s and for "1"s.

The game stops when the last n bits generated are (in correct order) exactly those that Player One chose or exactly those that Player Two chose.

The winner is the player whose bits showed up.

This month's questions: given that both players play optimally,

  1. for which values of n does Player One win with greater than 50% probability?
  2. for which values of n does Player Two win with greater than 50% probability?
  3. for an asymptotically large n, what are the winning probabilities for each player?
As usual, you are required to prove all answers for credit.

List of solvers:

Questions 1+2:

Radu-Alexandru Todor (11 June 03:41)
Dorian Nogneng (12 June 14:01)

Complete Answer:

Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!

To solution

Back to main page