The Pigeonhole Principle: Choosing the Boxes

Here is a piece of mathematics you already know. If you have more things than places to put them, some place gets two things. That is it. It sounds like it could not possibly prove anything, and over the next few minutes I would like to change your mind about that. So here it is, properly. Four boxes, five items. Put them away however you like, however cleverly, and one of these boxes ends up holding two. Say the same thing with a letter in it. Put n plus one items into n boxes, and some box holds at least two of them. And the proof is a single sentence. If every box held one item or none, then adding up over the boxes you would have at most n items in total. But you have more than n. So some box was holding two. That sentence is the easy half, and I will never have to say anything harder than it. The hard half never appears in it at all, because the hard half is deciding what the items are and what the boxes are. So let me put three statements on the board. Not one of them mentions a box, or an item, or anything that looks like counting. Two people at any party know the same number of people there. Any ten numbers, all different, contain four that go steadily up or four that go steadily down. And every irrational number has fractions chasing it far more closely than it has any right to expect. Every one of those is the sentence you just heard, applied once. So watch the boxes each time, and not the sentence. The boxes are the argument.

Six people at a party. Some of them know each other and some do not, and knowing is mutual: if I know you, you know me. That is the only rule there is, and here is one particular evening. Now go round and count. A knows exactly one person here. B knows two. And C also knows two. D, E and F each know three of the others. So the six counts are one, two, two, three, three, three, and they have already collided twice. You might reasonably think that was luck, and that I drew the lines to make it happen. I did not. Whatever this picture had looked like, two of the counts would have had to agree, and I want to show you why. Take the people themselves as the items. For the boxes, take the possible answers to the question: how many people here do you know? Nobody can know more than the other n minus one, and nobody can know fewer than none at all, so every count lands somewhere in this list. Now count the boxes. Zero, one, two, and so on up to n minus one. That is n boxes for n people, and pigeonhole gives us absolutely nothing. Six items in six boxes can sit one to a box quite happily. So the obvious choice of boxes fails, and I want you to sit with that for a moment, because this is exactly where these proofs are won or lost. Look at the two boxes on the ends. Can they both be used at once? Suppose somebody at this party knows nobody. Then no one in the room can know everybody, because knowing everybody would include knowing that person. Box zero and box n minus one can never both be occupied. So one of the two ends is always empty, whichever way it falls. The boxes were never n. There were only ever n minus one of them. Six people, five boxes. And now the sentence from the beginning does all the remaining work, without being asked twice. Two of them land together. Two people at any party, anywhere, know the same number of people at that party. Notice how little of that was cleverness. One honest look at which boxes could actually be used, and the theorem fell out.

Ten numbers, all different, in whatever order somebody wrote them down. Position along the bottom, value up the side. I want to hunt for runs. A run means this: read from left to right, skipping whatever you like, and take terms that keep going up, or terms that keep going down. They do not have to be neighbours. Start at the second term, which is seven. Going up from there I can reach nine, and then ten. A rising run of three. Going down from that same seven I can reach five, and then four. A falling run of three as well. So attach two numbers to every position. Call them u and d: the length of the longest rise that starts there, and the length of the longest fall that starts there. At the second term, both of them are three. Now, does this sequence contain a run of four? It does. Two, five, eight, ten, at positions three, five, seven and nine, rising the whole way. And that was not luck either. Any ten distinct numbers contain four that rise, or four that fall. To see it, suppose they do not. Suppose there is no rising run of four anywhere, and no falling run of four either. Then every u is one, two or three, and so is every d. Two numbers, three choices each. Three times three is nine possible pairs, and there are the nine of them, one box apiece. But there are ten positions, and each position hands you one pair. Ten items, nine boxes. So two positions, i somewhere to the left of j, carry the identical pair. Same u, same d. And now it breaks. The numbers are all different, so either a i is below a j or above it. Suppose it is below. Take the longest rise starting at j, and stick a i on the front of it. That is a rise starting at i, and it is one term longer. So u i beats u j, when they were supposed to be equal. If a i is the larger one instead, the very same trick runs downhill and d i beats d j. Either way the two pairs could not have matched, so the assumption is dead. There has to be a monotone run of four somewhere in that sequence. And ten was not an arbitrary number. Nine positions fit into nine boxes without any fight at all, so ten is the first length that forces the issue. Three by three, plus one.

One more, and this time the boxes are not objects at all. They are stretches of a line, and that turns out to change nothing about the argument and everything about what it can prove. The subject is approximating an irrational number by a fraction. Getting close to the square root of two is easy: take enough decimal places. The real question is how close you can get while keeping the denominator small. Dirichlet's answer is startling. For every whole number N there is a fraction p over q, with q no bigger than N, that sits within one over q times N of your number. And since q is at most N, that is within one over q squared. A denominator of five buying an error under one twenty fifth is not what randomly chosen fractions do for you. So, the boxes. Let N be five, and take the first six multiples of root two: nought, one point four one, two point eight three, four point two four, five point six six, and seven point zero seven. Now throw away the whole number part of each one and keep only what comes after the point. Six numbers, every one of them somewhere between nought and one, and here they are. And cut that stretch from nought to one into five equal pieces. Those are the boxes. Six numbers, five intervals, and I do not have to look at the numbers to know what happens next. Two of the six share an interval. Here they are: the very first one, which is nought exactly, and the last one, seven point zero seven with the seven thrown away. Both of them inside the leftmost box. And two numbers sitting in one interval of width a fifth are less than a fifth apart. That is everything the boxes were ever for. From here it is arithmetic. Write it out in general. The items are these N plus one fractional parts, one for each multiple of alpha from nought up to N. The boxes are the N intervals. More numbers than intervals, so two of them land in the same one: call their indices i and j, with i the smaller. The two fractional parts differ by less than one over N. Now unpack what a fractional part is. It is the number itself, minus some whole number. So that small difference is j alpha minus i alpha, with an integer taken off it. Give those two things names. Let q be j minus i, which is between one and N, and let p be the integer that came off. Then q alpha minus p is less than one over N in size. Divide the whole line through by q. Alpha minus p over q is less than one over q N. And q is at most N, so one over q N is at most one over q squared, which is the theorem. Put our own numbers in. The two indices were nought and five, so q is five, and p works out at seven. Seven fifths, which is one point four. The true error is a hundredth and a bit, comfortably inside the one twenty fifth we were promised. And run the whole thing again with a larger N and you get a different fraction, a better one. Which means an irrational number has infinitely many fractions chasing it this closely, forever. And the boxes that proved it were five stretches of a line. Three theorems, then, and three choices of box. In the first, the items were people and the boxes were the possible answers to a question, once we had noticed that two of those answers could never both be used. In the second, the items were positions in a sequence, and the boxes were pairs of numbers we had to invent from nothing. In the third, the items were multiples of alpha, and the boxes were stretches of a line. And the sentence at the end was the same all three times. More items than boxes, so two share a box. It was never the hard part. The boxes were.