2008
07.13

A coin problem – part I

[I might have posted this problem in the past. I am posting it for the second part, which I will post soon.]

A journalist, named Zoe, unfortunately (for her) interviews one of the presidential candidates. The candidate refuses to let Zoe to end the interview, and goes on and on about the candidate’s plans how to solve all the problems in the world. In the end, the candidate offers Zoe a game. If she wins the game she can leave.

The game board is made out of 2×2 coins:

At each round, Zoe can decide to flip one or two coins, by specifying which coins she is flipping (for example, flip the left bottom coin and the right top coin), next the candidate goes and rotates the board by either 90,180,270, or 0 degrees. (Of course, rotation by 0 degrees is just keeping the coins in their current configuration.)

The game is over when all the four coins are either all heads or all tails. To make things interesting, Zoe does not see the board, and does not know the starting configuration.

Describe an algorithm that Zoe can deploy, so that she always win. How many rounds are required by your algorithm?

1. Two clarifying questions:

1) Is the flipping random or deterministic (i.e., does flipping necessarily change a coin to the opposite state, or a randomly chosen state)?

2) Does the candidate get to choose a different rotation angle each time, or is it always the same?

2. I think
1. deterministic.
2. it is up to candidate.

3. [Sariel: I deleted the description of the (correct) solution – I don want to ruin it for other people.]
1) ????
2) ????
3) ????
So the answer is 7. Is that the best?

4. Does Zoe get to know by how much degrees has the candidate turned the square?

5. Zoe does not know the rotation angle…

6. And yes, 7 steps is the best solution possible.

7. […] you solved part I. But here is now part II (which is harder, BTW). Now, the board is made out of n coins places on […]

8. a clarification: So Zoe does NOT know by how much the board gets turned in each round ? I’m a little confused then. Fix Zoe’s winning strategy. Suppose the politician decides never to turn the board at all. Then her strategy corresponds to a fixed number of flips for each coin in the 2×2 grid, which we can reduce modulo 2 to a binary 2×2 matrix. Then we can find a starting configuration on which this binary 2×2 matrix will not yield the desired end configuration.

Maybe there’s a problem in my argument ?

9. Hi Suresh,

The important point is that the game stops as soon as the board is all heads or all tails. As such, there is no such thing is end configuration, since the game would end early… As such, the game might last 5 steps, or 3 steps, etc…

Makes snese?

10. ok I see. so it’s a ‘third party’ that informs the players when the game stops. that explains the process I think.

11. Well. The candidate does see the board. The journalist does not see it. We are assuming the candidate (or a third side) make sure that when the board is uniform the game stops.

12. […] via Sarielâ€™s blog […]

13. She wins by not playing the game. They are only candidates and by default have no real power to stop her from leaving.