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:
[Show 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.
Winning strategy
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:
ALL,OPP,ALL,ADJ,ALL,OPP,ALL,ONE,ALL,OPP,ALL,ADJ,ALL,OPP,ALL
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.
Cool. I suppose it depends a bit on what is meant by
“Can you find a series of steps that guarantees you will have all of the quarters heads up in a finite number of moves?”
If asserting that the number of moves is finite With Probability 1 is enough, I think a simple decision rule of at each position saying ‘flip kth coin’ and ‘do nothing’ (being n+1 distinct mutually exclusive choices selecting one at random, each with equal probability of $\frac{1}{n+1}$) is enough to guarantee an aperiodic, irreducible finite state (time homogenous) markov chain that includes all possible configurations. All states are visited WP1 and the time until first visit is stochastically smaller than some geometric random variable.
This is the random walk approach.
Agreed.
My take was different: I interpreted the question to mean that the algorithm had to have a uniform bound on stopping time that was robust to adversarial table spins. So really, I assumed the table spins weren’t random at all.
Laurent, Nice solution!
I modeled as a non-deterministic finite automaton that tracks all the possibilities (or all the possibilities with non-zero probability wrt the previous post). Then, I used breadth-first search on it to find the optimal 15-move solution.
Write up and code here:
https://colab.research.google.com/drive/1cPTMDfRgjbh9c_uabdM4B2XWWewkmO08
I did some statistical analysis over several hundred trials and found that the distribution of the number of steps required to reach a solution is pretty flat. I thought there might be an expectancy of some likely number of steps (a bell curve) but that wasn’t the case.
15 moves maximum.
A4 = flip all 4 coins
BR= flip bottom right coin
TLBR= flip top left, bottom right coins
B2= flip bottom 2 coins
I think the following sequence of steps will win every time:
A4
BR
A4
TLBR
A4
B2
A4
TLBR
A4
BR
A4
B2
A4
TLBR
A4
Nice illustration of the state diagram!
To be pedantic, it’s probably more accurate to say this problem is about probability (or combinatorics) than statistics 😉
I solved for n=2^k coins, using a recursive trick where you simultaneously play two games half the size. Your solution matches the recursive solution.
https://joshuameisel.github.io/Spinning-Table-Riddle/
It also turns out there’s no solution for any other n.
You listed 5 possible moves, and it seems 1 of them (TRI) was omitted from the discussion. Can you explain why?
It turns out this move is not needed. If you work out the transition diagram for (TRI) as I did with the other moves, you’ll find that it is very similar to the diagram for (ONE). In fact, you can take the solution I found and replace ONE with TRI and it still works!
I’d say the reason is because (TRI) is equivalent to (ONE) + (ALL) move, and (ALL) does not really change the state (except TTTT -> HHHH, which finishes the game).
you need 7 moves at maximum by switching between diagonals and sides. also note that out of 16 possible combinations, there are 8 pairs of equivalent classes like HHHH and TTTT. Since the starting position is not one of the above, so only 7 moves (at max) are needed to get to a solution.