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

Strangely, the cups refuse to behave themselves, no matter what moves the mug attempts. What the mug fails to notice is that the initial position has been changed, surreptitiously. And even if he does notice the change, he may not be aware of the devastating consequences. The parity (odd/even) of the set of upright mugs has now changed from even to odd. But every move preserves this parity. The number of upright cups changes by -2, 2 or 0 at each move, so even numbers stay even and odd numbers stay odd. The first starting position has even parity, and so does the required final position. But the second initial position has odd parity. This makes the required final position inaccessible - not just in three moves, but in any number whatsoever.

This disgraceful con-trick (please do not try this at home, or in a bar, or anywhere else - or if you do, keep me out of it) shows that there can be obstacles to cup-inversion, but it also misdirects the mug into looking for a three-move solution when the original problem can actually be solved in one move.

The problem can be generalised, with a slight difference from the pub scenario. The resulting puzzle involves the same principles, but it’s tidier. I’ll ask you two instances of it.

Suppose you start with 11 cups, all upside down. The rule is that you must make a series of moves, each of which inverts precisely 4 cups. They do not have to be adjacent. Your objective is to get all 11 cups upright at the same time. Can you do this, and if so, what is the smallest number of moves that does the job?

The same question starting with 12 cups, all upside down. Now the rule is that each move must invert precisely 5 cups. Again they do not have to be adjacent. Your have to get all 12 cups upright at the same time. Can you do this, and if so, what is the smallest number of moves required?

 

Answers on page
287

Coded messages are as old as writing, but most of the early codes were very easy to break. For instance, the message
can be decoded as
just by changing each letter into the previous one in the alphabet. If the code shifts the entire alphabet along a number of steps, there are only 25 possibilities to try. Julius Caesar is thought to have used this kind of code, with a shift of 3, in his military campaigns. It has the advantage that encrypting messages (putting them into code) and decrypting them (working out the original ‘plaintext’ from the coded message) are easy. Its main disadvantage is that you don’t have to be very bright to break the code.

You don’t have to keep the alphabet in (cyclic) order, of course; you could shuffle it into some random-looking order, giving a substitution code. Both sender and recipient must know the shuffled order, so they probably have it written down somewhere, which is potentially insecure. Or else they remember a ‘key’ such as DANGER! FLYING PIGS, which reminds them to use the order
which starts with the letters of the key, ignoring duplicates, and finishes with all the others in alphabetical order. Or maybe reverse alphabetical order, if lots of letters happen to remain unchanged.

Substitution codes are easy to break if the person trying to break them has access to a reasonable quantity of coded messages, because in any language some letters occur more often than others. By calculating the frequency with which each letter occurs - the fraction of times it appears, relative to the total
number of letters - you can make an educated guess at the plaintext, and then correct it by looking for words that almost make sense but don’t quite.

Typical frequencies of letters in written English.

For instance, in most English writing, the commonest letter is E, followed by T, A, O, I, N, and so on. Of course, texts from different sources may have different frequencies, but all we need is a rough guide. Suppose we already know that in the coded messages, the corresponding ‘top six’ letters are Z, B, M, X, Q, L. Our first attack on the code message
is to replace each of the letters ZBMXQL by the corresponding ones in ETAOIN. The result (replacing unknown letters by *s) is
which doesn’t look promising until we realise that NIT is unlikely to appear, whereas NOT is quite plausible. So perhaps X and Q are the wrong way round, and ETAION corresponds to ZBMQXL. Now we decode the message as

The second word can’t be TO or NO, because T and N have already been used, but it could well be DO. Now we know that
letter R encodes D, and so on. If we guess that the twice-used pair CY should be GS, we’re looking at
and the code breaks wide open.

What worked (probably badly) for Julius Caesar was not suitable for secure communications in more recent times. Once semaphore, the telegraph and radio were invented, and messages did not have to be carried by a human courier or a pigeon, secure codes became crucial to military and commercial operations. The subjects of cryptography (putting messages into code) and cryptanalysis (decoding them without initially knowing the code) became much more important. Today, almost all countries have big operations in both.

