Games and Mathematics (3 page)

The great Swiss mathematician Leonard Euler was born in 1707 in Basel and published his first paper at the age of 19. From then until his death in St Petersburg in 1783, he wrote a stream of papers on subjects from algebra and calculus to geometry and number theory, to acoustics and music, the theory of lenses, the motion of ships, the atmospheres of the moon and Venus, and many other topics, making him by far the most productive mathematician of all time.

His wonderful memory helped him. He knew Virgil's
Aeniad
by heart and could start ‘reading’ it from memory, given any page number. He could also do complex calculations in his head: when two pupils summed the first 17 terms of a series but couldn't agree on the fiftieth decimal place, Euler corrected them by doing the calculation mentally. Nothing distracted him, not even his 13 children or his blindness in 1771 after a cataract operation failed: he simply dictated his results to an assistant and wrote his papers faster than ever, nearly 900 in all. Thirty years after his death, the Academy in St Petersburg was still publishing his original works.

He gave his name to several Euler theorems, to the Euler equations and the Euler–Lagrange equation, two Euler formulae, the Euler and Eulerian numbers, and the Euler characteristic. His deepest ideas and discoveries had a lasting importance, yet he was also interested in very simple puzzles and pastimes.
Figure 1.1
shows one of them.

The Prussian town of Königsberg lay on the river Pregel which was crossed by seven bridges. The citizens of Königsberg were reputed to enjoy the recreation of starting on one of the banks and then strolling across all seven bridges, once and only once each, to their destination.

Their strolling suggests not just one but several puzzles: is it indeed possible to cross all the bridges exactly once each? If so, can you start wherever you
choose? If bridges were added or deleted, would the puzzle still be solvable? To answer these questions a natural first step is to explore the problem like a scientist by trying different starting points and routes. Which are successful? Which seem impossible? Intriguing!

Euler was intrigued and in 1736 he published a paper answering all these questions. Curiously, he didn't simplify the figure. We will, by focusing on the essential features of the puzzle and ignoring everything else (the process called abstraction). We get
Figure 1.2
.

 

As a result of this
transformation
, the western bank of the Pregel is represented by the single point A, and the south bank by D. The island and the land to the north of it are represented by the points C and B. The seven bridges are the seven lines joining these points. We can now draw the puzzle on a scrap of paper or a restaurant napkin and check possible solutions.

Trial and error correctly suggests that the puzzle cannot be solved, and Euler explained why. His insight, which was original then but might today be spotted by a smart child, was that whenever you visit a point and then leave it, two of
the lines from the point are ‘used up’. Therefore, if the puzzle is to be solved, any point that you visit which is
not
your start or end point must have an even number of lines leaving it. Only your start and end points, if necessary, can be visited by an odd number of lines. It follows that Euler's original problem cannot be solved, since A, B, C and D are all joined by either 3 or 5 lines. Behind the surface appearance not all the meeting points are the same – there is a
hidden significance
in the
odd
vertices.

This explanation also illustrates the amazing sense of conviction we can get from good visual proofs, sometimes called ‘proofs by showing’ or ‘proofs without words’. No complex calculation is needed, no algebra, just looking ‘in the right way’ until the penny drops.

Today this puzzle is called the
Königsberg bridge problem
. Euler's paper was titled
Solutio problematis ad geometriam situs pertinentis
, or in English,
The solution of a problem relating to the geometry of position
. Euler referred to geometry although it has nothing to do with lengths or angles or circles or triangles or even straight lines but then added
of position
because only the
relative position
of the banks of the river and its bridges mattered.

The problem of the Bridge of Königsberg is now considered to be the first ever result in a new branch of mathematics, originally called
analysis situs
or the analysis of situation but now called topology
from the Greek root
topos
= place.

It is indeed a remarkable problem, an everyday puzzle which could have been posed by the citizens of many towns and cities throughout the centuries. It needs no mathematical skill to understand and only a little ingenuity to solve. Euler's paper was his simplest ever. It is also totally abstract like all the purest mathematics. The town of Königsberg, the river Pregel, its banks and bridges are mere distractions which we can strip away to leave the core puzzle. No wonder that endless
analogous
puzzles appeared in later puzzle collections such as this ‘figure tracing’ poser (
Figure 1.3
) from a popular Victorian puzzle book,
Everybody's Illustrated Book of Puzzles
, by Don Lemon [Lemon
1890
: 66].

The reader is instructed: ‘Starting from A, make this figure with one continuous line, without taking the pencil from the paper or going over any line twice, finishing at B.’

Euler knew that the Bridges of Königsberg
was a new kind of problem: he opened his paper by referring to Leibniz who had introduced the term
analysis situs
, without giving any problems involving it:

 

 

We will add that
because
no measurement is needed, merely ‘sight’ of the lines and where they meet, you can solve such
unicursal
puzzles in your head if you have a good visual imagination.

Euler was also interested in another, much older puzzle.
Figure 1.4
shows a part of a chess board and the possible moves of a knight: two squares north, south, east or west and then one square at right-angles.

 

 

The
knight's tour
puzzle is to place the knight on a square of your choice and then to make a
tour
of 63 moves visiting every other square on the chess board. As in the Königsberg puzzle, no square can be visited twice. A harder puzzle is to make 64 moves that will bring you back to your starting square, a
re-entrant
solution. To get an idea of the possibilities and the difficulty of the puzzle and its pleasures, we can try it on smaller boards (
Figures 1.5
and
1.6
).

On the 3 by 3 board, we easily visit 8 squares ending where we started by an elegantly symmetrical route, but we cannot include the central square because it is not a knight's move away from any other.

A little experiment will also suggest that there are no tours on the 4 by 4 board either and we can
prove
this conclusion also though the reasoning is a little more complicated. In the above figure, b can only be reached from a or c. Let's suppose we go to b from a. Then we must move a-b-c and then d, otherwise d can never be reached: but now we are stuck at d. It follows that since we cannot afford to reach b from any other square, we must either start or end there. So our route must go b-a-d-c or b-c-d-a: but then we have the
identical problem with the other pair of corners that cannot now both be visited, and a little more experiment shows that a solution is impossible.

On the 5 by 5 board, however, we can find many routes like the easy solution in
Figure 1.7
which wraps repeatedly round the central square, where the tour ends, or the harder-to-find symmetrical tour in
Figure 1.8
.

These solutions, however, do not end where they start. Must this be so? Yes, and we can prove this conclusion also by a little reasoning. First we colour the board black and white like a real chess board. If the four corner squares are coloured black, we will see that in every solution we have to start and end on a black square. Why? Because there are 13 black squares and only 12 white squares and with every knight move you go either from black to white or from white to black. Therefore any sequence which visits them all must go: black – white – black – white – black – white…black, and the last square can never be a knight's move from the first.

The
many solutions on the 5 by 5 board suggest that on even larger boards there will be even more solutions. Indeed, there are, including this early solution by the Muslim chess player, Al Mani, which illustrates the bizarre combination of pattern and idiosyncracy in such solutions (
Figure 1.9
).

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
).

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.

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.