Arithmagic

Watch him pull a rabbit out of his hat? Not exactly.

Arthur T. Benjamin eschews the usual trappings of the magician's trade. Calling himself a mathemagician, he astonishes audiences with amazing feats of mental arithmetic. Behind the scenes, he reveals how you, too, can look like a genius without really trying.

Photo by Richard Haverty

A math professor at Harvey Mudd College, Benjamin has brought his particular brand of prestidigitation to a wide variety of appreciative audiences. He has appeared on television programs and performed in night clubs, classrooms, and banquet halls. He has even traded quips with comedian Stephen Colbert on The Colbert Report.

Benjamin's act is a striking demonstration of how miraculous fairly ordinary, simple mathematical machinery can appear when you don't really know what's going on under the hood.

One of my first encounters—many, many years ago—with arithmetic shortcuts was in a book titled Cheaper by the Dozen, the story of efficiency expert Frank B. Gilbreth and his family of 12 children. In a chapter about dinner conversation, Frank B. Gilbreth Jr. and Ernestine Gilbreth Carey write, "Also of exceptional general interest was a series of tricks whereby Dad could multiply large numbers in his head, without using pencil and paper."

For example, to multiply 46 times 46, you figure out how much greater 46 is than 25. The answer is 21. Then you calculate how much less 46 is than 50. The answer is 4. You square 4 and get 16. Putting 16 and 21 together gives the answer 2116.

That's the sort of venerable procedure that Benjamin uses to do fast multiplies and to square four-digit numbers faster than someone using a calculator. Turning a repertoire of such calculating tricks into a real show, however, requires developing a memory for numbers and learning how to calculate from left to right, performed at the speed of rapid-fire chatter.

Suppose you want to multiply 378 by 7. Starting from the left, you would get 2100 (300 x 7) plus something more. In the next step, 70 x 7 equals 490, which is added to 2100 to give 2590, plus something more. Finally, 7 x 8 equals 56, which is added to 2590 to give 2646.

One advantage of using this method is that you can start saying the answer while you're still calculating it, Benjamin remarks.

Here's a neat way to square two-digit numbers. Suppose the number to be squared is 37. That number is 3 less than 40, and 34 is 3 less than 37. Multiply 40 by 34 to get 1360, then add the square of the difference, 3² or 9, to get 1369.

The trick is to choose the difference so that the multiplication is easy. For example, to square 59, choose a difference of 1. Go up to 60 and down to 58. Multiply 60 times 58 to get 3480, then add 1² , to obtain 3481.

The proof is in the algebra: a² = (a + d)(a - d) + d² . The same idea can be extended to squaring 3-digit and 4-digit numbers.

Interestingly, when Benjamin performs calculations involving long sequences of digits, he relies on a phonetic code to remember the numbers. "There's no mental blackboard," he says. "It's much more an auditory process."

Benjamin turns sequences of digits into words that add up to some sort of crazy scenario. For example, he can mentally convert the sequence 9 6 4 8 3 7 5 4 8 3 1 2 7 5 9 6 into the words "pitcher fume color fume tinkle beach" as a handy mnemonic for (9 6 4) (8 3) (7 5 4) (8 3) (1 2 7 5) (9 6).

The underlying scheme assigns different consonants to different numbers, and the memorizer supplies the vowels: 1 (t, d), 2 (n), 3 (m), 4 (r), 5 (l), 6 (j, ch, sh), 7 (c, k, g), 8 (f, v, ph), 9 (p, b), 10 (z, s). This is the modern version of a number alphabet originally proposed by Pierre Hérigone and published in Paris in 1634. Three consonants—w, h, and y, spelling "why"—do not appear in the list.

For more on phonetic codes, see Benjamin’s article "A Better Way to Memorize Pi: The Phonetic Code," published in the February 2000 Math Horizons.

Benjamin can also handle magic squares, natural logarithms, cube roots, and much more. "As a kid, I liked to show off," he says. "Now I get paid to do this!" Besides, the techniques are so easy that even an elementary-school student can master them.

Benjamin describes and explains many of his mental calculation techniques in the book Secrets of Mental Math: The Mathemagician’s Guide to Lightning Calculation and Amazing Math Tricks (coauthored by Michael Shermer).

He also has a set of DVDs in The Great Courses series devoted to "Secrets of Mental Math." Benjamin’s "Mathemagic" performance, available as a TED video, has been viewed more than 5 million times.

Benjamin wrote about the mathematics underlying some of his mental feats in an article published in the January 2012 College Mathematics Journal—a special issue dedicated to Martin Gardner. Titled "Squaring, Cubing, and Cube Rooting," the article starts off:

