Professor Robin Wilson
In my last lecture I concentrated on just three specific problems -doubling the cube, trisecting the angle and squaring the circle. These problems all dated from Ancient Greece, but it took more than 2000 years to prove that they're unsolvable.
Today, by way of contrast, I shall introduce many mathematical problems, most of them simple to solve. My emphasis is on puzzles, as these formed the basis for much of the mathematics that we study today. Although some mathematics originally arose from practical applications, a great deal seems to have had its origins in the recreational aspects of the subject. But before I show you any puzzles, I have a few observations that have occurred to me, which you'll see exemplified later.
The first is that many mathematical puzzles recur throughout history - often in differing forms. The second observation is that one person's recreational puzzle is often another's piece of serious mathematics. The final one is how important it is to choose a suitable notation, or draw a suitable diagram, when trying to solve a mathematical problem - especially a recreational one.
An example of the recurrence of mathematical puzzles is the wolf, goat and cabbage problem discussed in the 9th century by Alcuin of York, and 1000 years later in a letter from Lewis Carroll as the problem of the fox, goose and bag of corn. The purpose is to transport the items across a river in a boat that can take only one at a time - but at no time can you leave the fox with the goose, or the goose with the corn. A simple solution involves four crossings:
1. Take the goose across, leave it on the opposite bank, and return alone.
2. Take the corn across, leave it there, and return with the goose.
3. Take the fox across, leave it there with the corn, and return alone.
4. Take the goose across - all three are then on the other side.
Another puzzle that reappeared from time to time was Problem 79 of the Egyptian Rhind papyrus (c.1850 BC): add 7 houses, 49 cats, 343 bags of rice, 2401 portions of wheat and 16,807 hekats: this gives a total of 19607 objects. A related problem appears in Fibonacci's Liber Abaci of 1202 AD, where 7 old women are going to Rome, each has 7 mules, each mule carries 7 sacks, each sack contains 7 loaves, each loaf has 7 knives, each knife has 7 sheaths - what is the total number of things? And this in turn became popular in the form of the nursery rhyme As I was going to St Ives, I met a man with 7 wives, etc.
Notice that the purposes of these latter three puzzles are different. The papyrus problem was probably there to give Egyptian scribes practice in adding numbers - in particular, the powers of 7. Fibonacci's purpose was to familiarise his readers with arithmetic in the Hindu-Arabic number system. And the nursery rhyme was probably designed purely for entertainment - with a twist at the end, since only one (myself) was going to St Ives - everyone else was coming back. Thus, the problems in the Rhind papyrus and Fibonacci's book have a serious arithmetical purpose, whereas the nursery rhyme probably doesn't. Indeed, a number of people have found that recreational puzzles provide an excellent vehicle for teaching serious mathematical ideas - Lewis Carroll certainly thought so, when he taught arithmetic to a group of schoolgirls in Oxford in 1856.
The last observation, which will become clear later on, is how important it is to choose a suitable notation, or draw a suitable diagram, when trying to solve a mathematical problem - and recreational puzzles are no exception.
Some historical examples
One of the oldest collections of puzzles is the Greek anthology of around 500 AD. One of the puzzles is well-known, and concerns the age of Diophantus of Alexandria. It is said that he spent 1/6 of his life in childhood, 1/12 in youth, and 1/7 more as a bachelor. Five years after his marriage there was a son who died four years before his father at ½ his father's final age. From this we can work out that Diophantus lived 84 years. A more complicated example comes from Dudeney's celebrated book Amusements in mathematics: the ages of Ann and Mary add to 44 years, and Mary is twice as old as Ann was when Mary was half as old as Ann will be when Ann is three times as old as Mary was when Mary was three times as old as Ann. How old is Mary?
Another problem from the Greek anthology concerns Polyphemus, who has spouts emerging from his eye, mouth and hand. The one from his hand will fill the cistern in 3 days, that from his eye in one day, and that from his mouth in 2/5 days. How long will it take if all three run together?
A similar problem occurs in Fibonacci's Liber Abaci (1202): if a lion eats a sheep in 4 hours, a leopard eats it in 5 hours, and a bear eats it in 6 hours, how long would they all take together. Here the trick is to turn the problem around and note that in one hour, the lion eats ¼ sheep, while the leopard eats 1/5 sheep and the bear eats 1/6 sheep, so together they can eat a total of 37/60 sheep. Thus, the total number of hours needed to finish off the sheep is 60/37, or 123/37 hours.
Fibonacci's book was full of examples designed to introduce the Hindu-Arabic numerals. Its most famous example is that of the rabbits: how many pairs of rabbits can be bred from one pair in a year, if each month they produce another pair, and in their second month each pair starts to breed? The answer leads to the so-called Fibonacci sequence, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, in which each successive term is the sum of the previous two.
My final problem from the Liber Abaci is a problem that seems to have too little information: if I buy 3 sparrows for a penny, 2 turtle-doves for a penny, and doves for two pence each, and if I spend 30 pence on 30 birds, how many of each do I buy. The answer relies on the fact that all three answers must be whole numbers.
Moving on to some arithmetical puzzles, we first note a method for multiplying two numbers - sometimes called Russian or Egyptian multiplication. If we want to multiply 23 × 89, we successively double the 89 (giving 178, 356, 712 and 1424) while halving the 23 (giving 11, 5, 2 and 1): whenever we get a remainder we just throw that row away. We then remove any row in the 23 column that starts with an even number (here, the row with 2 and 712). Adding the rest, gives us the answer: 89 + 178 + 356 + 1424 = 2047.
A well-known puzzle is the 1089 trick. Think up any three-digit number in which the first and last digits differ by two or more (for example, 683). Reverse it and take the smaller number form the larger (683 - 386 = 297). Reverse the answer and add (297 + 792 = 1089). We always get 1089 - whatever number we started with - for reasons that I'll leave you to discover. Lewis Carroll apparently invented the pounds, shillings and pence version of the puzzle, in which the 'magic total' is £12 18s 11d.
Talking of pre-decimal money, an ingenious puzzle of Lewis Carroll concerned a customer who wished to buy goods in a shop costing 7/3d. The only money he had was a half-sovereign (10/-), a florin (2/-) and a sixpence (6d), so he wanted change. The shopman had only a crown (5/-), a shilling (1/-) and a penny (1d). But a friend happened to come in, who had a double-florin (4/-), a half-crown (2/6d), a fourpenny bit (4d) and a threepenny bit (3d). By pooling all their money, they were able to extract 7/3d from the customer and give it to the shopman.
And here's a simple problem involving speeds. If I travel from Oxford top Cambridge at 40 mph, and travel back at 60 mph, what's my average speed over the double journey? 'Obviously' 50 miles per hour? - but it's not, as we'll now see. If the one-way distance is d, then to time taken to get to Cambridge is d/40 and the time taken to return is d/60. Thus the average speed, which is total distance over total time, is obtained from dividing 2d by d/40 +d/60. This all simplifies to an average speed of 48 mph.
Lewis Carroll also worked on logical syllogisms. What can we deduce from the following statements? (1) Babies are illogical; (2) Nobody is despised who can manage a crocodile; (3) Illogical persons are despised. Statements (1) and (3) tell us that Babies are despised, and we deduce from (2) that Babies cannot manage crocodiles. Carroll has similar examples extending up to 50 statements.
Here's another type of logical problem. Suppose that Pamela Potter's pease pottage is putrid provided that Pablo Picasso painted potted palms. Also, either Pablo Picasso painted potted palms, or Peter Piper did not pick a peck of pickled peppers. Also, there are two possibilities: either Peter Piper picked a peck of pickled peppers or else it is impossible that both Pablo Picasso did not paint potted palms and that Pamela Potter's porridge is putrid. The question is: Is Pamela's porridge putrid? The answer shows the importance of choosing convenient notation. If we let p= Pamela's porridge is putrid, q = Picasso painted potted palms, and r =Peter Piper picked a peck of pickled pepper, then (1) q → p; (2) q or (~r); (3) r or ~ [(~q) & (~p)]. If, now, p is false, then by (1), q is false; by (2), r is false; and (3) is then contradictory. So p is true: Pamela's porridge is putrid.
Magic and Latin squares
There is an ancient Chinese legend about the Emperor Yu standing on the banks of the river Lo (a tributary of the Yellow river), when a tortoise emerged from the river with a pattern of numbers on its back - in fact, a 3 × 3 magic square, in which the sum of the numbers in each row, each column, and the two diagonals, are all the same: 4 + 9 + 2 = 15, 2 + 5 + 8 = 15, and so on. Over the centuries this particular pattern of numbers came to acquire great religious and mystic significance, and appeared in many different forms, as you can see.
Most of the early work in this area was done by Chinese and Islamic scholars, who devised magic squares with all sorts of extra properties. For example, an ingenious magic square of Yang Hui (1275) is a 9 × 9 magic square that splits into nine smaller 3 × 3 magic squares.
Even cleverer is an earlier Islamic one by al-Antaakii (10th century). It's a 15 × 15 magic square, containing within it smaller magic squares of side 13, 11, 9, 7, 5 and 3 - and moreover, the numbers are arranged so that all the odd numbers appear inside a central diamond and all the even ones appear outside.
But my favourite magic square is a 16 × 16 one, constructed by Benjamin Franklin. Every row, column and diagonal add up to 2056, and the numbers are so arranged that the half-rows, half-columns and half-diagonals add up to 2056/2 = 1028. We also get 1028 if we add up the four corners and the four middle squares. But the remarkable thing is that is if we take any 4 × 4 square inside this magic square, the numbers still add up to 2056.
Moving now to Latin squares, in a 1725 book on recreational mathematics, Jacques Ozanam showed how to lay out the sixteen court cards in a pack so that each row and column contains each suit and each value, J, Q, K, A. It's also possible to do a similar thing with 25 cards - five suits and five values. But what about 36?
The year before he died, in a paper mainly on magic squares, Euler posed this as the 36 officers problem: arrange 36 officers, one each of 6 ranks from 6 regiments, in a square so that each row or column has one officer of each rank and one officer of each regiment. Euler believed that the answer is no - which was eventually confirmed around 1900 by Gaston Tarry, essentially by enumerating all the possibilities. Euler also claimed that the problem always has a solution, except when the number of ranks or regiments is 2 more than a multiple of 4: that is, 6, 10, 14, 18, and so on. He was right about 6. He was wrong about all the others, although this wasn't proved until around 1960, almost 300 years later.
Latin squares are currently enjoyed under the heading of sudoku, and there are now many sudoku-type puzzles, all of which are related to topics in combinatorial mathematics.
Here are some tilings that I've come across in my travels - two of them are from pavements and the third is from a kitchen floor, and so are presumably of concern to their designers. But the study of tilings forms a fascinating area of geometry in its own right - one with links to art. Most fascinating is this tiling which formed the floor pattern in my apartment in Colorado a few years ago; note the clever arrangement of squares, pentagons, hexagons, heptagons and octagons - not quite regular, but very nearly so.
It has been known since Greek times, or even earlier, that there are three types of regular tilings - made of equilateral triangles, squares, and regular hexagons. In a note 'on the sagacity of bees' Pappus (300 AD) considered these and deduced that bees were very sensible in choosing the hexagonal one, which holds most honey. The next task is to classify semi-regular tilings, with more than one type of regular polygon - there are just eight of these.
Graph theory / further reading
The final topic of the lecture was graph theory: the 6 people at a party problem, the Königsburg bridges problem, the tracing of mazes, the gas, water and electricity problem, the bracing of frameworks, and the 'instant insanity' puzzle. Since these all involve many diagrams we omit them here - they can be found in J. Aldous and R. J. Wilson: Graphs and applications: an introductory approach, Springer, 2000.
Other books involving recreational mathematics are H. E. Dudeney'sAmusements in mathematics (1917), B. Averbach and O. Chein's excellent Problem solving through recreational mathematics, Dover, 2000, and the many books of Martin Gardner. Many of Lewis Carroll's puzzles can be found in Martin Gardner's The universe in a handkerchief, Springer, 1996, two Dover books by Edward Wakeling, and my forthcoming book Lewis Carroll in Numberland, Penguin, 2008.
©Professor Robin Wilson, Gresham College, 6 February 2008