Jim challenges Bob and Sally to a game Bob and Sally both kn

Jim challenges Bob and Sally to a game. Bob and Sally both know the game and are allowed to discuss a strategy ahead of time. When the game starts, Bob and Sally are placed in separate rooms. Bob will then be given a 2n by 2n grid of coins. Jim will then flip the coins as he desires into an arbitrary configuration of heads and tails. After he finishes flipping the coins, Jim will then select a single square on the grid and declare it “Jim’s square”. At this time Bob is allowed to ask Jim to flip a single coin on the grid, which Jim will then proceed to do. Afterwards Bob is taken out of the room and Sally is brought in. No communication between them is allowed during this time. By only examining the grid of coins, Sally must identify which square is “Jim’s square”. If Sally can successfully determine which square Jim selected, Bob and Sally win. Otherwise Jim wins.

Prove that Bob and Sally can always win for any n > 0.

Solution

think in binary terms

so using head or tail we want Sally to know which coin Bob is referring.

Consider head as 0

tail as 1

given a binary number of length 4n (Jim is making arbitrary configuration )

in the same sequence, we want to point to some number x , 0<=x<4n by only changing one digit

So the one digit of this binary can change from 0 to 1 or 1 to 0 .

Now the strategy is to change the number in such a way

so that the resulting binary number mod (4n) becomes equal to x

and we can tell sally about x .

This is perfectly possible

Since we have 4n possible digits to change we can create 4n different remainders when the resultant number is divided by 4n.

And the claim which can easily be proved

numbers generated by changing diferent digits are different modulo 4n

So there is a unique way to get x mod 4n