# Mathematics Awareness Month 2014: Mathematics, Magic, and Mystery

### Navigate the Calendar

# Mathematical Mind Reading

Can you use mathematics to read someone's mind? Watch the following videos to find out. The first video was made by Richard Wiseman, and in it he demonstrates just how predictable you can be. A full explanation is provided in the second video, made by James Grime.

# Taking it Further

Once you understand the basic idea, you will be equipped to grapple with a broad variety of problems and puzzles based on the same principle. Here are a few to play with:

- Can you modify the trick to work on a hexagonal grid rather than a square one? How about on a triangular grid?
- Place a knight on a 5 x 5 chessboard. Is it possible for the knight to make a sequence of legal "knights moves," in which it visits every square on the board exactly once, and then returns to its original square? This is known as the
*knight's tour*problem. - Is it possible to find a knight's tour on an m x n chessboard, where m and n are both odd numbers?

# The Underlying Mathematics

The principle at work here is a *parity constraint*, since your location depends on the oddness or evenness of certain numbers. This principle belongs to the fields of *graph theory* and *combinatorics*, although it is also common in many other branches of mathematics, such as *algebraic topology*. The great Leonhard Euler's solution to the infamous Königsberg Bridge Problem is an outstanding example of a mathematical parity argument from the eighteenth century. The knight's tour problems themselves belong to a more difficult class of problem: finding a Hamiltonian cycle in a graph. In the simplest cases (such as the knight's tour problems stated above), a parity argument can be used to show that such a cycle cannot exist.

Other fundamental combinatorial results, such as the handshaking lemma and Sperner's lemma, are also based on parity constraints.

An example of a more subtle problem where a parity constraint is at work is the *Lamp Lighting Problem*, sometimes called the *All Ones Problem*:

*
A janitor is walking through a museum in the morning, switching on the light in every room. The electric connections are a bit tricky, however. In every room there is a button, and pushing a button toggles the light on/off not only in that room, but also in all adjoining rooms! Can the janitor light up every room in the museum?
*

Amazingly, the answer does not depend on the floor plan of the museum, which may have any number of rooms, and be laid out in any way imaginable. To the best of our knowledge this problem first appeared in print as problem 5.17(c) in the book Combinatorial Problems and Exercises, by László Lovász (North-Holland, 1979), although it is widely attributed to Klaus Sutner. A solution is provided in Lovász's book. A more thorough account is available here.