by Wells, David
Figure 1.9 Knight tour on 8 by 8 board
Euler, ingenious as always, found novel tours on the 8 by 8 board as well as this 5 by 5 tour in which the numbers on the diagonal from start to finish form an arithmetical progression with common difference 6 (Figure 1.10).
Figure 1.10 Euler tour with AP
Some knight's tours are very pretty, even beautiful, and they also have an element of dynamism: we can feel that we are observing the behaviour of the knight as it wanders the board. We also realise that all possible tours are in a sense – ‘in theory’ – defined from the moment we specify the conditions of the problem – but we still have to discover them in practice, and this is a very difficult task.
There are many variations on the original knight's tour. ‘Fairy chess’ enthusiasts have generalised the puzzle by trying different shapes and sizes of boards, and knight tours in three dimensions, as well as extended knight moves such as ‘along 3 and 1 up or down’.
The Königsberg puzzle and the knight tour appear at first glance to be different types of puzzle. The chess board is plainly geometrical with straight lines and right angles and 64 identical black and white cells. However, we also know that chess does not have to be played on such precise boards. Indeed, there are stories of chess being played on very strange boards indeed and with weird pieces, for example by prisoners in their cells.
Chess can also be played mentally, in the head. The world champion Alexander Alekhine once played 32 games simultaneously blindfold. In 1937 George Koltanowski increased the record to 34 games and Miguel Najdorf raised it again to 45. Then in 1960 Janos Flesch played 52 games, winning 31, drawing 18 and losing only 3. The Russians later banned their top players from blindfold displays because of the great mental strain [Birbrager 1975]. Shakhriyar Mamedyarov, one-time World U-21 Champion, trained by solving thousands of positions blindfold and in some recent tournaments the games are split between normal over-the-board play, quick play to a very short time-limit, and blindfold play.
The crucial point is that blindfold chess is possible. Indeed, most good players can play a couple of games in their heads, at the same time, without a superpower memory. What happens to the chess board ‘in the head’? It is ‘there’ in some mysterious sense that psychologists have not yet fully explained but it is less precise because geometrical precision is not necessary to play chess. All we need is a record of the relationships between the ‘squares’, as we can see from this imprecise and ‘ugly’ 5 by 5 board (Figure 1.11) on which we have marked the start of another solution.
Figure 1.11 Start of hand-drawn 5 by 5 knight tour
Like our simplified diagram of the Bridges of Königsberg, the chess board is basically a topological object in which it is the relationships between the squares that matter, though a precisely and elegantly drawn and simplified representation – such as any ordinary chessboard – is an immense help to the human player for sound psychological reasons. Similarly, it is the moves of the chess pieces that matter, not their size or design.
Once again, we meet abstraction in which the essential features are preserved and the inessential abandoned. The game of chess itself is universally supposed to be an abstraction from a real battle between two armies that has been simplified by leaving out the messiness and bloodshed of real conflict to create a game of moves and manoeuvres on a board of 64 squares with just sixteen pieces on either side.
Lucas and mathematical recreations
Édouard Lucas (1842–1891) was a talented French mathematician with an enthusiasm for recreations. In his Récréations Mathématiques he discussed the Tower of Hanoi, a puzzle which he invented in 1883 and published under the name, ‘N. Claus de Siam’ as, ‘A game of combination designed to explain the binary system of numeration.’ It created a sensation and was soon exploited in an advertising version, the Eight Puzzle, in which each disc advertised a different product. Lucas also made a giant version more than a metre high for public display. It is indeed a game, albeit a very simple one-person game, and it is also very mathematical. This is how it works. The object is to transfer all the rings in Figure 1.12 from peg A to peg C, following these two simple rules: (1) Only one ring can be moved at a time.
(2) No ring may ever be placed on top of a smaller ring.
The basic insight is that to move the 5 discs from A to C, you need to move the top 4 discs from A to B, then move the largest disc to C, and then move the 4 discs from B to C. The solution starts, naming only the number of the disc and the destination peg:
Figure 1.12 Tower of Hanoi puzzle
1 to C 2 to B 1 to B 3 to C 1 to A 2 to C 1 to C 4 to B 1 to B 2 to A 1 to A 3 to B 1 to C 2 to B 1 to B 5 to C
followed by repeating the process of getting discs 1 to 4 from B to C.
Why do we say this was so mathematical? Here are three reasons: • It is abstract.
• It can be played in the head.
• We can prove our conclusions.
It is abstract, because you can make the pieces of anything you like, and their exact dimensions don't matter. The rules refer to the size of the rings but you could just as well distinguish them by colour from dark to light or by numbers or by letters of the alphabet. The only crucial feature is that they are arranged in a fixed order.
It can be played in the head. You might try this yourself: start with 2 discs, then 3 discs, then 4, and see how quickly and correctly you can transfer them. (There is a simple rule which tells you which empty peg the first disc should be moved to.)
You can prove your conclusions about it. We have almost done this already. In order to move N + 1 discs from peg A to peg C, N discs must be moved to peg B, the largest disc moved to peg C and the remaining disks moved from B to C. Therefore, if it takes P moves to move N discs it takes 2P + 1 moves for N + 1 disks. The sequence of minimum moves needed for n disks therefore starts, disks
1
2
3
4
5
6
7
8
9
…
moves
1
3
7
15
31
63
127
255
511
…
The formula for N disks is 2N − 1. (Generalisations of the Tower of Hanoi are a very different matter. How many moves are needed if you have not 3 pegs but 4 or 5? If the disks are initially placed not all on one peg, but on several different pegs? These problems are much harder.)
The solution we have given requires no figure or diagram, but we can if we wish represent the solution as in Figure 1.13. All possible moves for 3 disks are represented in the graph which resembles the pattern of Pascal's triangle.
(It is a mathematical graph because it consists of points or vertices, joined by lines: each vertex represents a position, and each line joins two positions that can be reached from each other in a single move.)
The notation (2,3,1) indicates that the smallest disk is on peg 2, the middle disk in peg 3 and the largest disk is on peg 1. If all three disks start on peg 1, then they can be moved to peg 2 in 7 moves by simply following the sequence down the left side of the triangle.
We could say that the original ‘physical’ puzzle and this diagram have exactly the same form or structure, with the difference that seeing a path from one point on the diagram to another, with the eye, is far simpler than actually making the moves of the puzzle that they represent!
The diagram also illustrates a crucial point that we shall meet again and again and again: the original rules of the Tower of Hanoi puzzle are very simple and say nothing about any pattern or structure beyond the original three pegs and the disks of decreasing size. Yet as soon as we explore it we discover a hidden structure that is implied by the rules but which can only be discovered by experience, plus imagination and insight. We experience this hidden structure when we learn to solve the puzzle and the diagram then makes it visi
ble.
Lucas's game of solitaire calculation
One of Lucas's many interests was finding whether a given number is prime. He was the first mathematician to find tests for extremely large numbers that were much quicker to execute than dividing by all possible factors. In 1876 he showed that the enormous Mersenne number, M127 = 2127 − 1 is prime by using this test.
Let p = 24m+3 −1, where 4m + 3 is prime. Form the sequence 3
7
47
2207
4870847….
in which S1 = 3 and Sn+1 = Sn2 − 2. Then p is prime if the smallest value of k such that p divides Sk, is 4m + 2.
This test is simple in theory but requires an enormous amount of computation. How did Lucas do it by hand? With typical ingenuity he used binary arithmetic and turned the calculation into a kind of game, using a 127×127 chess board. Here is his method applied to the much simpler example of M7. (Readers of a nervous disposition may prefer to skip this explanation.)
The main operation of testing involves squaring, subtracting 2, and reduction modulo 127. To perform this on S3 to calculate S4, we first write S3 in binary, as 101111. Next, we start to square it by traditional long multiplication, applied to binary: 101111
101111
–––––––––––––––––‐
101111
101111
101111
101111
000000
101111
Next, because we only need to find the answer modulo 127, and we know that 27+m = 2m (mod 127), so 27 = 20, 28 = 21, 29 = 22, and so on, we put the lines of the long multiplication into this square array: No. of column
7654321
0101111
1011110
0111101
1111010
0000000
1101011
Lucas suggested using part of a chess board, with pawns for ones and empty squares for zeros, following these two rules: (1) Take (when possible but only once) a pawn away from column 2. This corresponds to subtracting 2 from the square. If a pawn never appears in column 2, then 2 must be subtracted from the final answer.
(2) For each pair of pawns in any column, remove one from the board and move the other into the column to the left, remembering that the columns to the left of column 7 is column 1.
Continue performing these operations until the only pawns remaining are in the first row. Lucas claimed that the operations of his ‘game’, with practice, could be performed extremely quickly and this was how he showed that M127 is prime. On the other hand, it would be easy to make a mistake which no doubt explains why Lucas ever afterwards showed a slight uncertainty as to whether he really had proved the primality of M127.
Euler's ingenuity showed that everyday puzzles and well-known games can be the basis for fascinating mathematics. Lucas's cunning transformation did the opposite – it turned an apparently forbidding calculation into something much like a simple game. In recent years mathematicians have turned their attention to many other everyday situations and given them the mathematical treatment they deserve. Have you ever said as you cut a cake, ‘I’ll cut, you choose!’? This is the simplest way to divide a cake fairly between two people so both recipients will be satisfied – but what if the cake has to be divided between three or more people? You will find the answers in the book Cake-Cutting Algorithms by Jack Robertson and William Webb [Robertson & Webb 1998].
You are no doubt aware also that there is more than one way to tie a tie, from the standard schoolboy knot to the Windsor knot, favoured by the late Duke. Knots are very ancient indeed but an essential part of the modern mathematical study of topology so it can't be too surprising that two ingenious Cambridge mathematicians, Thomas Fink and Yong Mao, wrote The 85 Ways to Tie a Tie: the Science and Aesthetics of Tie Knots [Fink & Mao 2001], which peaked at #5 in the Amazon mathematics best sellers list of 2005. And if that doesn't tickle your fancy then Burkhard Polster has written the definitive The Shoelace Book: A Mathematical Guide to the best (and Worst) Ways to Lace Your Shoes [Polster 2006] which comes with a pair of shoelaces so that you can do your own experiments.
The moral is: there is fascinating mathematics in so many puzzling everyday situations and much more mathematics out there than anyone ever realised!
Figure 1.1 The Bridges of Königsberg [Rouse Ball 1892: 123]
Figure 1.3 Unicursal by Don Lemon
Figure 1.13 Graph of Tower of Hanoi
2 Four abstract games
Abstract games naturally lead to puzzles and recreations such as Euler's knight tours or the Eight Queens puzzle (Figure 2.1): how can eight chess queens be placed on a chessboard so that no queen attacks another?
Figure 2.1 8 non-attacking queens
This solution looks simple, easy and elegant – but don't be fooled. There are exactly 96 solutions in total, reducing to 12 if solutions which can be rotated or reflected into each other are counted as one, and this is the only symmetrical one.
Conversely, many mathematical recreations can be turned into abstract games simply by adding suitable rules. The best-known example is Golomb's Game, created by Solomon Golomb who named and popularised pentominoes as a recreation.
From Dudeney's puzzle to Golomb's Game
The first ‘pentomino’ puzzle was created by the great English puzzle composer Henry Ernest Dudeney (1857–1930), and published in his book, The Canterbury Tales and other Curious Problems [1907] as problem 74: The Broken Chessboard. He sets it in a lengthy medieval tale about a prince who breaks a chessboard into pieces over the head of his antagonist. The resulting pieces are the 12 pentominoes plus an extra piece 2 by 2 (Figure 2.2).
Figure 2.2 12 pentominoes
Figure 2.3 Solution to Dudeney puzzle
The puzzle was, of course, to reassemble the original chessboard. In Dudeney's solution, Figure 2.3, the extra square piece is on the right-hand edge. Subsequently, puzzles using just the 12 pentominoes occasionally appeared, until in 1954 Solomon Golomb named them pentominoes in an article in Scientific American. He later wrote a book, Polyominoes (1965).
To make the puzzle into a game, Golomb proposed that the players take turns to place one of the 12 pentominoes on the 8 by 8 board, without, of course, overlapping another piece or the edges of the board. The last player to successfully place a piece is the winner.
The best-known abstract games have themselves many mathematical features as we shall now illustrate by looking at four examples, from the simple and extremely ancient Nine Men's Morris to the modern game of Hex, to the ancient game of chess and the even older oriental game of Go.
Nine Men's Morris
Nine Men's Morris, also known as Merelles, Muehle, Molenspel, and Mill, is a very old and simple board game, reminiscent of the children's game of tic-tac-toe or noughts-and-crosses. Boards for what appears to be Merelles have been found scratched on the walls of the Temple of Ramesses at Karnac in Egypt which dates from 1300 BCE, and the game is mentioned in Shakespeare's A Midsummer Night's Dream. It was popular throughout medieval Europe and is also played in China as the game of Yih. As might be expected from such an old game, the rules vary somewhat as does the size of the board and the number of pieces which might be 3 or 6 or 12 rather than 9.
Figure 2.4 Nine Men's Morris
The board starts empty (Figure 2.4) and in the first stage of the game the players take turns to place one piece at a time on a point of the board or move a piece already placed to an adjacent point, along a line, each player attempting to occupy a row of three adjacent points called a mill. When a mill is formed the player is allowed to capture one of his opponent's pieces which is taken off the board and never returns. (Some sets of rules disallow the capture of a piece that forms part of a mill.)
Once all the pieces have been placed on the board, the game changes. A move now consists of moving one of your pieces from one point to an adjacent point still trying to form a mill and capture an opponent's piece. (A move which forms two mills at once,
allows two of the enemy's pieces to be taken off.) At this stage, a player is allowed to move a piece out of a mill and then return on the next move, reforming the mill and making another capturing. The game ends when one player, the loser, has only one or two pieces left.
As abstract games go, it is very simple and in this age of computer power it has been solved completely although there are approximately 1010 legal positions and 1050 possible games. Ralph Gasser proved in October 1993 that with best play the game should be drawn. He also wrote a computer program called Bushy which is now the world's top player.
Nine Men's Morris satisfies all the points we made about puzzles and recreations. It's abstract, the pieces can be anything you like and made of any material or any shape, provided that they are placed and move according to the rules, and you could certainly play it in your head if you had a good enough memory.
To play well you need to ‘calculate’ ahead and it also has an aesthetic quality, though that is a matter of taste like all judgements of beauty, and finally, you have to explore the game, the miniature world of Nine Men's Morris, if you want to become a competent player. It is only by exploring, conjecturing and testing that you will initially discover the features of the game, the best points for your first moves, the best starting sequences, and the best arrangement of pieces.