This week’s Riddler Classic is a simple-sounding problem about statistics. But it’s not so simple! Here is a paraphrased version of the problem:
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?
Here is my solution:
Every time a move is made, the table spins around randomly. This sort of randomization actually simplifies the game considerably by reducing the number of distinct positions and moves possible:
- Although there are $2^4 = 16$ different ways to arrange quarters in combinations of Heads (H) and Tails (T) on the four corners of the table, if one position can be reached from another via rotation, then those two positions can be treated as one, since there is no way to distinguish them after the table spin. There are in fact only 6 distinct positions:
- all Heads: (H,H,H,H). This is the winning position
- all Tails: (T,T,T,T).
- opposite Heads: (H,T,H,T). There are 2 configurations for this position.
- one Head: (H,T,T,T). There are 4 configurations for this position.
- one Tail: (T,H,H,H). There are 4 configurations for this position.
- two at a time: (H,H,T,T). There are 4 configurations for this position.
- Although there are also $2^4-1=15$ different moves we can make (minus one because we exclude the move where you flip nothing), again the spinning makes several of these moves equivalent. There are really only five different possible moves:
- flip one quarter (ONE)
- flip two opposite quarters (OPP)
- flip two adjacent quarters (ADJ)
- flip three quarters (TRI)
- flip all the quarters (ALL)
Given this information, we can look at all the possible transitions between states that can occur if we make a certain move from any given position. Here is a diagram showing all possible transitions. I excluded the “flip three quarters” move because this move turns out not to be necessary.
For example, if we “flip two opposite quarters”, the (H,H,T,T) position always remains unchanged. Meanwhile, the (H,T,H,T) could lead us to the winning positions (H,H,H,H), or it could lead us to the (T,T,T,T) position.
A key observation: the “one-off” positions (H,T,T,T) and (T,H,H,H), which I colored in purple, will only ever transition between each other if we flip two quarters or all quarters. We can use this to our advantage: we will begin by only using these moves to try to win. If we cannot win, then we conclude that we must be in one of the “one-off” positions. Essentially, the strategy consists of making moves that successively test possible states. Every time we test a state, if we are correct we reach (H,H,H,H) and the game stops. Otherwise, the game continues and we can eliminate that state from the list of possible states. We continue in this fashion until there are no states left. Here are the logical steps:
- Are we in (T,T,T,T)? Try (ALL) to find out.
If the game continues, we must not be in (T,T,T,T).
- Are we in (H,T,H,T)? Do (OPP) to escape.
If the game continues, we moved to (T,T,T,T).
Repeat step 1 to test if this is true.
If the game continues, we must not be in (H,T,H,T).
- Are we in (H,H,T,T)? Do (ADJ) to escape.
If the game continues, we moved to (T,T,T,T) or (H,T,H,T).
Repeat steps 1-2 to test if this is true.
If the game continues, we must not be in (H,H,T,T).
- By elimination, we must be in (T,H,H,H) or (H,T,T,T). Do (ONE) to escape.
If the game continues, we moved to (T,T,T,T), (H,T,H,T), or (H,H,T,T).
Repeat steps 1-3 to test if this is true.
If we “unroll” the recipe above, the sequence guaranteed to win is:
These 15 moves are guaranteed to find (H,H,H,H) at some point along the way, no matter what position we start in, and no matter how unlucky we get with the spins of the table.