Ignoring the context, though, most mathematicians would beg to differ with President Lincoln, and answer ‘five’. Renaming a tail as a leg amounts to a temporary redefinition of terminology, which is common in mathematics. For example, in algebra ‘the’ unknown is usually denoted x, but the value of x differs from one problem to the next. If x was 17 in last week’s homework it need not be 17 ever after. The usual convention is that a temporary redefinition remains in force until it is explicitly cancelled, or until the context makes clear that it has been cancelled.
In fact, mathematicians habitually go further, and permanently redefine important terminology, usually to make it more general. Concepts such as number, geometry, space and dimension are examples; their meaning has changed repeatedly as the subject has progressed.
So, to mathematicians, if we agree to call a tail a leg for the rest of the discussion - which Lincoln’s question tacitly assumes, otherwise it’s not worth asking - then the meaning of ‘leg’ has changed, and now includes tails. So, Mr President, the dog has five legs, by your own redefinition.
What happens to Lincoln’s political point? It remains intact, but for a different reason. When Lincoln’s opponent asserted that slavery is protection, he redefined protection for the remainder of the discussion, so the properties normally associated with protection might not apply any longer. In particular, the new meaning does not imply that slavery is an act of kindness.
Whodunni’s Dice
The dice were 5, 1 and 3.
If the dice show the numbers a, b and c, then the calculation produces in turn the numbers
2a + 5
5(2a + 5) + b = 10a + b + 25
10(10a + b + 25) + c = 100a + 10b + c + 250
So Whodunni subtracted 250 from 763, to get 513 - the numbers on the three dice. Subtract 2 from the first digit of the answer, 5 from the second, and leave the third alone - easy.
The Bellows Conjecture
Heron’s formula applies to a triangle with sides a, b, c, and area x. Let s be half the perimeter:
Then Heron proved that
Square this equation and rearrange to get
16x2 + a4 + b4 + c4 - 2a2b2 - 2a2c2 - 2b2c2 = 0
This is a polynomial equation relating the area x to the three sides a, b, c.
Digital Cubes
The other 3-digit numbers that are equal to the sum of the cubes of their digits are 370, 371, and 407.
If the digits are a, b, c, then we have to solve
100a + 10b + c = a3 + b3 + c3
with 0 ≤ a, b, c ≤ 9 and a > 0. That’s 900 possibilities, so a systematic search will find the answer.
The work can be reduced by using some fairly simple tricks. For instance, if you divide a perfect cube by 9, the remainder is 0, 1 or 8. If you divide 100 or 10 by 9, the remainder is 1. So a + b + c and a3 + b3 + c3 leave the same remainder on division by 9. Eliminating cases where the digits are too small or too big to work, a + b + c has to be one of 7, 8, 9, 10, 11, 16, 17, 18, 19, 20. After that ... well, you get the idea. It’s a bit of a scramble, but it can be pushed through. Maybe there’s a better way.
Order into Chaos
There are plenty of solutions (usually there are lots, or none). Here’s one for each puzzle:
• SHIP-SHOP-SHOT-SOOT-ROOT-ROOK-ROCK-DOCK
• ORDER-OLDER-ELDER-EIDER-CIDER-CODER-CODES-CORES- SORES-SORTS-SOOTS-SPOTS-SHOTS-SHOPS-SHIPS-CHIPS- CHAPS-CHAOS
If you’re worried about EIDER and SOOTS, the first is a kind of duck and the second is not the plural of ‘soot’ (which is ‘soot’) but derives from the verb ‘to soot’, which means to cover with soot. As in the lesser-known proverb ‘A clumsy chimney-sweep soots the hearth.’54 Both words are in the official ScrabbleTM dictionary.
Now, I promised some maths, and we’ve not seen any yet.
All these puzzles are really about networks (also called graphs), which are collections of dots joined by lines. The dots represent objects, and the lines are connections between these. In the SHIP- DOCK puzzle, the objects are four-letter words, and two words are connected if they differ by just one letter (in a specific position). All four-letter word puzzles of this kind reduce to the same general question: Is the initial word connected to the final one by some path in the network of all possible four-letter words?
Connect SHIP to DOCK.
The diagram shows just a tiny part of this network - enough to find an answer.
There are computer algorithms (procedures) for finding paths between any two nodes of a network, and the mathematics quickly becomes fairly deep and difficult. One relatively simple point is that the whole network breaks up in to one or more components, and all the words in a component are connected to each other by paths. Once you have succeeded in joining a word to one of these components, you can easily join it to all the other words in that component.
How many components are there? A theorem proved by Paul Erdős and Alfred Rényi in 1960 implies that if on average each word connects to enough others - more than some critical amount - then we should expect to find one giant component containing almost all the words, and a scattering of much smaller ones. And this is what happens. The giant component usually misses some bits out - for instance, if we can find an isolated word, one that has no immediate neighbours, then that word on its own would form one component, disconnected from everything else.
What about an obscure word like SCRY (meaning to crystal-gaze)? Is that isolated? No, SCRY connects to SPRY, then to SPAY, then SPAR, SPAN, ... and it has clearly ‘escaped’, with lots of potential links, so we expect it to join up to the giant component, even though my picture doesn’t show how. In fact, SPAY-SPAT- SPOT-SHOT will do. This is why there is probably only one giant component. Since it’s so big, anything that is linked by a path to a reasonable number of words has more and more potential links, and at some point the path will run into the giant component.
Ted Johnson analysed the network of four-letter words, with one slight change to the definition of a link: you are also allowed to reverse the word. This probably does not change the components significantly, if at all, because relatively few words are meaningful when reversed.
He obtained his list of four-letter words from an online dictionary, resulting in a total of 4,776. Using mathematical methods (the Graph module for the computer scripting language Perl) he found that some words are isolated (like HYMN, according to the Scrabble dictionary) or form isolated pairs. Another small component contains just eight words. That left 4,439 words: one giant component with 4,436 words, and a small one with three - TYUM, TIUM, TUUM. These are not in the Scrabble Dictionary, but tuum is a literary word for ‘yours’, from the Latin, as in ‘meum and tuum’ - mine and yours. I’m inclined to rule out the other two and count tuum as a single isolated word. His results can be found at: users.rcn.com/ted.johnson/fourletter.htm
If you play around with the network, you start to notice some regular structural features. The group of words BAND, BEND, BIND, BOND is an example: they are all connected to each other. That’s because all the changes involve the same letter position, the second from the left. Biologists working on genetic networks call common small sub-networks motifs. There are five-word motifs like this, too: MARE, MERE, MIRE, MORE, MURE is one example.
A more significant motif in the word network is a series of three words like SHOT-SOOT-SORT with two vowels in the middle word. Vowels are crucial. Most single-letter changes to words change a consonant to another consonant or a vowel to another vowel. If all changes were like that, the vowel positions could never move. So changing SHIP, with a vowel in position 3, to DOCK, with a vowel in position 2, would be impossible. But sometimes consonants can change to vowels, or vowels to consonants. A sequence like SHOT- SOOT-SORT in effect moves the location of the vowel, by introducing another one and then losing the first.
In going from ORDER to CHAOS, the biggest problem is moving the vowel positions around. That’s where EIDER and SOOTS come in, in fact. But notice that although bot
h the start and end words have a vowel in position 4, some of the intermediate words don’t. Sometimes you have to take a detour to get where you want to go.
Provided we take a relaxed view of what constitutes a vowel, every English word contains one. The standard vowels are AEIOU, of course. But the Y in SPRY acts like a vowel, for instance, and Y is often included in the list of vowels. The same goes for the W in the Welsh word CWM (which comes into the 4-letter network if we use the plural CWMS). If we define vowels that way, or exclude words without vowels, then the Ship-Dock theorem holds. This states that when going from SHIP to DOCK, some intermediate word must contain two vowels.
Why? At each stage the number of vowels can change by at most 1, and if it does not change, then the vowel stays in the same position. If the vowel count was always 1, then the vowel in SHIP would have to stay in the third position - but the vowel in DOCK is in the second position. So the vowel count must change. Look at the first word where it changes. It starts at 1 and changes by 1, leading to either 2 or 0. But 0 is ruled out by our convention about what constitutes a vowel or a permissible word, so it must be 2. The same theorem holds for words of any length. If the initial word has a vowel where the final one has a consonant, or vice versa, then somewhere we must hit two or more vowels. Why more? Because of examples like ARISE-AROSE, where the start and end words have more than two vowels.
The Hairy Ball Theorem
Yes, a hairy ball can be combed so that it is smooth at every point except one. The idea is to move the two tufts in the picture together until they coincide.
Extend the loops smoothly over the back.
Cups and Downs
Cups Puzzle 1
This one is impossible, and again the proof is parity. We start with an even number of upright cups (zero) and end with an odd number (11). But we are inverting an even number of cups each time, and that implies that the parity cannot change.
Cups Puzzle 2
This time there is a solution, and the shortest takes four moves.
Inverting 12 cups, 5 at a time.
There’s a general version using n cups, initially all upside down, where each move inverts precisely m cups. Parity rules out any solutions when n is odd and m is even. In all other cases, solutions exist. Man-Keung Siu and I proved that the shortest solution depends in a surprisingly complicated way on m and n, and there are six different cases. For the record, the answers are:
n even, m even, 2m ≤ n : ┌n/m┐
n even, m even, 2m > n : 1 if m = n, 3 if m < n
n even, m odd, 2m ≤ n : 2┌n/2m┐
n even, m odd, 2m > n : 2┌n/2(n - m)┐
n odd, m odd, 2m ≤ n : 2┌(n - m)/2m┐ + 1
n odd, m odd, 2m > n : 1 if m = n, 3 if m < n
Here ┌x┐ is the ceiling function: the smallest integer greater than or equal to x.
Secret Codes That Can Be Made Public
The general procedure for the RSA cryptosystem goes like this:
• Choose, once and for all, two prime numbers p and q. They should be really large, say 100 or even 200 digits each. Work out their product pq.
• Choose an integer e (for encode) between 1 and (p - 1)(q - 1) which is not a multiple of p or q.
• Now Alice, who is sending the message N to Bob, does this:
• Encode the message N as Ne (mod pq).
• Transmit the message.
At this point, even Alice does not know how to decode a message. She knows what she sent, of course. Thanks to Euler, and some preliminary calculations when the code was set up, Bob knows a crucial fact that Alice doesn’t:
• There is a unique integer d (for decode) in the same range, for which
de ≡ 1(mod(p - 1)(q - 1))
and Bob knows what d is. Now he can decode Alice’s message Ne (mod pq) by raising it to the power d:
• Form (Ne)d (mod pq)
Euler’s theorem tells us that
(Ne)d≡ Ned≡ N(mod pq)
so Bob has recovered the message N.
As a practical matter, it is relatively straightforward to choose p and q, work out pq, and then let Alice know what pq is - and what the encoding power e is. However, if everyone now forgot what p and q were, it would be impossible to work them out again! So, with the big primes actually employed, Alice can’t deduce them from their product. Neither can anyone else who is not privy to the secret information that Bob knows.
Calendar Magic
The numbers always have this pattern.
If the smallest number is x, then the numbers in the 3×3 square are x, x + 1, x + 2, x + 7, x + 8, x + 9, x + 14, x + 15, x + 16. These add up to 9x + 72 = 9(x + 8). The volunteer tells Whodunni what x is. So all Whodunni has to do is add 8 and then multiply by 9. A quick way to multiply a number by 9 is to put 0 on the end and then subtract the number.
When the chosen number is 11, Whodunni adds 8 to get 19, and then works out 190 - 19 = 171.
The Rule of Eleven
The largest such number is 9,876,524,130. The smallest is 1,024,375,869 (remember, don’t start with 0).
How do we find these? Bearing the test in mind, we have to split the digits 0-9 into two distinct sets of five, so that the sums of these two sets differ by a multiple of 11. In fact, we can prove that the difference must be 11 or -11, like this. Let the sums concerned be a and b. Then a - b is some multiple of 11. But a + b is the sum of all digits 0-9, which is 45. Now, a - b = (a + b) - 2b = 45 - 2b. Since 45 is odd, and 2b is even, a - b has to be odd. So it might be any of the numbers 11, 33, 55, ... or their negatives -11, -33, -55, . . . . However, both a and b lie between 0 + 1 + 2 + 3 + 4 = 10 and 9 + 8 + 7 + 6 + 5 = 35. So their difference lies between -25 and 25. That cuts the possibilities down to -11 and 11.
Now we can solve the equations a - b = 11, a + b = 45 (or a - b = -11, a + b = 45) for a and b. The result is that a = 28, b = 17, or a = 17, b = 28. So it remains to find all possible ways to write 17 as a sum of five distinct digits. We can make a systematic search, bearing in mind that the digits concerned can’t be very big. For instance, 2 + 3 + 4 + 5 + 6 = 20 is already too big, so the smallest digit must be 0 or 1, and so on. The upshot is that one set of five digits must be one of:
01259, 01268, 01349, 01358, 01367, 01457,
02348, 02357, 02456, 12347, 12356
The other set of five must be whatever these miss out, namely:
34678, 34579, 25678, 24679, 24589, 23689
15679, 14689, 13789, 05689, 04789
respectively.
To get the largest multiple of 11 using all ten digits, we must interleave the two sets, keeping all digits as big as possible starting from the left-hand end. We can make a good start with 98765 using the pairs 34579 and 01268 (and only those), where I’ve used boldface and underlines to show which digit comes from which set. Continuing using the largest available possibilities (the so-called greedy algorithm) we get 9876524130.
The smallest number is slightly harder to find. We can’t start with 0, so 1 is the next best bet. This should be followed by 0, if possible, then 2, 3, and so on. If we try to start 10234 we’re stuck, because the only set listed that contains 1, 2 and 4 is 12347, but this also has the 3, which ought to be in the other set. In fact, starting 1023 won’t work because anything containing 12 also contains 0 or 3, but those have to be in the other set. So the next smallest possibility is to start 1024, and the smallest of all would start 10243. That forces one set to be 12356 and the other 04789. Interleaving these digits in order we get 1024375869 as the smallest possibility.
The smallest multiple of 11 where the difference a-b is not zero is 209. If you try the first few multiples of 11, such as 11, 22, 33, and so on, then a-b is obviously 0 up to at least 99, since a = b. The next multiple, 110, also has a = b, and so do 121, 132, 143, 154, 165, 176, 187, 198. But 209 has a = 11, b = 0, so this is the smallest case.
Digital Multiplication
Common Knowledge
With three monks, all bearing blobs, the reasoning is as follows.
Aelfred thinks: If I don’t have a blob, then Benedict sees a blob on Cyril but nothing on me. Then he will ask himself whether he has a blob. And what he will think is: ‘If I, Benedict, do not have a blob, then Cyril sees that neither Aelfred nor I has a blob, so he will quickly deduce that he has a blob. But Cyril, an excellent logician, remains unembarrassed. Therefore I must have a blob.’
Now Aelfred reasons: ‘Since Benedict is also an excellent logician, and has had plenty of time to work this out but remains unembarrassed, then I, Aelfred, must have a blob.’ At this point, Aelfred turns crimson - as do Benedict and Cyril, who have followed similar lines of reasoning.
Now suppose, say, that there are only two monks, of whom only Benedict has a blob. When the Abbot makes his announcement, Benedict sees that Aelfred has no blob, deduces that he must have one, and at the first ring of the bell, puts up his hand. Aelfred does not, because at that stage he’s not yet sure of his own blob status.
Next, think of three monks; suppose that Benedict and Cyril have blobs, but Aelfred does not.
Benedict sees just one blob, on Cyril’s head. He reasons that if he, Benedict, does not have a blob, then Cyril sees no blobs at all. So Cyril will raise his hand after the first ring. But Cyril doesn’t (we’ll shortly see why), so Benedict now knows that he must have a blob. So he raises his hand after ring 2.
Cyril is in exactly the same position as Benedict, since he also sees just one blob, on Benedict. So he does not raise his hand after the first ring, but does at the second.
Ian Stewart Page 23
