There is a square table with a quarter on each corner. The table is behind a curtain and thus out of your view. Your goal is to get all of the quarters to be heads up — if at any time all of the quarters are heads up, you will immediately be told and win.
The only way you can affect the quarters is to tell the person behind the curtain to flip over as many quarters as you would like and in the corners you specify. (For example, “Flip over the top left quarter and bottom right quarter,” or, “Flip over all of the quarters.”) Flipping over a quarter will always change it from heads to tails or tails to heads. However, after each command, the table is spun randomly to a new orientation (that you don’t know), and you must give another instruction before it is spun again.
Can you find a series of steps that guarantees you will have all of the quarters heads up in a finite number of moves?
Solution
While there are sixteen possible arrangements of heads and tails on the four corners of the table, some can be obtained from others by rotation (spinning the table) or inversion (flipping all four coins). It’s not hard to see that all arrangements thus fall into four types, typified as follows:
\[A : \begin{vmatrix} H&T\\ T&T\\ \end{vmatrix} \; B : \begin{vmatrix} H&T\\ H&T\\ \end{vmatrix} \; C : \begin{vmatrix} H&T\\ T&H\\ \end{vmatrix} \; D : \begin{vmatrix} H&H\\ H&H\\ \end{vmatrix} \;\]Now we’ll define four moves:
- All: flip all four coins.
- Single: flip the lower-left coin.
- Side: flip the lower-left and lower-right coins.
- Diag: flip the lower-left and upper-right coins.
Here’s how these moves transition between the four state-types:
| Start: | All | Single | Side | Diag |
|---|---|---|---|---|
| A | A | B,C,D | A | A |
| B | B | A | C,D | B |
| C | C | A | B | D |
Now to specify the winning sequence of moves. Before and after every non-All move, we do All to test whether we are in the all-tails D-state (and win if we are). So we will specify only the non-All moves that will ensure that we land in a D state-type.
We start with Diag. If we were in C, then we enter D and win. If we don’t win, we know we remain in state-type A or B.
Now we do Side. If we were in A, we stay there. If B, we enter D (and win) or C. If we don’t win, we know we are in A or C.
We do Diag again. If we were in C, we enter D and win. If A, we remain in A. If we don’t win, we know we are in A.
Now we break out Single for its star turn. Since we were in A, we are now in one of: B, C, and D. If D, we are done. If we don’t win, we know we are in B or C.
Now the sequence Diag, Side, Diag will win for us whichever of state-types B and C we are in, just as it did at the start of the overall sequence.