13 October 1991
Matthew Morrison Maddox is a professional mathemagician. Like any member of the Magic Circle, he is sworn to secrecy never to reveal his tricks. However, if you're mathematically aware, it's not so hard to work out the secrets behind some of the simpler ones.
Let me give you an example.
The scene: a small theatre in a Marseille backstreet. Maddox is on stage, dressed as always in his homespun black cloak and wooden chain. He has just finished sawing a Klein bottle in half to get two Möbius bands. You may think that's easy --- and it is, to a mathematician --- but Morris has performed it with a glass bottle and produced two glass Möbius bands. It's those features of his act that really baffle me. I assume they're mostly sleight-of-hand, but I can't see what he does and he's not telling.
He's into the next trick now.
MADDOX: I need the assistance of a young lady from the audience. (Walks to front row of seats.) Good evening, Mam'selle, would you be willing to help me? (She looks embarrassed but nods.) And would you be so kind as to tell us your name?
JOSEPHINE: Er --- Josephine.
MADDOX: Please come this way. (Helps her on to the stage and sits her at a small table. On it is a small red box; next to it, a slate and chalk.) By the way, Josephine, are you good at mental arithmetic?
JOSEPHINE: Well ---
MADDOX: I'm not. Like me, I think you might find a calculator helpful. (He reaches into her hair and pulls out a pocket calculator.) Funny place you keep it. (Laughter.) Numbers are magic, you know. To prove it, I am going to put on this blindfold and stand with my back to you, like... so. Now, I want you to write your age on the slate.
JOSEPHINE: M'sieur, a lady never reveals her age!
MADDOX: Sacrifices must be made in the name of magic, Josephine. Write it so that neither I nor the audience can see, and place it face down on the table. Have you done that?
JOSEPHINE: Yes.
MADDOX: Look in the red box, and you will find some cards. Written on them are all the numbers from 1 to 16. Now, Josephine: you know what a prime number is?
JOSEPHINE: Yes, it's one that has no factors other than 1 and itself.
MADDOX: Good. And all the other numbers are composite. I want you to enter your age into the calculator. Then take out the cards, one by one. If the number on the card is composite, throw the card on to the floor. But, if it is prime, I want you to multiply the number in the calculator by the number on the card. Keep doing this until you have used up all the cards. Got that?
JOSEPHINE: Yes.
MADDOX: Please proceed. Tell me when you have finished --- but do not tell me what number is shown on the calculator at the end.
JOSEPHINE: (Picks out cards and calculates.) Finished!
MADDOX: Thank you, Josephine. Now, you have performed a very long calculation and got quite a long number... six digits, I believe.
JOSEPHINE: Yes. How did you ---
MADDOX: Mathemagic, my dear. Now, I am sure you can see that, if you were to tell me the actual number you arrived at, then I might be able to work out your age by performing some equally complicated calculation.
JOSEPHINE: That makes sense.
MADDOX: But I am not going to ask you for the number. I am going to ask you for just one of its six digits, and then --- instantly --- tell you your age. Right? Good. Please tell me the second digit.
JOSEPHINE: Six.
MADDOX: (Without apparent hesitation) Your age is twenty-two! Is that correct? Please show the audience the number you wrote on the slate. (She does so. It is '22'. Wild applause.)
After the show, I found Maddox in his dressing-room. "Have you worked it out yet?" he asked.
"You mean the trick with the age written on the slate?"
"That's the one. Should be within your competence."
I nodded. "It's 1001, isn't it?"
He laughed. "Just to satisfy my curiosity, you must explain precisely what you mean by that cryptic remark, my friend. But first---" he produced a corkscrew from thin air and passed it to me, along with a bottle of local red wine and two glasses--- "open that." I got absolutely nowhere until I discovered that the corkscrew had a left-handed thread and had to be turned anticlockwise. I poured two glasses full. The wine ran out of mine and down my shirt. The stain turned blue, faded to green, and vanished. Silently he passed me a replacement glass.
"Well," I said, "there are lots of cute number tricks based on the fact that 1001 = 7.>11.>13. The common feature is that if you multiply a three-digit number, say 567, by 1001, you get the same three digits repeated: 567567."
"Yes, you're on the right track."
"The basic idea is to disguise the fact that you're multiplying by 1001. So you multiply by 7, 11, and 13 separately. In your trick, Josephine multiplied by all the primes between 1 and 16: that is, by 2, 3, 5, 7, 11, and 13. The number 1 is usually considered not to be prime, but it makes no difference if you include it too. She selected those numbers in some random order... nice piece of indirection, that," I added, "but of course it has no effect at all. The result is the same, in whatever order she drew the cards."
"Of course," he said. "Continue."
"Let's take Josephine's actual age, 22. Multiplying it by 2.3.5.7.11.13 is the same as multiplying by 2.3.5 = 30 and then by 7.11.13 = 1001. Multiplication by 30 is the same as multiplying by 3 and then putting a 0 on the end, so she gets 660. Multiplying that by 1001 just repeats the digits, 660660. In general, the final number in the calculator will always be of the form ab0ab0 where ab is three times the lady's age. Although there are six digits, you only need to know two of them --- the first two."
"Yes, but I only asked for the second one."
"Which in this case was 6. So three times her age is a6. Now, a number is a multiple of 3 if and only if the sum of its digits is a multiple of 3; so a must be 0, 3, 6, or 9. Three times her age is 06, 36, 66, or 96. So her age is 2, 12, 22, or 32. But anyone can tell a woman's age to within ten years, so you knew it must be 22."
"You haven't grasped the whole of it, but basically you're right."
"Let me guess some more. She has to be under 33 or you get trouble: more than six digits on the calculator. Hmmm...You always pick ladies who look between the ages of 19 and 28, to reduce the possibilities in advance. And even if your initial guess is off by a few years, you can easily distinguish a 17-year old from a 27-year old."
"More or less."
"And while you're saying 'Your age is', you're doing the calculation to work out the missing digit and divide by 3."
He shook his head. "No, I've done the trick so often I know the answer as soon as she gives me that one digit. Try me. Just give me the second digit on the calculator: I'll give you the age --- assuming it's between 19 and 28."
"OK. Seven."
"Nineteen."
"Eight."
"Twenty-six."
"Two."
"Twenty-four."
"I'm convinced," I said. Later I worked out a table (Table 1): it wouldn't take long to learn it by heart.
Table 1 Ages (if between 19 and 28) corresponding to the second digit on the calculator.
| 2nd digit | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| age | 20 | 27 | 24 | 21 | 28 | 25 | 22 | 19 | 26 | 23 |
"That reminds me of an interesting mathematical problem," I said, refilling both glasses. "The unusual factorisation 7.11.13 of the number 1001 is responsible for one of the strangest coincidences in the whole of mathematics."
"Inasmuch as anything in mathematics can be a coincidence," Maddox pointed out. He had removed one of my shoes and was tying knots in my shoelace, then cutting them into bits with a huge pair of scissors. I hoped he knew what he was doing. "After all, everything in mathematics is predetermined."
"I understand that," I said. "But this one really does look like a coincidence. It's to do with Pascal's triangle."
"The table of binomial coefficients," he said. "Every number is the sum of the two above, with 1's at the ends. Like this." He gave me back my shoe: the laces were intact but the ends seemed to have fused together into a seamless loop. He drew on his slate:
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
"OK, you can stop now," I said hastily. I once had a terrible experience in a Chinese restaurant when the waiter discovered I was a mathematician, and began scrawling Pascal's triangle on the tablecloth. By the time he reached the tenth row, my dinner companion was going glassy-eyed. By the time he reached the fifteenth row, so was I. He may have reached the twentieth row, but by then, we had left. I have occasional visions of a Chinese restaurant, its floor, walls, and ceiling entirely covered with numbers from Pascal's triangle, with a manic waiter still scribbling. Hell must be like that.
"Apart from its general importance in algebra and so on," I said, "Pascal's triangle is very interesting from a number-theoretic point of view. The general formula for the rth number in the nth row is
C(n,r) = n!/(r!(n-r!) = [n(n-1)...(n-r+1)]/[r(r-1)...3.2.1]
For instance,
C(14,6) = [14.13.12.11.10.9]/[6.5.4.3.2.1] = 3003.
Although Pascal's triangle is defined in terms of addition, the general formula is all about multiplication and division. That's very curious: it means that properties unrelated to addition can turn up unexpectedly."
"I'm not sure I follow you. Give an example."
"All right. Suppose that n is prime. Then all entries in row n of Pascal's triangle, other than the first and last, are divisible by n."
"Let me see... 5 is prime, and the entries in row 5 are 1, 5, 10, 10, 5, 1. All except the 1's are multiples of 5. I see. But what have primes got to do with addition?"
"Precisely," I said. "That's the surprise. But the proof is easy: just look at the formula. The numerator of the fraction is n(n-1)...(n-r+1), which is divisible by the prime n. Unless r = 0, of course, in which case the formula must be interpreted as a product of no integers at all, that is, as 1. The denominator is r(r-1)...1. If r < n, then since n is prime, nothing in the denominator is divisible by n. So the factor n can't cancel, and C(n,r) itself must be divisible by n."
"Amazing. Yes, I can see you'd have trouble proving anything like that directly from the definition in terms of addition."
"Even though Pascal's triangle has been studied for a long time ---"
"Ever since Pascal, I presume."
"Oh, much longer than that! The triangle appears on the title page of an early 16th century arithmetic by Petrus Apianus; it can be found in a Chinese mathematics book of 1303, and indeed it has been traced back at least to Omar Khayyaæ>m around 1100, who almost certainly got it from earlier Arabic or Chinese sources. Michael Stifel introduced the term binomial coefficient around 1500. The explicit formula was given by Isaac Newton. In its interpretation as the number of ways to choose r items from a set of n, this expression (though not in that notation) was known to Bhaskara (b. 1114).
"Actually, the theory of morphic resonance would strongly suggest it was invented in the year 1001... but I digress. Even though Pascal's triangle has been studied for a long time, many questions about it remain unanswered. One of the simplest was asked by David Singmaster in 1971. How many times can a number occur in Pascal's triangle?"
"Pardon?"
"Well, think about the number 6. It occurs three times in Pascal's triangle. Once near the start and end of row 6, and once more in the middle of row 4. That is,
C(6,1) = C(6,5) = C(4,2) = 6.
We can ask the same question for any other number."
"I see. The number 1 occurs infinitely often, of course."
"Yes; and it's the only number that does. Singmaster proved in 1971 that any number n > 1 occurs no more than 2 + 2 log n times. Lots of numbers occur twice, because each row in Pascal's triangle is palindromic: the second half is the same as the first, but in reverse. So any number not occurring in the exact centre is repeated twice."
"And any of those not occurring in the second or next-to-last place actually occur at least four times," said Maddox.
"Why?"
"Well, take a number like 15. It occurs twice in row 6, as C(6,2) and C(6,4). But it also occurs as C(15,1) and C(15,14), because the second and next-to-last entries in row m are always equal to m."
"Excellent!", I said. "So we know that lots of numbers --- in fact, infinitely many --- occur at least four times in Pascal's triangle. But no numbers seem to occur very often. Singmaster observed that, among all the numbers up to 2 48>, precisely one occurs eight times in Pascal's triangle, and everything else occurs less than eight times. In 1971 he conjectured that the number of occurrences is bounded: that is, there is some fixed number k such that no number other than 1 occurs more than k times in Pascal's triangle. The evidence so far suggests that k = 8 works."
"Which number occurs eight times?" asked Maddox.
"3003," I said. "And thereby hangs a tale, inasmuch as this is 3.1001, and the factorisation of 1001 is the reason for the eightfold occurrence of the number 3003."
Maddox leaned back in his chair, and absent-mindedly pulled several knotted handkerchiefs from his ears. "I think you'd better go into that in more detail."
"I was going to," I said. "Singmaster was intrigued by a pattern that occurs in rows 14, 15, and 16 of Pascal's triangle, starting with C(14,4) = 1001. It looks like this:
row 14 1001 2002 3003
row 15 3003 5005
row 16 8008
I've put the 3003 in bold to emphasise it. There are all sorts of peculiarities of this section of the table. For example, the top row is the only place where three successive entries in a row occur in the ratio 1:2:3. And if you divide out the 1001 you get Fibonacci numbers 1,2,3,5,8, a fact that is related to the additive structure of Pascal's triangle."
"Let me see," said Maddox. The number 3003 occurs four times in those rows: at C(14,6) and C(15,5), and also in the corresponding positions at the other end of those two rows, namelyC(14,8) and C(15,10)."
"Right,"
"And 3003 also occurs twice in row 3003, as I explained a little while ago."
"Yes, at C(3003,1) and C(3003,3002)."
"That only makes six occurrences. What about the other two?"
I laughed. "Isn't it obvious? They're in row 78. At C(78,2) and C(78,76)."
"No," he said. "It jolly well isn't obvious."
"My point," I said. "It's a coincidence. In fact, the whole thing is one colossal coincidence, and it happens because 1001 = 7.11.13. But let me prepare the ground a little. You agree that if in any row we see three consecutive binomial coefficients in the ratio 1:2:3, then the third one also appears the next row down?"
"Yes, I see that. The numbers will be a, 2a, and 3a; and the next row down will have to include a+2a = 3a, because each number in Pascal's triangle is the sum of the two above it."
"Fine. Because rows are palindromic, that means that 3a will occur at least four times, twice in each of those rows. By your observation, it also occurs twice in row 3a. That makes six occurrences."
"Right."
"Suppose that in addition to all this, 3a is a triangular number. A sum of consecutive integers, 1+2+3+...+m. Those numbers are precisely the binomial
coefficients C(m+1,2). So there will be two more occurrences in row m. Making eight altogether."
"I see that too. But why should it be triangular?"
"No idea. Just suppose."
"If you insist."
I noticed that my shoelaces had miraculously returned to normal. Refusing to be put off, I replied "I do. Now, let's look at the values of C(14,4), C(14,5) and C(14,6). From the formula,
C(14,4) = [14.13.12.11]/[4.3.2.1]
The 4.3 in the denominator cancels the 12 in the numerator. The factor 2 in the denominator divides into 14 in the numerator to give 7. So we're left with 7.11.13 which should look familiar by now."
"Sure."
"Now think about C(14,5). We get this from C(14,4) by multiplying the numerator by 10 and the denominator by 5. The 5 cancels, and we get just a factor of 2. So C(14,5) = 2C(14,4). Finally, C(14,6) = 9C(14,5)/6, which is 3/2 times as big again. But 3/2 x >2 = 3, so the three consecutive entries are in the ratio 1:2:3. Just think about all the numerical coincidences involved! They scarcely bear contemplating."
"You've still not done the triangular number bit," complained Maddox.
"Sorry. That happens because triangular numbers are always of the form n(n+1)/2, and 3003 = 3.7.11.13 = 77.78/2. . Which seems to me to be just as much a coincidence as anything else."
"I see what you mean."
"You'll see it even more if you try to prove or disprove Singmaster's conjecture that the number of occurrences is bounded. You end up worrying more and more about possible strange coincidences. It's hard to make any progress at all. Nobody has any idea how to solve it: it's wide open."
"It looks like the sort of question that recreational mathematicians might like to tackle," said Maddox thoughtfully. "Not to solve the problem completely, but to see what they can dig up. Extending Singmaster's calculations past 2 48>, for instance. What else is known about the problem?"
"Up to 2 48>, the only nontrivial repetitions are those in Table 2. Singmaster proved in 1975 that infinitely many numbers occur at least six times in Pascal's triangle." For example,
C(104,39) = C(103,40) = 61218182743304701891431482520,
so this colossal number (one of the smallest found by Singmaster's method) occurs at least six times. (In fact this one occurs only six times. But maybe some of the larger ones might also occur elsewhere?)
"You could try asking the same question for Stirling's triangle, where each number is twice the number above and to the right plus the number above and to the left," I suggested. Like this:
1 1
1 3 1
1 7 5 1
1 15 17 7 1
1 31 49 31 9 1
1 63 129 111 49 11 1
Table 2 Nontrivial repetitions in Pascal's triangle
120 = C(16,2) = C(10,3)
210 = C(21,2) = C(10,4)
1540 = C(56,2) = C(22,3)
7140 = C(120,2) = C(36,3)
11628 = C(153,2) = C(19,5)
24310 = C(221,2) = C(17,8)
3003 = C(78,2) = C(15,5) = C(14,6)
Or you could try Bernoulli's triangle
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
1 7 22 42 57 63 64
which is formed as for Pascal's triangle, but with powers of 2 down the right hand edge.
"I'm astonished," admitted Maddox. "It never occurred to me that a question as simple as that might be so hard to answer, or lead into such mirky waters." He peered into his wineglass as if it might reveal the secret of Life, the Universe, and Everything; and fished out a dead gnat. He snapped his fingers and it turned into a chameleon and ran off. "But," he went on, "this 1001 business isn't coincidence, you know."
"No?" I said. "What is it, then?
"Magic."
FURTHER READING
H.L.Abbott, P.Erdös, and D.Hanson, On the number of times an integer occurs as a binomial coefficient, American Mathematical Monthly 81 (1974) 256-261.
David Singmaster, How often does an integer occur as a binomial coefficient? American Mathematical Monthly 78 (1971) 385-386.
David Singmaster, Repeated binomial coefficients and Fibonacci numbers, Fibonacci Quarterly 13 (1975) 295-298.