COMPUTING SCIENCE

# Recreational Computing

Puzzles and tricks from Martin Gardner inspire math and science

# Coin-Flipping Magic

Our last example of recreational computer science is inspired by two tricks with a blindfolded magician, which involve flipping coins into a desired configuration. Because a volunteer manipulates the coins, these tricks have the distinction of being performable over the telephone, on radio or on television, thus being performed “personally” for many people at once.

The first trick, independently invented by Martin Gardner and Karl Fulves before 1980, involves three coins arranged in a line. The spectator arranges the coins as heads or tails, in any combination they like. The magician’s goal—without seeing the coins—is to make them all the same—all heads or all tails. Naturally, the spectator should not choose this outcome as the starting configuration, or else the trick will be over rather quickly. The magician now gives a sequence of instructions: Flip the left coin, flip the middle coin, and flip the left coin again. In between, the magician asks whether the coins are yet all the same, and continues to the next instruction only if the trick is not yet over. It’s no surprise that the magician can eventually equalize all the coins, but it’s impressive that it always takes at most three moves *(see the fifth figure, at right).*

Why these three moves work is closely linked to a set of codes in computer science that are widely used today to reduce errors when representing digital data with analog signals. These so-called Gray codes, named after Frank Gray from Bell Labs, who patented the system in 1947, have the feature that every two successive binary values differ by only one bit. A configuration of three coins can be seen as a corner of a three-dimensional cube: There are three coins, and each can be either heads or tails, making 2^{3}=8 corners. But the cube is effectively folded in half because the all-heads configuration is just as good as the all-tails configuration, leaving just 2^{2}=4 “double configurations” arranged in a two- dimensional square. The Gray code tells us how to traverse all these nodes by changing one coin at a time, without ever repeating a configuration. Because we are counting moves instead of configurations visited, we get to subtract 1, for a total of 3 moves. More generally, if we had *n* coins, we’d have 2^{n} configurations, 2^{n–1} double configurations, and 2^{n–1}–1 moves in the worst case. This study makes it clear why the trick is for three coins: Four coins would already require 2^{3}–1=7 moves.

To make the trick more impressive, we can give the spectator more freedom. A 1979 letter from Miner Keeler to Gardner, which Gardner wrote about in *Scientific American* in the same year, describes a trick involving four coins arranged in a circle. The setup and goal of the trick are the same as before, but this time the spectator can rotate the circle of coins however he or she likes before following each of the magician’s instructions. The magician follows these seven steps: Flip the top and bottom coins (after rotation), flip the top and right coins (after rotation), flip the left and right coins (after rotation), flip the bottom coin (after rotation), flip the left and right coins (after rotation), flip the right and bottom coins (after rotation) and flip the top and bottom coins (after rotation). Despite the spectator’s apparent flexibility, the magician equalizes all the coins in no more moves than the original four-coin trick *(see the sixth figure, at right).*

What makes this trick possible? A recent paper by two MIT students, Nadia Benbernou and Benjamin Rossman, along with my father and myself, analyzes what type of spectator moves such as “rotate the table” still let the magician equalize the coins with a clever choice of moves. The solution is closely tied to group theory, a field crucial to modern cryptography. The key requirement turns out to be that the number of different moves that a spectator can make is a power of 2. In the case of a rotating table, the number of coins must be a power of 2 (as in the four-coin trick above). But it is also possible, for example, to allow the table to be flipped over, because this precisely doubles the number of possible spectator moves.

Like many people, I love puzzles and magic. I also love theoretical computer science. It is wonderful to combine these loves, following in the footsteps of Martin Gardner, and I hope that more computer scientists will consider the recreational side as a good source of fun problems to solve, which may also lead to practical research. Let’s keep carrying the torch that Gardner left burning.

# Bibliography

- Benbernou, Nadia, Erik D. Demaine, Martin L. Demaine and Benjamin Rossman. 2008. Coin-flipping magic. Presented at Gathering for Gardner 8, March. http://erikdemaine.org/papers/CoinFlipping.
- Cipra, Barry, Erik D. Demaine, Martin L. Demaine and Tom Rodgers (eds). 2004.
*Tribute to a Mathemagician*. Natick, Mass: A. K. Peters, pp 23–30 and 63–72. - Demaine, Erik D., Martin L. Demaine and Helena A. Verrill. 2002. Coin-moving puzzles. In
*More Games of No Chance*. Cambridge, U.K.: Cambridge University Press, pp 405–431. - Demaine, Erik D., and Joseph O’Rourke. 2007.
*Geometric Folding Algorithms: Linkages, Origami, Polyhedra*. Cambridge, U.K.: Cambridge University Press. - Gardner, Martin. 1989. Penny puzzles. In
*Mathematical Carnival*, chapter 2. Washington, D.C.: Mathematical Association of America. Originally published in*Scientific American*, February 1966. - Gardner, Martin. 1995. Paper cutting. In
*New Mathematical Diversions*, chapter 5. Washington, D.C.: Mathematical Association of America. Originally published in*Scientific American*, June 1960.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Feature Article**: Restoring Depth to Leonardo’s Mona Lisa

**Perspective**: Taking the Long View on Sexism in Science

**Computing Science**: Computer Vision and Computer Hallucinations