5
$\begingroup$

A friend of mine recently shared the following puzzle with me:

Puzzle: A circular turntable is divided into four congruent quadrants by two perpendicular lines. (Think of a circle in the $xy$-plane centered at the origin and divided into quadrants by the coordinate axes.) In each quadrant is a quarter covered by an upside down opaque cup. The cups are identical in appearance as are their relative positions in each quadrant. A "move" consists of removing any two cups and then changing the orientations (heads up\tails up) of none, one, or both of the corresponding coins. After the move you turn your back and a judge inspects the coins under the remaining two cups. You "win" if all four coins are oriented the same, either all heads up, or all tails up. If you fail to win on a move then the judge replaces the cups back in their original (indistinguishable) positions over the (currently oriented) coins and gives the turntable a spin. When it stops rotating you turn back around and are allowed another move. Prove that you can win in at most five moves.

After toying around with this puzzle for a bit, I was able to come up with three different solutions, all of which involved 5 moves. (My friend originally had a solution involving 6 moves but improved to 5, hence the requirement to find a solution involving at most 5 moves.)

Question: Is it possible to guarantee a solution involving only 4 moves? Or a clever (i.e., not brute force) proof that demonstrates 5 moves is the smallest number of moves that guarantee a win?

$\endgroup$
  • $\begingroup$ Are we guaranteed that the initial position is not winning? $\endgroup$ – Ross Millikan Dec 16 '18 at 18:39
  • $\begingroup$ @RossMillikan My understanding (from what I have been told about this puzzle at least) is that there are no restrictions on initial conditions; thus, it is conceivable that one could have all coins oriented the same before even making a move. In all of my solutions, I assumed failure after each move until I forced a win. $\endgroup$ – Daniel W. Farlow Dec 16 '18 at 18:54
  • $\begingroup$ I am familiar with a similar puzzle where you can flip coins in any configuration but do not get to examine them and must wind up all heads. The accepted answer assumes you do not start all heads. $\endgroup$ – Ross Millikan Dec 16 '18 at 20:50
3
$\begingroup$

Here is a proof that $5$ is the minimum:

First, every turn consists of two 'moves': a 'choice-move', which is where you choose which two cups to remove, and a 'flip-move', where you flip any of the coins you get to see.

Second, note that there are only two possible 'choice-moves': you either choose two adjacent cups or two opposite cups ... and it is clear from the setup that it doesn't matter which of the four adjacent pairs or which of the two opposite pairs.

Third, there are only three kinds of coin-configurations where not all four coins face the same way:

A. three coins face the same way

B. two adjacent coins face the same way

C. two opposite coins face the same way

You yourself can be in one of several states as well which, as we will see, are listed here from 'best' to 'worst':

  1. You know you are in situation C

  2. You know you are in situation B

  3. You know you are in situation A

  4. You know two coins face the same way, but you don't know whether it's B or C

  5. You don't know whether you are in situation A, B, or C

Let's consider these, in order from 'best' to 'worst':

  1. if you know that you are in situation C, then the optimal strategy is of course to choose two opposite coins and flip them, and thus finish the game (and you obviously can't do better than that)

  2. If you know you are in situation B, then the optimal strategy is to choose two adjacent coins: if they are the same, flip them both, and that will finish the game, and if they are not the same, then flip them both to get into situation C, and finish the game after that. It is clear that this is the best strategy for state 2, since choosing two opposite coins (which will have opposite sides) and then flipping no or two coins will make you stay in state 2, and flipping 1 coin makes you go to state 1 which, as we will see, is even worse.

  3. If you know you are in situation A, then the optimal strategy is to choose two opposite coins. If you happen to know which side it is that is the odd one out, then if you see that one, flip it and you win (clearly can't do better). If you see two of the same faces, then flip one of the coins, which will get you into state 2 (can't do better, since flipping none or both will keep you in state 1), and thus two moves from finishing the game. Choosing two adjacent coins is not a good strategy when in state 1, since you might get to see two coins that are facing the same way, and thus flipping none or both keeps you in state 1, and since you do not know where the odd one out is located, flipping one coin gets you to state 4 which, as we will see, has a worst-case scenario of being 3 moves from finishing the game. In other words, the best strategy when in state 3 is to choose opposite coins, which with optimal game-play has a worst-case of finishing the game in 3 moves.

  4. If you know that the coins are in configuration B or C, but you don't know which one, then the optimal strategy is to choose two opposite cups, since choosing two adjacent cups might reveal two coins that are not facing the same way, which would be compatible with both B and C, and so that does not tell you anything. Now, if the two opposite coins show the same face, then you are clearly in situation C, so flip both to finish the game. If the opposite coins show different faces though, you know you are in situation B, but flipping any coins does not improve your state, meaning that you can move to state 2, and finish the game in at most 2 moves. Hence, in the worst-case scenario, it will take 3 moves to finish the game when in state 4.

  5. Finally, at the start of the game you are in state 5. You can now finish the game in at most 5 moves by doing the following: select two adjacent cups, make sure both coins are heads, and then on the next turn choose two opposite cups, and again make sure both coins are heads. This will ensure that yo have flipped exactly three coins to heads, and thus that you are in state 3 if you didn't finish the game already. And, as we saw, it takes at worst 3 more moves to finish the game.

Notice that you could of course have made the three coins tails as well, and you can also first choose two opposite coins and then choose adjacent coins.... although for an optimal strategy that minimizes the expected number of turns, you should first pick two adjacent cups, and then pick two opposite cups, for if the opposite cups show the same face, then you can flip one of them to ensure you get to configuration B.

OK, but why can't you do better, starting at the very start of the game? Well, after one turn you have not seen two of the coins, and hence you cannot know whether you are in situation A, B, or C.

Moreover, it is impossible to get to either state 1 or 2 in just 2 moves from the start:

First of all, if you make the same 'choice-move' for the first two moves, then it is possible to see the exact same two coins twice, meaning that you do not know anything about the other two coins, except that, given that you made the two coins you saw face the same way, the other two coins are not both also facing that way. Hence, you do not know whether one of both of the other two coins are facing the other way, and hence you can't get to state 1 or 2 that way.

However, if you make two different 'choice-moves' for the first two moves, then you are guaranteed to see exactly three different coins, meaning that you do not know the orientation of the fourth coin (and hence again you cannot get to state 1 or 2), unless you made all the 3 coins face the same way ... which is exactly what we claimed was the optimal strategy, and which leads to a worst-case of 5 moves.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.