Three cups problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

The solvable version of the Three Cups Problem is shown here. In the impossible version, cups A and C are upright, and cup B is turned down.

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[edit]

To see that the problem is insolvable (when starting with just one cup upside down), it suffices to concentrate on the number of cups the wrong way up, which we may call W. We observe that we are required to change W from 1 to 0, i.e. by -1; it is therefore sufficient to show that any move changes W by an even number. Since a move inverts two cups and each inversion changes W by +1 (if the cup was the right way up) or -1 (otherwise), a move changes W by the sum of two odd numbers, which is even, completing the proof.

More generally, this argument shows that for any number of cups, we cannot reduce W to 0 if it is initially odd. On the other hand, if W is even, all we need to do is invert them two at a time until W is 0.

See also[edit]

Notes[edit]