WEBVTT 00:00:00.058 --> 00:00:02.785 Here is a piece of mathematics you already know. 00:00:02.868 --> 00:00:07.385 If you have more things than places to put them, some place gets two things. 00:00:07.581 --> 00:00:08.766 That is it. 00:00:09.079 --> 00:00:12.852 It sounds like it could not possibly prove anything, and over the next few minutes I 00:00:12.852 --> 00:00:14.885 would like to change your mind about that. 00:00:16.281 --> 00:00:18.349 So here it is, properly. 00:00:18.545 --> 00:00:20.926 Four boxes, five items. 00:00:21.239 --> 00:00:23.037 Put them away however you like, 00:00:23.120 --> 00:00:27.079 however cleverly, and one of these boxes ends up holding two. 00:00:27.992 --> 00:00:30.071 Say the same thing with a letter in it. 00:00:30.268 --> 00:00:35.400 Put n plus one items into n boxes, and some box holds at least two of them. 00:00:35.825 --> 00:00:38.252 And the proof is a single sentence. 00:00:38.449 --> 00:00:40.618 If every box held one item or none, 00:00:40.701 --> 00:00:44.905 then adding up over the boxes you would have at most n items in total. 00:00:45.101 --> 00:00:46.725 But you have more than n. 00:00:46.808 --> 00:00:48.992 So some box was holding two. 00:00:49.788 --> 00:00:54.398 That sentence is the easy half, and I will never have to say anything harder than it. 00:00:55.013 --> 00:00:57.008 The hard half never appears in it at all, 00:00:57.091 --> 00:01:00.923 because the hard half is deciding what the items are and what the boxes are. 00:01:01.406 --> 00:01:03.984 So let me put three statements on the board. 00:01:04.181 --> 00:01:05.909 Not one of them mentions a box, 00:01:05.992 --> 00:01:09.267 or an item, or anything that looks like counting. 00:01:09.808 --> 00:01:13.083 Two people at any party know the same number of people there. 00:01:13.280 --> 00:01:14.334 Any ten numbers, 00:01:14.417 --> 00:01:19.701 all different, contain four that go steadily up or four that go steadily down. 00:01:20.153 --> 00:01:21.348 And every irrational 00:01:21.348 --> 00:01:26.411 number has fractions chasing it far more closely than it has any right to expect. 00:01:27.208 --> 00:01:31.156 Every one of those is the sentence you just heard, applied once. 00:01:31.353 --> 00:01:36.416 So watch the boxes each time, and not the sentence. The boxes are the argument. 00:01:37.503 --> 00:01:39.292 Six people at a party. 00:01:39.395 --> 00:01:44.421 Some of them know each other and some do not, and knowing is mutual: if I know you, 00:01:44.504 --> 00:01:45.677 you know me. 00:01:46.129 --> 00:01:50.333 That is the only rule there is, and here is one particular evening. 00:01:51.129 --> 00:01:52.930 Now go round and count. 00:01:53.033 --> 00:01:55.449 A knows exactly one person here. 00:01:55.645 --> 00:01:57.028 B knows two. 00:01:57.224 --> 00:01:59.361 And C also knows two. 00:02:00.263 --> 00:02:03.375 D, E and F each know three of the others. 00:02:03.560 --> 00:02:07.122 So the six counts are one, two, two, 00:02:07.205 --> 00:02:12.361 three, three, three, and they have already collided twice. 00:02:13.146 --> 00:02:14.295 You might reasonably think 00:02:14.295 --> 00:02:17.930 that was luck, and that I drew the lines to make it happen. 00:02:18.382 --> 00:02:19.579 I did not. 00:02:19.892 --> 00:02:23.617 Whatever this picture had looked like, two of the counts would have had to agree, 00:02:23.700 --> 00:02:25.535 and I want to show you why. 00:02:27.349 --> 00:02:30.032 Take the people themselves as the items. 00:02:30.345 --> 00:02:33.559 For the boxes, take the possible answers to the question: 00:02:33.642 --> 00:02:35.745 how many people here do you know? 00:02:35.941 --> 00:02:40.248 Nobody can know more than the other n minus one, and nobody can know fewer than 00:02:40.248 --> 00:02:44.115 none at all, so every count lands somewhere in this list. 00:02:44.912 --> 00:02:46.666 Now count the boxes. 00:02:46.863 --> 00:02:51.345 Zero, one, two, and so on up to n minus one. 00:02:51.797 --> 00:02:56.883 That is n boxes for n people, and pigeonhole gives us absolutely nothing. 00:02:57.335 --> 00:03:01.376 Six items in six boxes can sit one to a box quite happily. 00:03:02.080 --> 00:03:06.144 So the obvious choice of boxes fails, and I want you to sit with that for a moment, 00:03:06.144 --> 00:03:10.089 because this is exactly where these proofs are won or lost. 00:03:10.172 --> 00:03:12.344 Look at the two boxes on the ends. 00:03:12.541 --> 00:03:14.747 Can they both be used at once? 00:03:15.230 --> 00:03:19.467 Suppose somebody at this party knows nobody. Then no one in the room can know 00:03:19.550 --> 00:03:23.719 everybody, because knowing everybody would include knowing that person. 00:03:23.915 --> 00:03:28.630 Box zero and box n minus one can never both be occupied. 00:03:28.973 --> 00:03:32.945 So one of the two ends is always empty, whichever way it falls. 00:03:33.141 --> 00:03:35.009 The boxes were never n. 00:03:35.092 --> 00:03:37.647 There were only ever n minus one of them. 00:03:38.443 --> 00:03:40.789 Six people, five boxes. 00:03:40.893 --> 00:03:43.910 And now the sentence from the beginning does all the remaining work, 00:03:43.993 --> 00:03:45.805 without being asked twice. 00:03:46.416 --> 00:03:48.297 Two of them land together. 00:03:48.401 --> 00:03:53.429 Two people at any party, anywhere, know the same number of people at that party. 00:03:53.626 --> 00:03:56.018 Notice how little of that was cleverness. 00:03:56.215 --> 00:03:58.953 One honest look at which boxes could actually be used, 00:03:59.036 --> 00:04:00.732 and the theorem fell out. 00:04:01.791 --> 00:04:06.111 Ten numbers, all different, in whatever order somebody wrote them down. 00:04:06.308 --> 00:04:09.594 Position along the bottom, value up the side. 00:04:10.391 --> 00:04:12.377 I want to hunt for runs. 00:04:12.573 --> 00:04:14.304 A run means this: 00:04:14.501 --> 00:04:17.552 read from left to right, skipping whatever you like, 00:04:17.635 --> 00:04:21.593 and take terms that keep going up, or terms that keep going down. 00:04:21.676 --> 00:04:23.674 They do not have to be neighbours. 00:04:24.099 --> 00:04:26.387 Start at the second term, which is seven. 00:04:26.583 --> 00:04:31.437 Going up from there I can reach nine, and then ten. A rising run of three. 00:04:32.141 --> 00:04:36.042 Going down from that same seven I can reach five, and then four. 00:04:36.239 --> 00:04:38.527 A falling run of three as well. 00:04:39.323 --> 00:04:41.864 So attach two numbers to every position. 00:04:41.947 --> 00:04:46.148 Call them u and d: the length of the longest rise that starts there, 00:04:46.231 --> 00:04:49.088 and the length of the longest fall that starts there. 00:04:49.400 --> 00:04:52.327 At the second term, both of them are three. 00:04:53.123 --> 00:04:55.806 Now, does this sequence contain a run of four? 00:04:56.003 --> 00:04:58.288 It does. Two, five, 00:04:58.371 --> 00:05:03.945 eight, ten, at positions three, five, seven and nine, rising the whole way. 00:05:04.288 --> 00:05:06.100 And that was not luck either. 00:05:06.413 --> 00:05:11.012 Any ten distinct numbers contain four that rise, or four that fall. 00:05:11.208 --> 00:05:13.693 To see it, suppose they do not. 00:05:15.090 --> 00:05:17.852 Suppose there is no rising run of four anywhere, 00:05:17.935 --> 00:05:20.164 and no falling run of four either. 00:05:20.361 --> 00:05:25.644 Then every u is one, two or three, and so is every d. 00:05:26.440 --> 00:05:28.984 Two numbers, three choices each. 00:05:29.297 --> 00:05:33.323 Three times three is nine possible pairs, and there are the nine of them, 00:05:33.406 --> 00:05:34.940 one box apiece. 00:05:35.852 --> 00:05:39.859 But there are ten positions, and each position hands you one pair. 00:05:39.962 --> 00:05:42.274 Ten items, nine boxes. 00:05:43.070 --> 00:05:48.142 So two positions, i somewhere to the left of j, carry the identical pair. 00:05:48.225 --> 00:05:50.142 Same u, same d. 00:05:50.938 --> 00:05:52.530 And now it breaks. 00:05:52.726 --> 00:05:57.206 The numbers are all different, so either a i is below a j or above it. 00:05:57.289 --> 00:05:59.054 Suppose it is below. 00:05:59.538 --> 00:06:04.101 Take the longest rise starting at j, and stick a i on the front of it. 00:06:04.298 --> 00:06:08.478 That is a rise starting at i, and it is one term longer. 00:06:08.675 --> 00:06:13.087 So u i beats u j, when they were supposed to be equal. 00:06:14.302 --> 00:06:16.645 If a i is the larger one instead, 00:06:16.728 --> 00:06:20.677 the very same trick runs downhill and d i beats d j. 00:06:20.873 --> 00:06:25.263 Either way the two pairs could not have matched, so the assumption is dead. 00:06:25.366 --> 00:06:29.431 There has to be a monotone run of four somewhere in that sequence. 00:06:29.856 --> 00:06:32.341 And ten was not an arbitrary number. 00:06:32.538 --> 00:06:35.856 Nine positions fit into nine boxes without any fight at all, 00:06:35.939 --> 00:06:40.793 so ten is the first length that forces the issue. Three by three, plus one. 00:06:41.936 --> 00:06:46.035 One more, and this time the boxes are not objects at all. 00:06:46.232 --> 00:06:48.809 They are stretches of a line, and that turns out 00:06:48.809 --> 00:06:52.815 to change nothing about the argument and everything about what it can prove. 00:06:53.612 --> 00:06:57.746 The subject is approximating an irrational number by a fraction. 00:06:57.942 --> 00:07:02.399 Getting close to the square root of two is easy: take enough decimal places. 00:07:02.482 --> 00:07:07.068 The real question is how close you can get while keeping the denominator small. 00:07:07.865 --> 00:07:10.165 Dirichlet's answer is startling. 00:07:10.361 --> 00:07:13.564 For every whole number N there is a fraction p over q, 00:07:13.647 --> 00:07:19.081 with q no bigger than N, that sits within one over q times N of your number. 00:07:19.878 --> 00:07:24.616 And since q is at most N, that is within one over q squared. 00:07:24.928 --> 00:07:27.076 A denominator of five buying an error 00:07:27.076 --> 00:07:31.848 under one twenty fifth is not what randomly chosen fractions do for you. 00:07:33.245 --> 00:07:34.836 So, the boxes. 00:07:35.149 --> 00:07:39.585 Let N be five, and take the first six multiples of root two: 00:07:39.781 --> 00:07:45.202 nought, one point four one, two point eight three, four point two four, 00:07:45.285 --> 00:07:48.908 five point six six, and seven point zero seven. 00:07:49.217 --> 00:07:50.866 Now throw away the whole number part 00:07:50.866 --> 00:07:53.873 of each one and keep only what comes after the point. 00:07:54.070 --> 00:07:58.843 Six numbers, every one of them somewhere between nought and one, and here they are. 00:07:59.384 --> 00:08:03.213 And cut that stretch from nought to one into five equal pieces. 00:08:03.296 --> 00:08:05.026 Those are the boxes. 00:08:05.223 --> 00:08:07.439 Six numbers, five intervals, 00:08:07.522 --> 00:08:11.017 and I do not have to look at the numbers to know what happens next. 00:08:11.814 --> 00:08:13.997 Two of the six share an interval. 00:08:14.194 --> 00:08:15.379 Here they are: 00:08:15.483 --> 00:08:18.070 the very first one, which is nought exactly, 00:08:18.153 --> 00:08:21.936 and the last one, seven point zero seven with the seven thrown away. 00:08:22.019 --> 00:08:24.666 Both of them inside the leftmost box. 00:08:25.370 --> 00:08:30.328 And two numbers sitting in one interval of width a fifth are less than a fifth apart. 00:08:30.525 --> 00:08:33.182 That is everything the boxes were ever for. 00:08:33.265 --> 00:08:35.437 From here it is arithmetic. 00:08:36.415 --> 00:08:38.065 Write it out in general. 00:08:38.261 --> 00:08:41.626 The items are these N plus one fractional parts, 00:08:41.709 --> 00:08:45.205 one for each multiple of alpha from nought up to N. 00:08:45.816 --> 00:08:48.429 The boxes are the N intervals. 00:08:48.625 --> 00:08:50.123 More numbers than intervals, 00:08:50.123 --> 00:08:56.112 so two of them land in the same one: call their indices i and j, with i the smaller. 00:08:56.195 --> 00:09:00.039 The two fractional parts differ by less than one over N. 00:09:00.742 --> 00:09:03.518 Now unpack what a fractional part is. 00:09:03.622 --> 00:09:06.766 It is the number itself, minus some whole number. 00:09:06.849 --> 00:09:11.981 So that small difference is j alpha minus i alpha, with an integer taken off it. 00:09:13.033 --> 00:09:18.302 Give those two things names. Let q be j minus i, which is between one and N, 00:09:18.385 --> 00:09:21.184 and let p be the integer that came off. 00:09:21.288 --> 00:09:25.584 Then q alpha minus p is less than one over N in size. 00:09:26.125 --> 00:09:28.294 Divide the whole line through by q. 00:09:28.377 --> 00:09:33.612 Alpha minus p over q is less than one over q N. And q is at most N, 00:09:33.695 --> 00:09:38.990 so one over q N is at most one over q squared, which is the theorem. 00:09:40.042 --> 00:09:41.561 Put our own numbers in. 00:09:41.644 --> 00:09:46.634 The two indices were nought and five, so q is five, and p works out at seven. 00:09:46.717 --> 00:09:49.435 Seven fifths, which is one point four. 00:09:49.918 --> 00:09:52.041 The true error is a hundredth and a bit, 00:09:52.124 --> 00:09:54.967 comfortably inside the one twenty fifth we were promised. 00:09:55.050 --> 00:09:58.949 And run the whole thing again with a larger N and you get a different fraction, 00:09:59.032 --> 00:10:00.217 a better one. 00:10:00.758 --> 00:10:02.383 Which means an irrational number 00:10:02.383 --> 00:10:06.494 has infinitely many fractions chasing it this closely, forever. 00:10:06.598 --> 00:10:09.977 And the boxes that proved it were five stretches of a line. 00:10:11.374 --> 00:10:14.695 Three theorems, then, and three choices of box. 00:10:14.892 --> 00:10:15.761 In the first, 00:10:15.844 --> 00:10:20.091 the items were people and the boxes were the possible answers to a question, 00:10:20.174 --> 00:10:24.250 once we had noticed that two of those answers could never both be used. 00:10:25.047 --> 00:10:26.916 In the second, the items were positions 00:10:26.916 --> 00:10:31.317 in a sequence, and the boxes were pairs of numbers we had to invent from nothing. 00:10:31.513 --> 00:10:32.324 In the third, 00:10:32.407 --> 00:10:36.831 the items were multiples of alpha, and the boxes were stretches of a line. 00:10:37.628 --> 00:10:41.077 And the sentence at the end was the same all three times. 00:10:41.273 --> 00:10:44.629 More items than boxes, so two share a box. 00:10:44.942 --> 00:10:46.647 It was never the hard part. 00:10:46.730 --> 00:10:48.286 The boxes were.