4by12

Four Cups

Four coins are placed on a round table, in positions north, east, south, and west. The room is dark, so you can’t see the coins. Your goal is to get all coins to be on the same side — heads or tails. In each turn you can choose to flip any of the four coins. After the coins are flipped, the table is rotated randomly and the turn ends. Once all the coins lie on the same side, the game ends and you win.

This is one of my favorite riddles, because the solution actually uses some nice mathematical concepts.

We are looking for a solution that will work regardless of how the table is rotated after each flip we make. It will be nice if we can place all the possible table states into classes that aren’t affected by the rotation. That way we can develop an algorithm to progress through the states without worrying about the rotation at each turn.

Let’s define the following states:

1. A: All coins are the same (all heads or all tails) - in this case we win
2. B: Two opposing coins are heads, and the other two are tails.
3. C: Two adjoining coins are heads, and the other two are tails.
4. D: One coin is different from the other three.

The last three states are illustrated below.

It’s clear that if a state is in a given category, then any rotation of it remains in the same category. Formally we can say that these categories are equivalence classes, using the relation that connects two states iff one can be reached from the other via rotation.

Okay, so our goal is to transform a state of any class to class A. We notice that coin flips change some classes but not others:

• Flip two opposing coins: This changes a B state to A (i.e. we win), but doesn’t transform either a C state or a D state to a different class
• Flip two adjoining coins: C -> B or A, and D doesn’t change
• Flip one coin: D -> C or B or A

The winning strategy is thus:

1. Flip North, South
2. Flip North, East
3. Flip North, South
4. Flip North
5. Flip North, East
6. Flip North, South

This works as follows:

• If we start out in class B, we win after step 1
• If we start out in class C, we win after step 2 or 3
• If we start out in class D, we win after step 4, 5, or 6

The point here is that when we handle class B, we don’t change either C or D. When we handle C, we don’t change D. So there you have it — victory in just six steps!