Log In

Guess a coin for freedom

Posted on: March 7th, 2014 by
5

A and B are prisoners. The jailer have them play a game. He places one coin on each cell of an 8x8 chessboard. Some are tails up and others are heads up. B cannot yet see the board. The jailer shows the board to A and selects a cell. He will allow A to flip exactly one coin on the board. Then B arrives. He is asked to inspect the board and then guess the cell selected by the jailer. If B guesses the correct cell among 64 options, A and B are set free. Otherwise, they are both executed. Is there a winning strategy for A and B? (They can co-operate and discuss a strategy before the game starts).

- via Algorithmic puzzles


5 Responses to Guess a coin for freedom

  1. Lizard had this to say about that:

    Since 64=2^6, each cell is identified by a 6-bit label. For a given configuration of coins on the board, let P be the 6-bit integer whose bit in position i is the parity of the number of heads among all cells whose labels have a 1 in position i.

    Prisoner A computes the initial value of P and the label X of the jailor's selected cell, and flips over the coin whose label is P XOR X. The effect of this is to flip a bit in P exactly when it differs from the corresponding bit of X, so that the new value of P is equal to X; prisoner B can simply read this off.

    • Sid Hollander had this to say about that:

      Would you please give an example for

      a) a 2 by 2 grid?
      b) Does solution hold if jailer rotates board?

      • Lizard had this to say about that:

        a) The cells are labeled 00,01,10,11. Suppose cells 01 and 11 have heads-up coins, so P = xor(01, 11) = 10. The jailor selects cell 00, so prisoner A flips coin 10, which changes P to xor(01, 10, 11) = 00.

        b) No, but that's an interesting modification. Hmm

    • Lizard had this to say about that:

      My friend noticed that P is simply the bitwise-XOR of the labels of the cells with heads-up coins. This makes the solution easier to understand: prisoner A computes the initial value of P, compares it to the desired message (i.e. the label of the jailor's cell) to determine which bits of P he needs to change, and flips the coin whose label has a 1 in exactly those bits.

  2. Lizard had this to say about that:

    We also proved that there's no winning strategy if the number of cells is not a power of two:

    With N cells, there are 2^N possible coin configurations. Each configuration is adjacent to (i.e. one coin flip away from) exactly N other configurations.

    Suppose K_1 configurations denote "choose cell 1" to prisoner B. There are at most K_1*N adjacent configurations from which prisoner A could send this message; in a winning strategy, this must include all 2^N possible initial configurations, so K_1*N >= 2^N, i.e. K_1 >= 2^N/N. This applies to every possible message, so we have (K_1 + ... + K_N) >= N*2^N/N, i.e. 2^N >= 2^N. The strict inequality case is a contradiction, so we must have K_1=2^N/N, so N evenly divides a power of 2.


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}