"I still recall the thrill and simultaneous disappointment I felt when I first read Mathematical Carnival by Martin Gardner. I was thrilled because, as my high school teacher had told me, mathematics was presented there in a playful way that I had never seen before. I was disappointed because Gardner quoted a formula that I thought I had 'invented' a few years earlier. I have always had a passion for mental calculation, and the formula . . . appears in Gardner's chapter on 'lightning calculators.' It was used by the mathematician A. C. Aitken to square large numbers mentally."

Benjamin's article is reprinted in Martin Gardner in the Twenty-First Century, edited by Michael Henle and Brian Hopkins (MAA, 2012).

Original version posted October 5, 1998

Reference:

Gardner, M. 2008. Memorizing numbers. In Hexaflexagons, Probability Paradoxes, and the Tower of Hanoi: Martin Gardner's First Book of Mathematical Puzzles and Games. Cambridge University Press and MAA.

Sliding Around

Try the following sliding-coin puzzle.

Place four coins on the bottom row of circles (G, D, E, and R), leaving the letters MARTIN exposed. Your challenge is to slide the coins along the paths joining the circles so that the four coins cover the top row of circles (M, T, I, and blank), exposing the letters GARDNER.

Sounds simple? The catch is that at no time are two coins allowed next to each other when a path joins the two circles. For example, you can't move the G coin initially because the only allowed move would put it next to the D coin. The D coin can move to the T circle but not to the A circle or the I circle. You also have to slide the coins one at a time, all the way from one circle to another. And, where paths cross, you can't switch from one path to another en route.

Robert A. Hearn invented this puzzle in honor of Martin Gardner, mathemagician extraordinaire.

In traditional sliding-coin puzzles, a set of coins laid out in a certain arrangement must be slid into a new configuration in the fewest possible moves. It's been proved for these types of puzzles that it's always computationally "easy" to determine whether a given puzzle is solvable.

Hearn's Martin Gardner coin-sliding puzzle, however, is a different sort of beast. It's more akin to sliding-block puzzles, such as the infamous 15 puzzle than to traditional sliding-coin puzzles.

It happens to take 25 moves to solve the Martin Gardner puzzle. In exploring how hard it might be solve such puzzles in general, Hearn discovered that there's a relatively simple way to generate arbitrarily difficult instances. Indeed, it's easy to make puzzles for which it's computationally very difficult to determine whether there's a solution at all.

More formally, it turns out the Hearn's new type of puzzle belongs to a category of computational problems described as PSPACE-complete. This means that you should expect that, as the number of circles and paths gets larger, the amount of computer time required to solve the puzzle increases exponentially in the worst possible case, even though the amount of memory required increases merely algebraically with size.

Here's another puzzle for you to try.

Place four coins on the red circles. Slide the coins along the paths so that there is a coin on every starred circle. At no time may any two coins be adjacent—occupying two circles joined by a path. You should be able to solve this puzzle in 28 moves.

Hearn has tried a number of variations, such as using tokens or coins of different colors. "Then the start and end configurations have specific places for each color of token," Hearn says. "This makes more complex puzzles possible on smaller graphs." Mathematically, a graph is an array of vertices or nodes (circles in this case) connected by edges (paths).

In this puzzle, each of four tokens has a different color, initially placed as shown by the colored dots. Your goal is to move each token to a space containing a circle of the same color. Solving this particular puzzle requires 116 moves.

Hearn's Martin Gardner coin-sliding puzzle also inspired puzzle designer James Stephens, who runs the PuzzleBeast website, to create a computer-generated set of puzzles called the "Meandering Monk Maze."

Reference:

Hearn, R.A. 2005. The complexity of sliding-block puzzles and plank puzzles. In Tribute to a Mathemagician, B. Cipra, E.D. Demaine, M.L. Demaine, and T. Rodgers, eds. A K Peters.

Originally posted October 24, 2005

Illustrations and puzzles courtesy of Bob Hearn

The Complexity of TipOver and Other Puzzles

Imagine a warehouse with several vertical stacks of crates. Standing on top of one of the stacks, James Bond has to reach a particular crate. He can't touch the electrified warehouse floor, so he must topple some of the stacks to reach others to eventually get to the target crate. His problem, then, is to figure out the right stacks to tip over in the right directions in the right order. A stack falls as a unit, crates can tip over only into empty spaces, and Bond can't leap across empty space or move diagonally to reach other crates.

This scenario is the basis for an entertaining and challenging puzzle called TipOver, made by ThinkFun. In 2006, Games magazine named it "puzzle of the year."

TipOver started out as an online game invented by James W. Stephens of Atlanta. It's featured on his PuzzleBeast website as the "Kung Fu Packing Crate Maze." Puzzle inventor M. Oskar van Deventer created the three-dimensional version sold by ThinkFun.