Clearly, the two are linked: in order to break a code you need a lot of sample messages, and some understanding of what sort of code might be involved. Letter frequencies, for instance, do not help much if it is not a substitution code - and it won’t be. Each procedure for encrypting messages generates specialised methods for trying to break it.

For very high security, the traditional encryption method is the one-time pad. Here, the originator and recipient of the code message both possess a ‘notepad’ listing ‘keys’, which are sequences of random numbers. One such sequence is used for any given message, and after use it is destroyed. The numbers on that page are combined with the letters in the plaintext message according to a simple mathematical rule. For instance, successive numbers in the sequence may indicate how far along the alphabet the corresponding letter is to be displaced. So, for example, if the pad reads
and the plaintext is
then the encrypted message would be

(P moves along 5 places, I moves 7 places, and so on). I’m ignoring how to treat spaces, and in practice these should be thought of as additional ‘letters’.

The one-time pad was invented in 1917, and it has been proved that any perfectly secure code must use keys that are in some sense equivalent to one-time pad keys. Although one-time pads are secure against any cryptanalysis system, they are not fully secure, because the notepad might be discovered. Originally, the notepad was a physical object - a pad of paper. To reduce the risk of discovery, it was often printed in very small type, and read using a magnifying-glass. For ease of disposal, the pages were made of inflammable material. Today, the ‘notepad’ might be a computer file.

As a warm-up to more modern methods of data encryption, we need to understand a curious type of arithmetic that goes back to Carl Friedrich Gauss. It is called modular arithmetic, and it is widely used in number theory.

Pick some number, say 4, and call it the modulus. Work only with the whole numbers 0, 1, 2, 3 that lie between 0 (included) and the modulus (excluded). To add two such numbers, add them in the usual way, but if the sum is greater than or equal to 4 (the modulus), subtract a multiple of 4 to reduce the sum to the range 0-3. Do the same for multiplication. So, for example,

We can write down addition and multiplication tables:

Here the boldface numbers show which numbers are being operated on, and the number in the corresponding row and column is the result. For example, to find 3 + 2 look in row 3, column 2 of the table with a + in the top left-hand corner. The result is 1, so 3 + 2 = 1.

Well, you may not approve of arithmetic in which 3 + 2 = 1, but it turns out to be vital to any problem in which what really matters is the
remainder
after dividing by 4. For instance, if you turn some object through four right angles it ends up exactly where it started. So a turn of three right angles followed by two right angles has the same affect as a turn through one right angle. (Yes, that’s also five right angles, but only 0, 1, 2, 3 right angles are needed to cover all possibilities, so it often makes sense to stay in that range.) So
and 3 + 2 = 1 isn’t so silly in this context. Neither is 2 + 2 = 0, which is how that sum pans out. Rotate through two right angles, and another two right angles, and you get right back where you began - a rotation through zero right angles.

Two right angles plus two right angles equals zero right angles.

The fun comes when you discover that you can use any positive whole number as the modulus - not just 4. The same ideas still work, and they’re now sufficiently general to be useful. Any process that repeats the same behaviour over and over again, for instance, may be ripe for analysis using this kind of arithmetic.

When the modulus is 12, we get what is often called clock arithmetic, because on a conventional clock the hour hand gets back to the same position after 12 hours have passed, so multiples of 12 have the same effect as zero.

These funny variants on arithmetic turn up whenever things fit together as part of some cycle that eats its own tail and starts again. It turns out that they obey all of the standard laws of algebra, such as
and so on. There are a few oddities, though, especially when it comes to division. For example, when working to the modulus 4, the fraction
makes no sense. If it did make sense, it would be whichever number, multiplied by 2, gives 1. But the only multiples of 2 are 0 and 2 - the number 1 never appears.