Professor Stewart's Hoard of Mathematical Treasures (53 page)

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.

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.

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:

Here ┌x┐ is the ceiling function: the smallest integer greater than or equal to x.

The general procedure for the RSA cryptosystem goes like this:

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:

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 9
x
+ 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 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
) - 2
b
= 45 - 2
b
. 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:

The other set of five must be whatever these miss out, namely:
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.

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.

Aelfred is in a rather different position. He sees two blobs, one on Benedict and one on Cyril. He wonders whether he, Aelfred, also has a blob. If so, then all three of them have blobs, and he knows from the previous version of the puzzle that they will all wait for ring 3 and then raise their hands. So he does not, and should not, raise his hand after ring 1 or 2. Then the other two do raise their hands: at that point he knows that he does not have a blob.