Ian Stewart
Page 7
Now nothing happens for 99 rings, and then all 100 monks simultaneously raise their hands after the 100th ring.
Why? Monk number 100, say, can see that the other 99 all have blobs. ‘If I do not have a blob,’ he thinks, ‘then the other 99 all know this. That takes me out of the reckoning altogether. So they are making whatever series of deductions you get with 99 monks when I don’t have a blob. If I’ve sorted out the 99-monk logic right, then after 99 rings they will all put up their hands.’ He waits for ring 99, and nothing happens. ‘Ah, so my assumption is wrong, and I must have a blob.’ Ring 100, up goes his hand. Ditto for the other 99 monks.
Ah, yes . . . but maybe monk 100 was wrong about the 99-monk logic. Then it all falls apart. However, the 99-monk logic (with the hypothetical assumption that monk 100 is blobless) is the same. Now monk 99 expects the other 98 to put up their hands at the 98th ring, unless monk 99 has a blob. And so it goes, recursively, until we finally get down to a single hypothetical monk. He sees no blobs anywhere, is startled to discover that somebody has one, immediately deduces it must be him (you don’t need to be an expert logician at that stage) and puts his hand up after the first ring.
Since his 1-monk logic is correct, so is the 2-monk logic, then the 3-monk . . . all the way to the 100-monk logic. So this puzzle is a striking example of the Principle of Mathematical Induction. This says that if some property of whole numbers holds for the number 1, and if its validity for any given number implies its validity for the next number, no matter what those numbers may be, then it must be valid for all numbers.
That’s the usual story, but there’s more. So far I’ve assumed that every monk has a blob. However, very similar reasoning shows that this requirement is not essential. Suppose, for example, that 76 monks out of a total of 100 have blobs. Then, if everyone is logical, nothing happens until just after the 76th ring, when all the monks with blobs put up their hands simultaneously, but none of the others.
At first sight, it’s hard to see how they can work this out. The trick lies in the synchronisation of their deductions by the bell, and the application of common kowledge. Try two or three monks first, with different numbers of blobs, or cheat by peeking at the answers on page 291.
Pickled Onion Puzzle
Three weary travellers came to an inn, late in the evening, and asked the landlord to prepare some food.
‘All I got is pickled onions,’ he muttered.
The travellers replied that pickled onions would be fine, thank you very much, since the alternative was no food at all. The landlord disappeared and eventually came back with a jar of pickled onions. By then, all the travellers had fallen asleep, so he put the jar on the table and went off to bed, leaving his guests to sort themselves out.
The first traveller awoke. Not wishing to make a pig of himself, and not knowing what anyone else had already eaten, he took the lid off the jar, threw away an onion that looked bad, ate one-third of the onions that remained, put the lid back on the jar, and went back to sleep.
The second traveller awoke. Not wishing to make a pig of himself, and not knowing what anyone else had already eaten, he took the lid off the jar, threw away two onions that looked bad, ate one-third of the onions that remained, put the lid back on the jar, and went back to sleep.
The third traveller awoke. Not wishing to make a pig of himself, and not knowing what anyone else had already eaten, he took the lid off the jar, threw away three onions that looked bad, ate one-third of the onions that remained, put the lid back on the jar, and went back to sleep.
At this point the landlord returned and removed the jar, which now contained six pickled onions.
How many were there to start with?
Answer on page 292
Guess the Card
The Great Whodunni has an endless supply of mathematical card tricks. This one allows him to identify a specific card, chosen from 27 cards taken from a standard pack.
Whodunni shuffles the 27 cards, and lays them out in a fan so that his victim can see all of them.
‘Choose one card, mentally, and remember it,’ he tells him. ‘Turn your back, write down the card, and seal it in this envelope, so that we can verify your choice at the end.’
Now Whodunni deals out the 27 cards, face up, into three piles of 9 cards each, and asks the victim to say which pile the chosen card is in.
He picks up the piles, stacks them together without shuffling, then deals them into three piles and asks for the same information.
Finally, he picks up the piles, stacks them together without shuffling, then deals them into three piles and asks for the same information for a third time.
Then he picks out the chosen card.
How does the trick work?
Answer on page 293
And Now with a Complete Pack
Whodunni can do even better. In just two deals, he can correctly identify a card chosen from the full 52-card pack.
First, he deals the cards in 13 rows of 4 cards, and asks which row the card is in.
Then he reassembles the cards into the same order, deals them into 4 rows of 13 cards, and again asks which row the card is in.
After which he unerringly names the chosen card.
How does this trick work?
Answer on page 293
Halloween = Christmas
Why do mathematicians always confuse Halloween and Christmas?
Answer on page 293
Egyptian Fractions
Whole numbers are fine for addition and multiplication, but subtraction causes problems because, for instance, 6 - 7 doesn’t work with positive whole numbers. This is why negative numbers were invented. A positive or negative whole number is called an integer.
In the same way, the problem of dividing one number by another, such as 6 ÷ 7,18 requires the invention of fractions like . The number on the top (here 6) is the numerator, the one on the bottom (here 7) is the denominator.
Historically, different cultures handled fractions in different ways. The ancient Egyptians had a very unusual approach to fractions; in fact, they had three unusual approaches.
First, they had special hieroglyphs for and
Hieroglyphs for and
Second, they used various portions of the Eye of Horus, or Wadjet Eye, to represent 1 divided by the first six powers of 2.
Wadjet Eye (left), and fraction hieroglyphs derived from it (right).
Finally, they devised symbols for fractions of the form ‘one over something’, that is, , , , , and so on. Today we call these unit fractions. The unit fraction 1/n was represented by placing a cushion-shaped hieroglyph (normally representing the letter R) over the top of the symbols for n.
Hieroglyphs for 1/1,237
(in practice the Egyptians wouldn’t have used such big numbers in a unit fraction).
However, these methods dealt only with special types of fractions, and 6 divided by 7 was still a problem. So the Egyptians expressed all other fractions as sums of distinct unit fractions, for instance
and
It’s not at all clear why they didn’t like to write as + , but they didn’t.
Doing arithmetic with unit fractions is weird, but possible. Our method is very different: we ‘put both fractions over a common denominator’ (page 310) like this:
We can see that the result is roughly 1, which isn’t obvious from the Egyptian fractions.
Nevertheless, the Egyptians did amazing things with their symbolism. Our most important source for their work is the Rhind mathematical papyrus, now in the British Museum. Alexander Rhind bought the papyrus in 1858 in Luxor; it seems to have been unearthed by unauthorised excavations near the Ramesseum.
Part of the Rhind mathematical papyrus.
The papyrus dates to around 1650 BC, in the Second Intermediate Period. The scribe Ahmose copied it from an earlier text from the time of the 12th dynasty pharaoh Amenemhat III, two centuries earlier, but the original text is lost. It measures 33 cm by 5 m, and even now scholars do not und
erstand everything on it. However, one remarkable section, about one-third of one side, deals with unit-fraction representations of numbers of the form 2/n, where n is odd and runs from 3 to 101.
Ahmose’s results here can be summed up in a table. To simplify the printing and improve legibility, an entry like
means that
The table is impressive, but also raises a number of questions. How did whoever first found these representations discover them? Why did the scribes prefer these particular representations?
Expressing 2/n, for n odd, as a sum of at most four unit fractions.
In 1967, at the request of Richard Gillings, C. L. Hamblin programmed an early electronic computer belonging to Sydney University to list all possible ways to represent the fractions 2/n in Ahmose’s table as sums of unit fractions. The results led Gillings to argue that:
• the Egyptians preferred small numbers;
• they preferred sums with two unit fractions to those with three, and sums with three unit fractions to those with four;
• usually they liked the first number to be as small as possible, but not when that made the last number too big;
• they preferred even numbers, even when this led to bigger numbers or more of them.
For example, the computer found that
but both numbers are odd and 703 is large. The scribes preferred
with two even numbers and nothing very big. Gillings gives an extensive discussion in his Mathematics in the Time of the Pharaohs. This book is a bit long in the tooth, and the historical study of Egyptian mathematics has moved on, but it still has a lot of interesting things to say.
The Greedy Algorithm
Egyptian fractions are obsolete for practical arithmetic, but still very much alive as mathematics, and you can learn a lot about modern fractions by thinking about Egyptian ones. For a start, it’s not obvious that every fraction less than one has an ‘Egyptian representation’ - as a sum of distinct unit fractions - but it’s true. Leonardo of Pisa, the famous ‘Fibonacci’ (Cabinet, page 98), proved this in 1202, showing that what is nowadays called the ‘greedy algorithm’ always does the job. An algorithm is a specific method of calculation that always produces an answer, like a computer program.
The greedy algorithm begins by finding the largest unit fraction that is less than or equal to the fraction you want to represent - that’s what makes it greedy. Subtract this fraction from the original fraction. Now repeat, looking for the largest unit fraction that is different from the one you got the first time, but less than what’s left. Keep going.
Amazingly, this method eventually reaches a unit fraction and stops.
Let’s try out the greedy algorithm on the fraction
• Find the biggest unit fraction that is less than or equal to This is
• Find the difference
• Find the biggest unit fraction different from that is less than or equal to This is
• Find the difference:
• Find the biggest unit fraction different from and that is less than or equal to This is itself, so the algorithm stops.
Putting the pieces together, we have
which is the required Egyptian representation.
The greedy algorithm doesn’t always give the simplest Egyptian representation. For instance, when applied to it produces
and fails to spot a simpler answer:
The Erdős-Straus conjecture states that every fraction of the form 4/n has a unit fraction representation with three terms:
It is true for all n < 1014. Exceptions, if they exist, must be very thin on the ground, but no proof or disproof exists.
There are also some interesting variations on the greedy algorithm that you can try. I suggest using fractions with small numerators and denominators to avoid monsters like the one we’ve just seen. First, try it with the extra condition that every fraction involved must be one over an even number. Surprisingly, the greedy algorithm still works - it has been proved that every fraction less than one is a sum of unit fractions with distinct even denominators.
Now try it with odd denominators. Computer experiments suggest that it also works in this case. For instance,
But now nobody has a proof. For all we know there might be some peculiar fraction for which the odd-denominator greedy algorithm goes on for ever.
Now that’s really greedy.
We have only scratched the surface of the mathematics of Egyptian fractions. For more, see: en.wikipedia.org/wiki/Egyptian_fraction
How to Move a Table
William Feller.
William Feller was a probability theorist at Princeton University. One day he and his wife wanted to move a large table from one room of their house to another, but, try as they might, they couldn’t get it through the door. They pushed and pulled and tipped the table on its side and generally tried everything they could, but it just wouldn’t go.
Eventually, Feller went back to his desk and worked out a mathematical proof that the table would never be able to pass through the door.
While he was doing this, his wife got the table through the door.
Rectangling the Square
Form five rectangles by choosing their sides from the list 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, with each number being chosen exactly once. Then assemble the rectangles, without overlaps, to form an 11×11 square.
Answer on page 293
Newton, by Byron
When Newton saw an apple fall, he found
A mode of proving that the earth turn’d round
In a most natural whirl, called gravitation;
And this is the sole mortal who could grapple
Since Adam, with a fall or with an apple.
Isaac Newton
George Gordon Byron.
X Marks the Spot
‘Shiver me timbers and brace the mainsplice!’ declared Roger Redbeard, the pirate captain. ‘What have we here, me hearties? Methinks it be a treasure map, aaargh, for plainly I sees an X.’
Here be treasure me hearties, aaargh!
‘I knows that island,’ said the bosun. ‘It be where we marooned that lily-livered swine Admiral Ponsonby-Ffynche and his crew, when we seized the Vainglorious. Dead Man’s Key, it were. Not a drop o’ water on the island, may their bones whiten in the merciless sun.’
‘Set sail for Dead Man’s Key!’ ordered Redbeard. As the crew hoisted the mains’l, he looked round to make sure no one was watching, and turned the map over. On the back, in letters of blood, were instructions to locate the loot:
Four stone markers form a great square, 140 nautical
perches to a side.
From the markers at Abandon Hope Point, Buccaneer Bay
and Cutlass Hill, measure exact whole numbers of
nautical perches to the spot marked X.
From Abandon Ho—
From Buccaneer Bay: 99 naut—
From the marker nearest the treasure, Cutl—
The rest was torn away.
Roger cursed a foul pirate curse, for he was a foul pirate and knew how to curse the sort of curse that foul pirates curse. ‘I swear,’ he swore, ‘I’ll dig up the entire island if I have to, aaargh!’ For he knew that pirates never placed their X’s on maps in the correct location, as that would make it too easy for others to discover their hoard.
‘If only I’d paid more attention to my maths teacher at school,’ Roger sighed. ‘For then, by Beelzebub’s flaming breeches, I’d know how far X must be from the markers.’19
What are the three distances?
[Hint: This is hard. You may find it helpful to know that if 7 divides a sum of two integer squares, u2 + v2, then 7 divides each of u and v. Then again ... ]
Answer on page 294
Whatever’s the Antimatter?
Harold P. Furth was an Austrian-born American physicist who worked on nuclear fusion and related topics. In 2001, he wrote a short poem, ‘Perils of Modern Living’, which begins:
Well up above the tropostrata
Where, on a streak of anti-matter
Lived Dr Edward Anti-Teller.
Edward Teller was a co-inventor of the hydrogen bomb, acquired huge political influence, and was the inspiration behind the Dr Strangelove character in the movie of the same name. The poem goes on to relate that one day a visitor from Earth turned up, and human and antihuman approached each other:
. . . their right hands
Clasped, and the rest was gamma rays.
Anyone brought up on Star Trek is aware that antimatter is a kind of ‘mirror image’ of ordinary matter, and when the two are brought into contact they annihilate each other in a gigantic burst of photons (‘gamma rays’), particles of light. The combined mass of the two types of matter is released as energy. Thanks to Einstein’s famous formula E = mc2, a small mass m turns into a huge amount of energy E, because the speed of light c is very big, so c2 is even bigger.