Robert A. Hearn has had a longstanding interest in the connection between combinatorial games and computation. He has proved a variety of results related to computational complexity for sliding-block puzzles, sliding-coin puzzles, plank puzzles, hinged polygon dissections, Amazons, Konane, Cross Purposes, and others. He has also strengthened existing results or provided new, simpler proofs of complexity for games and puzzles such as Minesweeper, the Warehouseman's Problem, Sokoban, and Rush Hour.

Many of these results were included in Hearn's 2006 doctoral thesis on "Games, Puzzles, and Computation," which became the basis of a book with the same title (CRC Press, 2009) and coauthor Erik D. Demaine (Hearn's thesis adviser).

In the case of TipOver, Hearn proved that this puzzle belongs to a class of computational problems described as NP-complete. He described those results in the article "TipOver is NP-complete," published in the Mathematical Intelligencer (Vol. 28, No. 3, pp. 10-14).

In its starting configuration, a TipOver puzzle has several vertical crates of various heights (1 x 1 x h) arranged on a square grid. A tipper—representing a person navigating the layout—stands on top of a particular starting crate. There is a special 1 x 1 x 1 red crate—the target—elsewhere on the grid.

The tipper can topple any vertical crate that it is standing on, in any of the four compass directions, provided there's enough space for the crate to fall unobstructed and lie flat. The tipper can walk (or climb) along the tops of any crates that are adjacent, even when they have different heights.

In the sample puzzle and solution shown below, the numbers indicate the vertical height of each untoppled crate. The tipper starts on the purple crate. In the first move (top, second from left), the tipper has moved to one of the green crates (3 units tall) and toppled it southward so that it ends up adjacent to a yellow crate that is 2 units tall.

"Surprisingly, it does not take many crates to make an interesting puzzle," Hearn writes. "The number of tips required can never be more than the number of crates—once a crate has been tipped over, it stays fallen—yet finding the correct sequence can be quite a challenge."

To prove that TipOver is NP-complete, Hearn showed that TipOver puzzles are related to a well-known problem in computer science called the Boolean formula satisfiability (SAT) problem.

Consider, for example, two variables, x and y, and the logical statement (x OR y) AND ((NOT x) OR (NOT y)). The OR means that the clause (x OR y) is true if either x or y is true, and the AND means that the clause (x AND y) is true only if both x and y are true. Solving the given problem means assigning a value of true or false to each of the two variables so that the entire statement is satisfied. Here, x must be true and y false, or vice versa, for the statement to be true.

"For any given instance of SAT, there is a corresponding TipOver puzzle that can be solved just when the SAT problem can be solved," Hearn says.

SAT is the prototypical NP-complete problem. Roughly speaking, an NP problem is one for which it is relatively easy to check whether a given answer is correct, but may require an impossibly long time to solve by any direct procedure. In general, as the number of elements, n, increases, a computer's solution time grows exponentially in the worst case. In effect, systematically solving such a worst-case problem involving many elements can take an enormous amount of time, even on the fastest available computers.

Hearn's results show that TipOver must be at least as hard as SAT. "It's easy to show that TipOver is also no harder than SAT," Hearn says, "so TipOver must be NP-complete as well."

Interestingly, Minesweeper, Tetris, and n x n sudoku also belong to the NP-complete category.

How hard is TipOver? "Is there, perhaps, a clever algorithm for coming up with a solution to a given puzzle instance?" Hearn asks. Probably not, he responds.

Hearn has also applied his analytic techniques to plank puzzles, invented by Andrea Gilbert and available as River Crossing from ThinkFun.

In this case, you have to cross a crocodile-infested swamp using only wooden planks supported by tree stumps. You can pick up planks and put them down between other stumps, as long as the stumps are exactly the right distance apart. You can't let planks cross each other or intervening stumps, and you can carry only one plank at a time.

Here's a sample puzzle.

To solve the puzzle, you start by walking across the first plank (length 1) to get to a stump. You pick the plank up, lay it down to the south, walk across it, pick it up again, lay it down to the east, walk across it again, pick it up again, walk across the length-2 plank, lay the length-1 plank down to the east, and so on.

It turns out that plank puzzles belong to the class of computational problems known as PSPACE-complete. Such problems are thought to be computationally harder than their NP-complete counterparts.

"We should not be surprised that [plank puzzles] can be very challenging," Hearn says. "It can be very difficult to determine whether there is a solution, and there are puzzles that take exponentially many moves to escape."

At the same time, no one has yet proved that there is no efficient algorithm for solving all NP-complete (or PSPACE-complete) problems. Indeed, finding an efficient method to solve TipOver could yield the most important computer science result of all time—an achievement worth a $1 million prize.

Originally posted Feb. 19, 2007