Three cups problem

The three cups problem is a mathematical puzzle that, in its most common form, cannot be solved.

In the beginning position of the problem, one cup is upside-down and the other two are right-side up. The objective is to turn all cups right-side up in no more than six moves. You must turn over exactly two cups at each move.

Solvable version

The solvable (but trivial) version of this puzzle begins with one cup right-side up and two cups upside-down. To solve the puzzle in a single move, you need only turn up the two cups that are upside down — after which all three cups are facing up.

Proof of impossibility

The proof that the problem is impossible to solve is done by means of exhausting cases.

As a starting position, we place cup A up, cup B down, and cup C up — the reverse of the figure above. Using a well known formula for combinations,^[1] we find that two items can be selected, without regard to their order, from three items in three ways. In this instance, the three ways are:

1. Select cups A^U and B^D
2. Select cups A^U and C^U
3. Select cups B^D and C^U

Where U means Up, and D means Down.

If we flip selection 1 we get A^D and B^U.

If we flip selection 2 we get A^D and C^D. Cup B remains down, so now all three cups are down.

If we flip selection 3 we get B^U and C^D.

Thus we see that in all three cases at least one cup remains down after flipping. Reversing any one of these flips restores the starting position of the cups.

This exhausts the possible combinations of two cups selected (without order) from among three; no other combination of two cups is possible. Therefore the problem cannot be solved.

Notes

^ ${\frac {n!}{k!(n-k)!}}$ where $k\leq n$ . n is the number of items, and k is the number of items to be selected from them.

[1] ${\frac {n!}{k!(n-k)!}}$ where $k\leq n$ . n is the number of items, and k is the number of items to be selected from them.

[1]

Solvable version

Proof of impossibility

See also

Notes