# The Pigeonhole Principle: Choosing the Boxes

> The pigeonhole principle takes one line to state and one sentence to prove, and then proves things that look nothing like it. This lecture states it once, over four boxes and five items, and spends the rest of its time on three consequences: that any group of people contains two who know the same number of others in the group, that any ten distinct numbers contain four that rise or four that fall, and Dirichlet's theorem that every irrational number is chased by fractions to within one over the denominator squared. Each proof is a single sentence once the boxes have been chosen, so each time the boxes are built on screen, including the first choice that fails and has to be repaired. For a first year student meeting combinatorial argument for the first time.

- Canonical watch page: [The Pigeonhole Principle: Choosing the Boxes](https://academa.ai/lectures/pigeonhole-principle-boxes)
- Publisher: [Academa, Inc.](https://academa.ai)
- Subject: Mathematics
- Published: 2026-08-28T22:51:39.000Z
- Updated: 2026-08-28T22:51:39.000Z
- Duration: PT652S (10 minutes 52 seconds)
- Chapters: 4
- Views: 0
- Language: en-US
- Access: Free
- Video stream: [HLS content](https://academa.ai/media/l/01M14TZDF7NPG7EJ913X21HSZK/0/dark/master.m3u8)
- Audiovisual record: [Semantic JSON](https://academa.ai/media/l/01M14TZDF7NPG7EJ913X21HSZK/0/semantic.json)
- Thumbnail: [Image](https://academa.ai/media/l/01M14TZDF7NPG7EJ913X21HSZK/0/dark/poster.jpg)

## Description

State the pigeonhole principle in one line, then watch it prove three things that look nothing like it. The trick is choosing the boxes.

## Chapters

- [00:00–01:34.098 · One Line, Then the Hard Part](https://academa.ai/lectures/pigeonhole-principle-boxes?t=0)
- [01:34.098–03:50.068 · Six People at a Party](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.0981875)
- [03:50.068–06:35.788 · Ten Numbers, and a Run of Four](https://academa.ai/lectures/pigeonhole-principle-boxes?t=230.0681875)
- [06:35.788–10:52 · Boxes That Are Intervals](https://academa.ai/lectures/pigeonhole-principle-boxes?t=395.78841666666665)

## Transcript

### [00:00 · One Line, Then the Hard Part](https://academa.ai/lectures/pigeonhole-principle-boxes?t=0)

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.

### [01:34.098 · Six People at a Party](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.0981875)

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.

### [03:50.068 · Ten Numbers, and a Run of Four](https://academa.ai/lectures/pigeonhole-principle-boxes?t=230.0681875)

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.

### [06:35.788 · Boxes That Are Intervals](https://academa.ai/lectures/pigeonhole-principle-boxes?t=395.78841666666665)

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.

## About Academa, Inc.

Academa makes technical knowledge easier to understand through visual lectures and lets learners request new lecture videos on the topics they need.

## Complete audiovisual record

Immutable source: [semantic.json](https://academa.ai/media/l/01M14TZDF7NPG7EJ913X21HSZK/0/semantic.json)

Record version: 1. Render attempt: 0.

### How to read this timeline

Each scene owns its object identifiers. A beat's board is the complete board when listed, empty when marked empty, and unchanged from the nearest earlier listed board in the same scene when marked unchanged. Action times are absolute positions in the published video.

### Scene 1: [One Line, Then the Hard Part](https://academa.ai/lectures/pigeonhole-principle-boxes?t=0)

Span: 00:00–01:34.098 (0s–94.0981875s).

#### Objects

- bins: a Polygon \[gray\] drawn in pens (vertices=((0.4, 0.5), (2.0, 0.5), (2.0, 1.9), (0.4, 1.9)), filled=False)
- bins\_2: a Polygon \[gray\] drawn in pens (vertices=((2.2, 0.5), (3.8000000000000003, 0.5), (3.8000000000000003, 1.…, filled=False)
- bins\_3: a Polygon \[gray\] drawn in pens (vertices=((4.0, 0.5), (5.6, 0.5), (5.6, 1.9), (4.0, 1.9)), filled=False)
- bins\_4: a Polygon \[gray\] drawn in pens (vertices=((5.8, 0.5), (7.4, 0.5), (7.4, 1.9), (5.8, 1.9)), filled=False)
- card: a Title that says "Discrete Mathematics — The Pigeonhole Principle: Choosing the Boxes"
- chips: a Point \[blue\] drawn in pens (location=(1.2, 1.2))
- chips\_2: a Point \[blue\] drawn in pens (location=(3.0, 1.2))
- chips\_3: a Point \[yellow\] drawn in pens (location=(4.5, 1.2))
- chips\_4: a Point \[yellow\] drawn in pens (location=(5.1, 1.2))
- chips\_5: a Point \[blue\] drawn in pens (location=(6.6, 1.2))
- head\_plan: a Heading that says "Three Things It Proves"
- head\_state: a Heading that says "The Whole Principle"
- note: a Panel that says "Nothing in that line tells you what the items are or what the boxes are. Choosing them is the whole of the work."
- oneline: a Math \[text\] that says "$lt.eq 1 thin upright("per box") arrow.r.double lt.eq n thin upright("items")$"
- pens: a Figure (x\_range=(0.0, 8.0), y\_range=(0.0, 2.6), aspect=(8.0, 2.6))
- plan: a Block \[text\] that says "Two people at any party know the same number of people there. Any ten distinct numbers hide four that rise, or four that fall. Every irrational number is chased by fractions closer than it deserves."
- statement: a Math \[text\] that says "$n + 1 thin upright("items,") thin n thin upright("boxes") arrow.r.double upright("two share")$"

#### Beats

##### [00:00](https://academa.ai/lectures/pigeonhole-principle-boxes?t=0)

Narration: 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.

Board: Empty.

Actions:
- [00:00](https://academa.ai/lectures/pigeonhole-principle-boxes?t=0): card is shown on the screen, written out.
- [00:1.5](https://academa.ai/lectures/pigeonhole-principle-boxes?t=1.5): card: enter:write-left-to-right.
- [00:14.664](https://academa.ai/lectures/pigeonhole-principle-boxes?t=14.6635): card is hidden from the screen — left the board.

##### [00:15.864](https://academa.ai/lectures/pigeonhole-principle-boxes?t=15.8635)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [00:15.864](https://academa.ai/lectures/pigeonhole-principle-boxes?t=15.8635): head\_state is shown on the screen, written out.
- [00:15.864](https://academa.ai/lectures/pigeonhole-principle-boxes?t=15.8635): pens is shown on the screen, written out.
- [00:17.802](https://academa.ai/lectures/pigeonhole-principle-boxes?t=17.802): bins is shown on the screen, written out.
- [00:17.922](https://academa.ai/lectures/pigeonhole-principle-boxes?t=17.922): bins\_2 is shown on the screen, written out.
- [00:18.042](https://academa.ai/lectures/pigeonhole-principle-boxes?t=18.041999999999998): bins\_3 is shown on the screen, written out.
- [00:18.162](https://academa.ai/lectures/pigeonhole-principle-boxes?t=18.162): bins\_4 is shown on the screen, written out.
- [00:19.195](https://academa.ai/lectures/pigeonhole-principle-boxes?t=19.195): chips is shown on the screen, written out.
- [00:19.375](https://academa.ai/lectures/pigeonhole-principle-boxes?t=19.375): chips\_2 is shown on the screen, written out.
- [00:19.555](https://academa.ai/lectures/pigeonhole-principle-boxes?t=19.555): chips\_3 is shown on the screen, written out.
- [00:19.735](https://academa.ai/lectures/pigeonhole-principle-boxes?t=19.735): chips\_4 is shown on the screen, written out.
- [00:19.915](https://academa.ai/lectures/pigeonhole-principle-boxes?t=19.915): chips\_5 is shown on the screen, written out.

##### [00:26.285](https://academa.ai/lectures/pigeonhole-principle-boxes?t=26.2855)

Narration: 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.

Board: pens — a Figure (x\_range=(0.0, 8.0), y\_range=(0.0, 2.6), aspect=(8.0, 2.6)); head\_state — a Heading that says "The Whole Principle"; bins — a Polygon \[gray\] drawn in pens (vertices=((0.4, 0.5), (2.0, 0.5), (2.0, 1.9), (0.4, 1.9)), filled=False); bins\_2 — a Polygon \[gray\] drawn in pens (vertices=((2.2, 0.5), (3.8000000000000003, 0.5), (3.8000000000000003, 1.…, filled=False); bins\_3 — a Polygon \[gray\] drawn in pens (vertices=((4.0, 0.5), (5.6, 0.5), (5.6, 1.9), (4.0, 1.9)), filled=False); bins\_4 — a Polygon \[gray\] drawn in pens (vertices=((5.8, 0.5), (7.4, 0.5), (7.4, 1.9), (5.8, 1.9)), filled=False); chips — a Point \[blue\] drawn in pens (location=(1.2, 1.2)); chips\_2 — a Point \[blue\] drawn in pens (location=(3.0, 1.2)); chips\_3 — a Point \[yellow\] drawn in pens (location=(4.5, 1.2)); chips\_4 — a Point \[yellow\] drawn in pens (location=(5.1, 1.2)); chips\_5 — a Point \[blue\] drawn in pens (location=(6.6, 1.2))

Actions:
- [00:27.62](https://academa.ai/lectures/pigeonhole-principle-boxes?t=27.62): pens moves to a new place on the board.
- [00:27.62](https://academa.ai/lectures/pigeonhole-principle-boxes?t=27.62): statement is shown on the screen, written out.

##### [00:34.745](https://academa.ai/lectures/pigeonhole-principle-boxes?t=34.745)

Narration: 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.

Board: statement — a Math \[text\] that says "$n + 1 thin upright("items,") thin n thin upright("boxes") arrow.r.double upright("two share")$"; pens — a Figure (x\_range=(0.0, 8.0), y\_range=(0.0, 2.6), aspect=(8.0, 2.6)); head\_state — a Heading that says "The Whole Principle"; bins — a Polygon \[gray\] drawn in pens (vertices=((0.4, 0.5), (2.0, 0.5), (2.0, 1.9), (0.4, 1.9)), filled=False); bins\_2 — a Polygon \[gray\] drawn in pens (vertices=((2.2, 0.5), (3.8000000000000003, 0.5), (3.8000000000000003, 1.…, filled=False); bins\_3 — a Polygon \[gray\] drawn in pens (vertices=((4.0, 0.5), (5.6, 0.5), (5.6, 1.9), (4.0, 1.9)), filled=False); bins\_4 — a Polygon \[gray\] drawn in pens (vertices=((5.8, 0.5), (7.4, 0.5), (7.4, 1.9), (5.8, 1.9)), filled=False); chips — a Point \[blue\] drawn in pens (location=(1.2, 1.2)); chips\_2 — a Point \[blue\] drawn in pens (location=(3.0, 1.2)); chips\_3 — a Point \[yellow\] drawn in pens (location=(4.5, 1.2)); chips\_4 — a Point \[yellow\] drawn in pens (location=(5.1, 1.2)); chips\_5 — a Point \[blue\] drawn in pens (location=(6.6, 1.2))

Actions:
- [00:35.987](https://academa.ai/lectures/pigeonhole-principle-boxes?t=35.987): oneline is shown on the screen, written out.
- [00:43.011](https://academa.ai/lectures/pigeonhole-principle-boxes?t=43.011): oneline (the "lt.eq n thin upright("items")" part) is emphasized.
- [00:46.68](https://academa.ai/lectures/pigeonhole-principle-boxes?t=46.68): oneline (the "lt.eq n thin upright("items")" part) is no longer emphasized.

##### [00:48.371](https://academa.ai/lectures/pigeonhole-principle-boxes?t=48.370999999999995)

Narration: 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.

Board: statement — a Math \[text\] that says "$n + 1 thin upright("items,") thin n thin upright("boxes") arrow.r.double upright("two share")$"; oneline — a Math \[text\] that says "$lt.eq 1 thin upright("per box") arrow.r.double lt.eq n thin upright("items")$"; pens — a Figure (x\_range=(0.0, 8.0), y\_range=(0.0, 2.6), aspect=(8.0, 2.6)); head\_state — a Heading that says "The Whole Principle"; bins — a Polygon \[gray\] drawn in pens (vertices=((0.4, 0.5), (2.0, 0.5), (2.0, 1.9), (0.4, 1.9)), filled=False); bins\_2 — a Polygon \[gray\] drawn in pens (vertices=((2.2, 0.5), (3.8000000000000003, 0.5), (3.8000000000000003, 1.…, filled=False); bins\_3 — a Polygon \[gray\] drawn in pens (vertices=((4.0, 0.5), (5.6, 0.5), (5.6, 1.9), (4.0, 1.9)), filled=False); bins\_4 — a Polygon \[gray\] drawn in pens (vertices=((5.8, 0.5), (7.4, 0.5), (7.4, 1.9), (5.8, 1.9)), filled=False); chips — a Point \[blue\] drawn in pens (location=(1.2, 1.2)); chips\_2 — a Point \[blue\] drawn in pens (location=(3.0, 1.2)); chips\_3 — a Point \[yellow\] drawn in pens (location=(4.5, 1.2)); chips\_4 — a Point \[yellow\] drawn in pens (location=(5.1, 1.2)); chips\_5 — a Point \[blue\] drawn in pens (location=(6.6, 1.2))

Actions:
- [00:49.753](https://academa.ai/lectures/pigeonhole-principle-boxes?t=49.75299999999999): note is shown on the screen, written out.
- [00:56.138](https://academa.ai/lectures/pigeonhole-principle-boxes?t=56.138): note (the "Choosing them is the whole of the work." part) is emphasized.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): head\_state is hidden from the screen — left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): note is hidden from the screen — left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): oneline is hidden from the screen — left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): pens is hidden from the screen — left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): bins is hidden from the screen — pens left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): bins\_2 is hidden from the screen — pens left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): bins\_3 is hidden from the screen — pens left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): bins\_4 is hidden from the screen — pens left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): chips is hidden from the screen — pens left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): chips\_2 is hidden from the screen — pens left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): chips\_3 is hidden from the screen — pens left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): chips\_4 is hidden from the screen — pens left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): chips\_5 is hidden from the screen — pens left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): statement is hidden from the screen — left the board.
- [00:58.901](https://academa.ai/lectures/pigeonhole-principle-boxes?t=58.9015): note (the "Choosing them is the whole of the work." part) is no longer emphasized.

##### [00:59.501](https://academa.ai/lectures/pigeonhole-principle-boxes?t=59.50149999999999)

Narration: 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.

Board: Empty.

Actions:
- [00:59.501](https://academa.ai/lectures/pigeonhole-principle-boxes?t=59.50149999999999): head\_plan is shown on the screen, written out.
- [01:0.337](https://academa.ai/lectures/pigeonhole-principle-boxes?t=60.336999999999996): plan is shown on the screen, written out.

##### [01:7.822](https://academa.ai/lectures/pigeonhole-principle-boxes?t=67.82199999999999)

Narration: 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.

Board: plan — a Block \[text\] that says "Two people at any party know the same number of people there. Any ten distinct numbers hide four that rise, or four that fall. Every irrational number is chased by fractions closer than it deserves."; head\_plan — a Heading that says "Three Things It Proves"

Actions:
- [01:9.064](https://academa.ai/lectures/pigeonhole-principle-boxes?t=69.064): plan (the "know the same number of people there" part) is emphasized.
- [01:14.672](https://academa.ai/lectures/pigeonhole-principle-boxes?t=74.672): plan (the "four that rise, or four that fall" part) is emphasized.
- [01:14.672](https://academa.ai/lectures/pigeonhole-principle-boxes?t=74.672): plan (the "know the same number of people there" part) is no longer emphasized.
- [01:19.861](https://academa.ai/lectures/pigeonhole-principle-boxes?t=79.86099999999999): plan (the "chased by fractions closer than it deserves" part) is emphasized.
- [01:19.861](https://academa.ai/lectures/pigeonhole-principle-boxes?t=79.86099999999999): plan (the "four that rise, or four that fall" part) is no longer emphasized.
- [01:22.509](https://academa.ai/lectures/pigeonhole-principle-boxes?t=82.50899999999999): plan (the "chased by fractions closer than it deserves" part) is no longer emphasized.

##### [01:24.037](https://academa.ai/lectures/pigeonhole-principle-boxes?t=84.0375)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [01:33.057](https://academa.ai/lectures/pigeonhole-principle-boxes?t=93.05652083333332): head\_plan is hidden from the screen — left the board.
- [01:33.057](https://academa.ai/lectures/pigeonhole-principle-boxes?t=93.05652083333332): plan is hidden from the screen — left the board.

### Scene 2: [Six People at a Party](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.0981875)

Span: 01:34.098–03:50.068 (94.0981875s–230.0681875s).

#### Objects

- bins: a Polygon \[gray\] drawn in slots (vertices=((0.35, 0.8), (1.35, 0.8), (1.35, 2.0), (0.35, 2.0)), filled=False)
- bins\_2: a Polygon \[gray\] drawn in slots (vertices=((1.5, 0.8), (2.5, 0.8), (2.5, 2.0), (1.5, 2.0)), filled=False)
- bins\_3: a Polygon \[gray\] drawn in slots (vertices=((2.65, 0.8), (3.65, 0.8), (3.65, 2.0), (2.65, 2.0)), filled=False)
- bins\_4: a Polygon \[gray\] drawn in slots (vertices=((3.8, 0.8), (4.8, 0.8), (4.8, 2.0), (3.8, 2.0)), filled=False)
- bins\_5: a Polygon \[gray\] drawn in slots (vertices=((4.95, 0.8), (5.95, 0.8), (5.95, 2.0), (4.95, 2.0)), filled=False)
- bins\_6: a Polygon \[gray\] drawn in slots (vertices=((6.1, 0.8), (7.1, 0.8), (7.1, 2.0), (6.1, 2.0)), filled=False)
- folk: a Point \[blue\] labelled "A" drawn in party (location=(8.266365894244634e-17, 1.35))
- folk\_2: a Point \[blue\] labelled "B" drawn in party (location=(-1.1691342951089922, 0.6749999999999999))
- folk\_3: a Point \[blue\] labelled "C" drawn in party (location=(-1.1691342951089922, -0.6750000000000002))
- folk\_4: a Point \[blue\] labelled "D" drawn in party (location=(-2.4799097682733903e-16, -1.35))
- folk\_5: a Point \[blue\] labelled "E" drawn in party (location=(1.1691342951089918, -0.6750000000000006))
- folk\_6: a Point \[blue\] labelled "F" drawn in party (location=(1.1691342951089922, 0.6749999999999999))
- guests: a Point \[blue\] drawn in slots (location=(0.85, 1.4))
- guests\_2: a Point \[blue\] drawn in slots (location=(2.0, 1.4))
- guests\_3: a Point \[yellow\] drawn in slots (location=(2.9, 1.4))
- guests\_4: a Point \[yellow\] drawn in slots (location=(3.4, 1.4))
- guests\_5: a Point \[blue\] drawn in slots (location=(4.3, 1.4))
- guests\_6: a Point \[blue\] drawn in slots (location=(5.45, 1.4))
- head\_boxes: a Heading that says "Choosing the Boxes"
- head\_party: a Heading that says "Six People at a Party"
- links: a Line \[gray\] drawn in party (start=(8.266365894244634e-17, 1.35), end=(-2.4799097682733903e-16, -1.35))
- links\_2: a Line \[gray\] drawn in party (start=(-1.1691342951089922, 0.6749999999999999), end=(-2.4799097682733903e-16, -1.35))
- links\_3: a Line \[gray\] drawn in party (start=(-1.1691342951089922, 0.6749999999999999), end=(1.1691342951089918, -0.6750000000000006))
- links\_4: a Line \[gray\] drawn in party (start=(-1.1691342951089922, -0.6750000000000002), end=(1.1691342951089918, -0.6750000000000006))
- links\_5: a Line \[gray\] drawn in party (start=(-1.1691342951089922, -0.6750000000000002), end=(1.1691342951089922, 0.6749999999999999))
- links\_6: a Line \[gray\] drawn in party (start=(-2.4799097682733903e-16, -1.35), end=(1.1691342951089922, 0.6749999999999999))
- links\_7: a Line \[gray\] drawn in party (start=(1.1691342951089918, -0.6750000000000006), end=(1.1691342951089922, 0.6749999999999999))
- party: a Figure (x\_range=(-2.0, 2.0), y\_range=(-1.85, 1.85), aspect=(4.0, 3.7))
- seen: a Tex \[text\] that says "$B$ and $C$ both know two. So do $D$, $E$ and $F$ at three."
- slots: a Figure (x\_range=(0.0, 7.45), y\_range=(0.0, 2.6), aspect=(7.45, 2.6))
- tags: a Math \[text\] that says "$0$" drawn in slots
- tags\_2: a Math \[text\] that says "$1$" drawn in slots
- tags\_3: a Math \[text\] that says "$2$" drawn in slots
- tags\_4: a Math \[text\] that says "$3$" drawn in slots
- tags\_5: a Math \[text\] that says "$4$" drawn in slots
- tags\_6: a Math \[text\] that says "$5$" drawn in slots
- verdict: a Tex \[text\] that says "Two people share a count."
- work: a Derivation \[text\] that says "$upright("count") &in brace.l 0, 1, 2, dots, n - 1 brace.r \\ n thin upright("people") &arrow.r n thin upright("boxes") \\ upright("some count") = 0 &arrow.r.double upright("no count") = n - 1 \\ n thin upright("people") &arrow.r n - 1 thin up…$"

#### Beats

##### [01:34.098](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.0981875)

Narration: 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.

Board: Empty.

Actions:
- [01:34.098](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.0981875): head\_party is shown on the screen, written out.
- [01:34.098](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.0981875): party is shown on the screen, written out.
- [01:34.133](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.13318749999999): folk is shown on the screen, written out.
- [01:34.273](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.27318749999999): folk\_2 is shown on the screen, written out.
- [01:34.413](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.41318749999999): folk\_3 is shown on the screen, written out.
- [01:34.553](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.55318749999999): folk\_4 is shown on the screen, written out.
- [01:34.693](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.6931875): folk\_5 is shown on the screen, written out.
- [01:34.833](https://academa.ai/lectures/pigeonhole-principle-boxes?t=94.8331875): folk\_6 is shown on the screen, written out.
- [01:43.955](https://academa.ai/lectures/pigeonhole-principle-boxes?t=103.9551875): links is shown on the screen, written out.
- [01:44.075](https://academa.ai/lectures/pigeonhole-principle-boxes?t=104.0751875): links\_2 is shown on the screen, written out.
- [01:44.195](https://academa.ai/lectures/pigeonhole-principle-boxes?t=104.19518749999999): links\_3 is shown on the screen, written out.
- [01:44.315](https://academa.ai/lectures/pigeonhole-principle-boxes?t=104.3151875): links\_4 is shown on the screen, written out.
- [01:44.435](https://academa.ai/lectures/pigeonhole-principle-boxes?t=104.4351875): links\_5 is shown on the screen, written out.
- [01:44.555](https://academa.ai/lectures/pigeonhole-principle-boxes?t=104.55518749999999): links\_6 is shown on the screen, written out.
- [01:44.675](https://academa.ai/lectures/pigeonhole-principle-boxes?t=104.67518749999999): links\_7 is shown on the screen, written out.

##### [01:45.2](https://academa.ai/lectures/pigeonhole-principle-boxes?t=105.1996875)

Narration: Now go round and count. A knows exactly one person here. B knows two. And C also knows two.

Board: party — a Figure (x\_range=(-2.0, 2.0), y\_range=(-1.85, 1.85), aspect=(4.0, 3.7)); head\_party — a Heading that says "Six People at a Party"; folk — a Point \[blue\] labelled "A" drawn in party (location=(8.266365894244634e-17, 1.35)); folk\_2 — a Point \[blue\] labelled "B" drawn in party (location=(-1.1691342951089922, 0.6749999999999999)); folk\_3 — a Point \[blue\] labelled "C" drawn in party (location=(-1.1691342951089922, -0.6750000000000002)); folk\_4 — a Point \[blue\] labelled "D" drawn in party (location=(-2.4799097682733903e-16, -1.35)); folk\_5 — a Point \[blue\] labelled "E" drawn in party (location=(1.1691342951089918, -0.6750000000000006)); folk\_6 — a Point \[blue\] labelled "F" drawn in party (location=(1.1691342951089922, 0.6749999999999999)); links — a Line \[gray\] drawn in party (start=(8.266365894244634e-17, 1.35), end=(-2.4799097682733903e-16, -1.35)); links\_2 — a Line \[gray\] drawn in party (start=(-1.1691342951089922, 0.6749999999999999), end=(-2.4799097682733903e-16, -1.35)); links\_3 — a Line \[gray\] drawn in party (start=(-1.1691342951089922, 0.6749999999999999), end=(1.1691342951089918, -0.6750000000000006)); links\_4 — a Line \[gray\] drawn in party (start=(-1.1691342951089922, -0.6750000000000002), end=(1.1691342951089918, -0.6750000000000006)); links\_5 — a Line \[gray\] drawn in party (start=(-1.1691342951089922, -0.6750000000000002), end=(1.1691342951089922, 0.6749999999999999)); links\_6 — a Line \[gray\] drawn in party (start=(-2.4799097682733903e-16, -1.35), end=(1.1691342951089922, 0.6749999999999999)); links\_7 — a Line \[gray\] drawn in party (start=(1.1691342951089918, -0.6750000000000006), end=(1.1691342951089922, 0.6749999999999999))

Actions:
- [01:47.933](https://academa.ai/lectures/pigeonhole-principle-boxes?t=107.93318749999999): folk: one name gives way to another over the same drawing (label\_becomes).
- [01:49.489](https://academa.ai/lectures/pigeonhole-principle-boxes?t=109.4891875): folk\_2: one name gives way to another over the same drawing (label\_becomes).
- [01:50.615](https://academa.ai/lectures/pigeonhole-principle-boxes?t=110.61518749999999): folk\_3: one name gives way to another over the same drawing (label\_becomes).

##### [01:52.255](https://academa.ai/lectures/pigeonhole-principle-boxes?t=112.25468749999999)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [01:54.002](https://academa.ai/lectures/pigeonhole-principle-boxes?t=114.00218749999999): folk\_4: one name gives way to another over the same drawing (label\_becomes).
- [01:54.402](https://academa.ai/lectures/pigeonhole-principle-boxes?t=114.4021875): folk\_5: one name gives way to another over the same drawing (label\_becomes).
- [01:55.202](https://academa.ai/lectures/pigeonhole-principle-boxes?t=115.2021875): folk\_6: one name gives way to another over the same drawing (label\_becomes).
- [01:59.876](https://academa.ai/lectures/pigeonhole-principle-boxes?t=119.8761875): seen is shown on the screen, written out.

##### [02:1.823](https://academa.ai/lectures/pigeonhole-principle-boxes?t=121.82318749999999)

Narration: 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.

Board: party — a Figure (x\_range=(-2.0, 2.0), y\_range=(-1.85, 1.85), aspect=(4.0, 3.7)); seen — a Tex \[text\] that says "$B$ and $C$ both know two. So do $D$, $E$ and $F$ at three."; head\_party — a Heading that says "Six People at a Party"; folk — a Point \[blue\] labelled "A" drawn in party (location=(8.266365894244634e-17, 1.35)); folk\_2 — a Point \[blue\] labelled "B" drawn in party (location=(-1.1691342951089922, 0.6749999999999999)); folk\_3 — a Point \[blue\] labelled "C" drawn in party (location=(-1.1691342951089922, -0.6750000000000002)); folk\_4 — a Point \[blue\] labelled "D" drawn in party (location=(-2.4799097682733903e-16, -1.35)); folk\_5 — a Point \[blue\] labelled "E" drawn in party (location=(1.1691342951089918, -0.6750000000000006)); folk\_6 — a Point \[blue\] labelled "F" drawn in party (location=(1.1691342951089922, 0.6749999999999999)); links — a Line \[gray\] drawn in party (start=(8.266365894244634e-17, 1.35), end=(-2.4799097682733903e-16, -1.35)); links\_2 — a Line \[gray\] drawn in party (start=(-1.1691342951089922, 0.6749999999999999), end=(-2.4799097682733903e-16, -1.35)); links\_3 — a Line \[gray\] drawn in party (start=(-1.1691342951089922, 0.6749999999999999), end=(1.1691342951089918, -0.6750000000000006)); links\_4 — a Line \[gray\] drawn in party (start=(-1.1691342951089922, -0.6750000000000002), end=(1.1691342951089918, -0.6750000000000006)); links\_5 — a Line \[gray\] drawn in party (start=(-1.1691342951089922, -0.6750000000000002), end=(1.1691342951089922, 0.6749999999999999)); links\_6 — a Line \[gray\] drawn in party (start=(-2.4799097682733903e-16, -1.35), end=(1.1691342951089922, 0.6749999999999999)); links\_7 — a Line \[gray\] drawn in party (start=(1.1691342951089918, -0.6750000000000006), end=(1.1691342951089922, 0.6749999999999999))

Actions:
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): head\_party is hidden from the screen — left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): party is hidden from the screen — left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): folk is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): folk\_2 is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): folk\_3 is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): folk\_4 is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): folk\_5 is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): folk\_6 is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): links is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): links\_2 is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): links\_3 is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): links\_4 is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): links\_5 is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): links\_6 is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): links\_7 is hidden from the screen — party left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): seen is hidden from the screen — left the board.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): slots is shown on the screen, written out.
- [02:14.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.1071875): bins is shown on the screen, written out.
- [02:14.207](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.2071875): bins\_2 is shown on the screen, written out.
- [02:14.407](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.4071875): bins\_3 is shown on the screen, written out.
- [02:14.707](https://academa.ai/lectures/pigeonhole-principle-boxes?t=134.7071875): bins\_4 is shown on the screen, written out.
- [02:15.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=135.1071875): bins\_5 is shown on the screen, written out.

##### [02:15.307](https://academa.ai/lectures/pigeonhole-principle-boxes?t=135.3071875)

Narration: 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.

Board: slots — a Figure (x\_range=(0.0, 7.45), y\_range=(0.0, 2.6), aspect=(7.45, 2.6)); bins — a Polygon \[gray\] drawn in slots (vertices=((0.35, 0.8), (1.35, 0.8), (1.35, 2.0), (0.35, 2.0)), filled=False); bins\_2 — a Polygon \[gray\] drawn in slots (vertices=((1.5, 0.8), (2.5, 0.8), (2.5, 2.0), (1.5, 2.0)), filled=False); bins\_3 — a Polygon \[gray\] drawn in slots (vertices=((2.65, 0.8), (3.65, 0.8), (3.65, 2.0), (2.65, 2.0)), filled=False); bins\_4 — a Polygon \[gray\] drawn in slots (vertices=((3.8, 0.8), (4.8, 0.8), (4.8, 2.0), (3.8, 2.0)), filled=False); bins\_5 — a Polygon \[gray\] drawn in slots (vertices=((4.95, 0.8), (5.95, 0.8), (5.95, 2.0), (4.95, 2.0)), filled=False)

Actions:
- [02:15.307](https://academa.ai/lectures/pigeonhole-principle-boxes?t=135.3071875): head\_boxes is shown on the screen, written out.
- [02:15.607](https://academa.ai/lectures/pigeonhole-principle-boxes?t=135.6071875): bins\_6 is shown on the screen, written out.
- [02:16.207](https://academa.ai/lectures/pigeonhole-principle-boxes?t=136.2071875): tags is shown on the screen, written out.
- [02:16.907](https://academa.ai/lectures/pigeonhole-principle-boxes?t=136.9071875): tags\_2 is shown on the screen, written out.
- [02:17.707](https://academa.ai/lectures/pigeonhole-principle-boxes?t=137.7071875): tags\_3 is shown on the screen, written out.
- [02:18.607](https://academa.ai/lectures/pigeonhole-principle-boxes?t=138.6071875): tags\_4 is shown on the screen, written out.
- [02:19.607](https://academa.ai/lectures/pigeonhole-principle-boxes?t=139.6071875): tags\_5 is shown on the screen, written out.
- [02:20.707](https://academa.ai/lectures/pigeonhole-principle-boxes?t=140.7071875): tags\_6 is shown on the screen, written out.
- [02:30.156](https://academa.ai/lectures/pigeonhole-principle-boxes?t=150.1561875): work is shown on the screen, written out.

##### [02:32.66](https://academa.ai/lectures/pigeonhole-principle-boxes?t=152.65968750000002)

Narration: 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.

Board: slots — a Figure (x\_range=(0.0, 7.45), y\_range=(0.0, 2.6), aspect=(7.45, 2.6)); head\_boxes — a Heading that says "Choosing the Boxes"; bins — a Polygon \[gray\] drawn in slots (vertices=((0.35, 0.8), (1.35, 0.8), (1.35, 2.0), (0.35, 2.0)), filled=False); bins\_2 — a Polygon \[gray\] drawn in slots (vertices=((1.5, 0.8), (2.5, 0.8), (2.5, 2.0), (1.5, 2.0)), filled=False); bins\_3 — a Polygon \[gray\] drawn in slots (vertices=((2.65, 0.8), (3.65, 0.8), (3.65, 2.0), (2.65, 2.0)), filled=False); bins\_4 — a Polygon \[gray\] drawn in slots (vertices=((3.8, 0.8), (4.8, 0.8), (4.8, 2.0), (3.8, 2.0)), filled=False); bins\_5 — a Polygon \[gray\] drawn in slots (vertices=((4.95, 0.8), (5.95, 0.8), (5.95, 2.0), (4.95, 2.0)), filled=False); bins\_6 — a Polygon \[gray\] drawn in slots (vertices=((6.1, 0.8), (7.1, 0.8), (7.1, 2.0), (6.1, 2.0)), filled=False); tags — a Math \[text\] that says "$0$" drawn in slots; tags\_2 — a Math \[text\] that says "$1$" drawn in slots; tags\_3 — a Math \[text\] that says "$2$" drawn in slots; tags\_4 — a Math \[text\] that says "$3$" drawn in slots; tags\_5 — a Math \[text\] that says "$4$" drawn in slots; tags\_6 — a Math \[text\] that says "$5$" drawn in slots

Actions:
- [02:40.381](https://academa.ai/lectures/pigeonhole-principle-boxes?t=160.3811875): work is shown on the screen, written out.

##### [02:49.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=169.1776875)

Narration: 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?

Board: Unchanged from the preceding beat in this scene.

Actions:
- [02:58.837](https://academa.ai/lectures/pigeonhole-principle-boxes?t=178.83718750000003): bins is indicated — a transient flash.
- [02:59.237](https://academa.ai/lectures/pigeonhole-principle-boxes?t=179.2371875): bins\_6 is indicated — a transient flash.

##### [03:2.154](https://academa.ai/lectures/pigeonhole-principle-boxes?t=182.1541875)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [03:2.456](https://academa.ai/lectures/pigeonhole-principle-boxes?t=182.4561875): work is shown on the screen, written out.

##### [03:16.652](https://academa.ai/lectures/pigeonhole-principle-boxes?t=196.6516875)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [03:18.405](https://academa.ai/lectures/pigeonhole-principle-boxes?t=198.4051875): bins\_6 is hidden from the screen.
- [03:18.405](https://academa.ai/lectures/pigeonhole-principle-boxes?t=198.4051875): tags\_6 is hidden from the screen.
- [03:21.91](https://academa.ai/lectures/pigeonhole-principle-boxes?t=201.9101875): work is shown on the screen, written out.

##### [03:26.069](https://academa.ai/lectures/pigeonhole-principle-boxes?t=206.0691875)

Narration: Six people, five boxes. And now the sentence from the beginning does all the remaining work, without being asked twice.

Board: slots — a Figure (x\_range=(0.0, 7.45), y\_range=(0.0, 2.6), aspect=(7.45, 2.6)); head\_boxes — a Heading that says "Choosing the Boxes"; bins — a Polygon \[gray\] drawn in slots (vertices=((0.35, 0.8), (1.35, 0.8), (1.35, 2.0), (0.35, 2.0)), filled=False); bins\_2 — a Polygon \[gray\] drawn in slots (vertices=((1.5, 0.8), (2.5, 0.8), (2.5, 2.0), (1.5, 2.0)), filled=False); bins\_3 — a Polygon \[gray\] drawn in slots (vertices=((2.65, 0.8), (3.65, 0.8), (3.65, 2.0), (2.65, 2.0)), filled=False); bins\_4 — a Polygon \[gray\] drawn in slots (vertices=((3.8, 0.8), (4.8, 0.8), (4.8, 2.0), (3.8, 2.0)), filled=False); bins\_5 — a Polygon \[gray\] drawn in slots (vertices=((4.95, 0.8), (5.95, 0.8), (5.95, 2.0), (4.95, 2.0)), filled=False); tags — a Math \[text\] that says "$0$" drawn in slots; tags\_2 — a Math \[text\] that says "$1$" drawn in slots; tags\_3 — a Math \[text\] that says "$2$" drawn in slots; tags\_4 — a Math \[text\] that says "$3$" drawn in slots; tags\_5 — a Math \[text\] that says "$4$" drawn in slots

Actions:
- [03:27.177](https://academa.ai/lectures/pigeonhole-principle-boxes?t=207.1771875): guests is shown on the screen, written out.
- [03:27.337](https://academa.ai/lectures/pigeonhole-principle-boxes?t=207.3371875): guests\_2 is shown on the screen, written out.
- [03:27.497](https://academa.ai/lectures/pigeonhole-principle-boxes?t=207.4971875): guests\_3 is shown on the screen, written out.
- [03:27.657](https://academa.ai/lectures/pigeonhole-principle-boxes?t=207.65718750000002): guests\_4 is shown on the screen, written out.
- [03:27.817](https://academa.ai/lectures/pigeonhole-principle-boxes?t=207.8171875): guests\_5 is shown on the screen, written out.
- [03:27.977](https://academa.ai/lectures/pigeonhole-principle-boxes?t=207.9771875): guests\_6 is shown on the screen, written out.

##### [03:33.896](https://academa.ai/lectures/pigeonhole-principle-boxes?t=213.8961875)

Narration: 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.

Board: slots — a Figure (x\_range=(0.0, 7.45), y\_range=(0.0, 2.6), aspect=(7.45, 2.6)); head\_boxes — a Heading that says "Choosing the Boxes"; bins — a Polygon \[gray\] drawn in slots (vertices=((0.35, 0.8), (1.35, 0.8), (1.35, 2.0), (0.35, 2.0)), filled=False); bins\_2 — a Polygon \[gray\] drawn in slots (vertices=((1.5, 0.8), (2.5, 0.8), (2.5, 2.0), (1.5, 2.0)), filled=False); bins\_3 — a Polygon \[gray\] drawn in slots (vertices=((2.65, 0.8), (3.65, 0.8), (3.65, 2.0), (2.65, 2.0)), filled=False); bins\_4 — a Polygon \[gray\] drawn in slots (vertices=((3.8, 0.8), (4.8, 0.8), (4.8, 2.0), (3.8, 2.0)), filled=False); bins\_5 — a Polygon \[gray\] drawn in slots (vertices=((4.95, 0.8), (5.95, 0.8), (5.95, 2.0), (4.95, 2.0)), filled=False); tags — a Math \[text\] that says "$0$" drawn in slots; tags\_2 — a Math \[text\] that says "$1$" drawn in slots; tags\_3 — a Math \[text\] that says "$2$" drawn in slots; tags\_4 — a Math \[text\] that says "$3$" drawn in slots; tags\_5 — a Math \[text\] that says "$4$" drawn in slots; guests — a Point \[blue\] drawn in slots (location=(0.85, 1.4)); guests\_2 — a Point \[blue\] drawn in slots (location=(2.0, 1.4)); guests\_3 — a Point \[yellow\] drawn in slots (location=(2.9, 1.4)); guests\_4 — a Point \[yellow\] drawn in slots (location=(3.4, 1.4)); guests\_5 — a Point \[blue\] drawn in slots (location=(4.3, 1.4)); guests\_6 — a Point \[blue\] drawn in slots (location=(5.45, 1.4))

Actions:
- [03:34.999](https://academa.ai/lectures/pigeonhole-principle-boxes?t=214.9991875): guests\_3 is indicated — a transient flash.
- [03:35.299](https://academa.ai/lectures/pigeonhole-principle-boxes?t=215.29918750000002): guests\_4 is indicated — a transient flash.
- [03:40.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=220.1071875): verdict is shown on the screen, written out.
- [03:42.975](https://academa.ai/lectures/pigeonhole-principle-boxes?t=222.9751875): A box is drawn around verdict.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): head\_boxes is hidden from the screen — left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): slots is hidden from the screen — left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): bins is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): bins\_2 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): bins\_3 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): bins\_4 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): bins\_5 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): tags is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): tags\_2 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): tags\_3 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): tags\_4 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): tags\_5 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): guests is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): guests\_2 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): guests\_3 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): guests\_4 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): guests\_5 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): guests\_6 is hidden from the screen — slots left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): verdict is hidden from the screen — left the board.
- [03:49.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=229.02652083333334): work is hidden from the screen — left the board.

### Scene 3: [Ten Numbers, and a Run of Four](https://academa.ai/lectures/pigeonhole-principle-boxes?t=230.0681875)

Span: 03:50.068–06:35.788 (230.0681875s–395.78841666666665s).

#### Objects

- cells: a Polygon \[gray\] drawn in grid (vertices=((0.75, 0.75), (1.75, 0.75), (1.75, 1.75), (0.75, 1.75)), filled=False)
- cells\_2: a Polygon \[gray\] drawn in grid (vertices=((1.9, 0.75), (2.9, 0.75), (2.9, 1.75), (1.9, 1.75)), filled=False)
- cells\_3: a Polygon \[gray\] drawn in grid (vertices=((3.05, 0.75), (4.05, 0.75), (4.05, 1.75), (3.05, 1.75)), filled=False)
- cells\_4: a Polygon \[gray\] drawn in grid (vertices=((0.75, 1.9), (1.75, 1.9), (1.75, 2.9), (0.75, 2.9)), filled=False)
- cells\_5: a Polygon \[gray\] drawn in grid (vertices=((1.9, 1.9), (2.9, 1.9), (2.9, 2.9), (1.9, 2.9)), filled=False)
- cells\_6: a Polygon \[gray\] drawn in grid (vertices=((3.05, 1.9), (4.05, 1.9), (4.05, 2.9), (3.05, 2.9)), filled=False)
- cells\_7: a Polygon \[gray\] drawn in grid (vertices=((0.75, 3.05), (1.75, 3.05), (1.75, 4.05), (0.75, 4.05)), filled=False)
- cells\_8: a Polygon \[gray\] drawn in grid (vertices=((1.9, 3.05), (2.9, 3.05), (2.9, 4.05), (1.9, 4.05)), filled=False)
- cells\_9: a Polygon \[gray\] drawn in grid (vertices=((3.05, 3.05), (4.05, 3.05), (4.05, 4.05), (3.05, 4.05)), filled=False)
- chips: a Point \[blue\] drawn in grid (location=(1.25, 1.25))
- chips\_10: a Point \[blue\] drawn in grid (location=(3.55, 3.55))
- chips\_2: a Point \[blue\] drawn in grid (location=(2.4, 1.25))
- chips\_3: a Point \[blue\] drawn in grid (location=(3.55, 1.25))
- chips\_4: a Point \[blue\] drawn in grid (location=(1.25, 2.4))
- chips\_5: a Point \[yellow\] drawn in grid (location=(2.1799999999999997, 2.4))
- chips\_6: a Point \[yellow\] drawn in grid (location=(2.62, 2.4))
- chips\_7: a Point \[blue\] drawn in grid (location=(3.55, 2.4))
- chips\_8: a Point \[blue\] drawn in grid (location=(1.25, 3.55))
- chips\_9: a Point \[blue\] drawn in grid (location=(2.4, 3.55))
- claim: a Tex \[text\] that says "Suppose no monotone run of four."
- col\_tags: a Math \[text\] that says "$1$" drawn in grid
- col\_tags\_2: a Math \[text\] that says "$2$" drawn in grid
- col\_tags\_3: a Math \[text\] that says "$3$" drawn in grid
- d\_tag: a Math \[red\] that says "$d$" drawn in grid
- def\_d: a Math \[text\] that says "$d\_i = upright("longest fall from") thin i$"
- def\_u: a Math \[text\] that says "$u\_i = upright("longest rise from") thin i$"
- dots: a Point \[blue\] drawn in plot (location=(1, 3))
- dots\_10: a Point \[blue\] drawn in plot (location=(10, 6))
- dots\_2: a Point \[blue\] drawn in plot (location=(2, 7))
- dots\_3: a Point \[blue\] drawn in plot (location=(3, 2))
- dots\_4: a Point \[blue\] drawn in plot (location=(4, 9))
- dots\_5: a Point \[blue\] drawn in plot (location=(5, 5))
- dots\_6: a Point \[blue\] drawn in plot (location=(6, 1))
- dots\_7: a Point \[blue\] drawn in plot (location=(7, 8))
- dots\_8: a Point \[blue\] drawn in plot (location=(8, 4))
- dots\_9: a Point \[blue\] drawn in plot (location=(9, 10))
- example: a Math \[text\] that says "$u\_2 = 3, quad d\_2 = 3$"
- fall\_legs: a Line \[red\] drawn in plot (start=(2, 7), end=(5, 5))
- fall\_legs\_2: a Line \[red\] drawn in plot (start=(5, 5), end=(8, 4))
- four\_legs: a Line \[yellow\] drawn in plot (start=(3, 2), end=(5, 5))
- four\_legs\_2: a Line \[yellow\] drawn in plot (start=(5, 5), end=(7, 8))
- four\_legs\_3: a Line \[yellow\] drawn in plot (start=(7, 8), end=(9, 10))
- grid: a Figure (x\_range=(-0.1, 4.6), y\_range=(-0.1, 4.6), aspect=(1.0, 1.0))
- head\_grid: a Heading that says "Nine Boxes for Ten Positions"
- head\_seq: a Heading that says "Ten Numbers in Some Order"
- plot: an Axes (x\_range=(0.0, 11.0), y\_range=(0.0, 11.0), x\_ticks\_every=1.0)
- proof: a Derivation \[text\] that says "$u\_i, d\_i &in brace.l 1, 2, 3 brace.r \\ 10 thin upright("positions") &arrow.r 9 thin upright("pairs") \\ (u\_i, d\_i) &= (u\_j, d\_j), quad i \< j \\ a\_i \< a\_j &arrow.r.double u\_i \> u\_j \\ a\_i \> a\_j &arrow.r.double d\_i \> d\_j$"
- rise\_legs: a Line \[green\] drawn in plot (start=(2, 7), end=(4, 9))
- rise\_legs\_2: a Line \[green\] drawn in plot (start=(4, 9), end=(9, 10))
- row\_tags: a Math \[text\] that says "$1$" drawn in grid
- row\_tags\_2: a Math \[text\] that says "$2$" drawn in grid
- row\_tags\_3: a Math \[text\] that says "$3$" drawn in grid
- u\_tag: a Math \[green\] that says "$u$" drawn in grid
- verdict: a Tex \[text\] that says "So a monotone run of four always exists."

#### Beats

##### [03:50.068](https://academa.ai/lectures/pigeonhole-principle-boxes?t=230.0681875)

Narration: Ten numbers, all different, in whatever order somebody wrote them down. Position along the bottom, value up the side.

Board: Empty.

Actions:
- [03:50.068](https://academa.ai/lectures/pigeonhole-principle-boxes?t=230.0681875): head\_seq is shown on the screen, written out.
- [03:50.068](https://academa.ai/lectures/pigeonhole-principle-boxes?t=230.0681875): plot is shown on the screen, written out.
- [03:55.107](https://academa.ai/lectures/pigeonhole-principle-boxes?t=235.10718749999998): dots is shown on the screen, written out.
- [03:55.227](https://academa.ai/lectures/pigeonhole-principle-boxes?t=235.22718749999999): dots\_2 is shown on the screen, written out.
- [03:55.347](https://academa.ai/lectures/pigeonhole-principle-boxes?t=235.3471875): dots\_3 is shown on the screen, written out.
- [03:55.467](https://academa.ai/lectures/pigeonhole-principle-boxes?t=235.4671875): dots\_4 is shown on the screen, written out.
- [03:55.587](https://academa.ai/lectures/pigeonhole-principle-boxes?t=235.5871875): dots\_5 is shown on the screen, written out.
- [03:55.707](https://academa.ai/lectures/pigeonhole-principle-boxes?t=235.7071875): dots\_6 is shown on the screen, written out.
- [03:55.827](https://academa.ai/lectures/pigeonhole-principle-boxes?t=235.82718749999998): dots\_7 is shown on the screen, written out.
- [03:55.947](https://academa.ai/lectures/pigeonhole-principle-boxes?t=235.94718749999998): dots\_8 is shown on the screen, written out.
- [03:56.067](https://academa.ai/lectures/pigeonhole-principle-boxes?t=236.0671875): dots\_9 is shown on the screen, written out.
- [03:56.187](https://academa.ai/lectures/pigeonhole-principle-boxes?t=236.1871875): dots\_10 is shown on the screen, written out.

##### [03:58.76](https://academa.ai/lectures/pigeonhole-principle-boxes?t=238.7601875)

Narration: 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.

Board: plot — an Axes (x\_range=(0.0, 11.0), y\_range=(0.0, 11.0), x\_ticks\_every=1.0); head\_seq — a Heading that says "Ten Numbers in Some Order"; dots — a Point \[blue\] drawn in plot (location=(1, 3)); dots\_2 — a Point \[blue\] drawn in plot (location=(2, 7)); dots\_3 — a Point \[blue\] drawn in plot (location=(3, 2)); dots\_4 — a Point \[blue\] drawn in plot (location=(4, 9)); dots\_5 — a Point \[blue\] drawn in plot (location=(5, 5)); dots\_6 — a Point \[blue\] drawn in plot (location=(6, 1)); dots\_7 — a Point \[blue\] drawn in plot (location=(7, 8)); dots\_8 — a Point \[blue\] drawn in plot (location=(8, 4)); dots\_9 — a Point \[blue\] drawn in plot (location=(9, 10)); dots\_10 — a Point \[blue\] drawn in plot (location=(10, 6))

Actions:
- None.

##### [04:13.455](https://academa.ai/lectures/pigeonhole-principle-boxes?t=253.4551875)

Narration: Start at the second term, which is seven. Going up from there I can reach nine, and then ten. A rising run of three.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [04:18.47](https://academa.ai/lectures/pigeonhole-principle-boxes?t=258.4701875): rise\_legs is shown on the screen, drawn.
- [04:18.77](https://academa.ai/lectures/pigeonhole-principle-boxes?t=258.7701875): rise\_legs\_2 is shown on the screen, drawn.

##### [04:22.89](https://academa.ai/lectures/pigeonhole-principle-boxes?t=262.8901875)

Narration: Going down from that same seven I can reach five, and then four. A falling run of three as well.

Board: plot — an Axes (x\_range=(0.0, 11.0), y\_range=(0.0, 11.0), x\_ticks\_every=1.0); head\_seq — a Heading that says "Ten Numbers in Some Order"; dots — a Point \[blue\] drawn in plot (location=(1, 3)); dots\_2 — a Point \[blue\] drawn in plot (location=(2, 7)); dots\_3 — a Point \[blue\] drawn in plot (location=(3, 2)); dots\_4 — a Point \[blue\] drawn in plot (location=(4, 9)); dots\_5 — a Point \[blue\] drawn in plot (location=(5, 5)); dots\_6 — a Point \[blue\] drawn in plot (location=(6, 1)); dots\_7 — a Point \[blue\] drawn in plot (location=(7, 8)); dots\_8 — a Point \[blue\] drawn in plot (location=(8, 4)); dots\_9 — a Point \[blue\] drawn in plot (location=(9, 10)); dots\_10 — a Point \[blue\] drawn in plot (location=(10, 6)); rise\_legs — a Line \[green\] drawn in plot (start=(2, 7), end=(4, 9)); rise\_legs\_2 — a Line \[green\] drawn in plot (start=(4, 9), end=(9, 10))

Actions:
- [04:25.595](https://academa.ai/lectures/pigeonhole-principle-boxes?t=265.5951875): fall\_legs is shown on the screen, drawn.
- [04:25.895](https://academa.ai/lectures/pigeonhole-principle-boxes?t=265.8951875): fall\_legs\_2 is shown on the screen, drawn.

##### [04:30.526](https://academa.ai/lectures/pigeonhole-principle-boxes?t=270.5261875)

Narration: 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.

Board: plot — an Axes (x\_range=(0.0, 11.0), y\_range=(0.0, 11.0), x\_ticks\_every=1.0); head\_seq — a Heading that says "Ten Numbers in Some Order"; dots — a Point \[blue\] drawn in plot (location=(1, 3)); dots\_2 — a Point \[blue\] drawn in plot (location=(2, 7)); dots\_3 — a Point \[blue\] drawn in plot (location=(3, 2)); dots\_4 — a Point \[blue\] drawn in plot (location=(4, 9)); dots\_5 — a Point \[blue\] drawn in plot (location=(5, 5)); dots\_6 — a Point \[blue\] drawn in plot (location=(6, 1)); dots\_7 — a Point \[blue\] drawn in plot (location=(7, 8)); dots\_8 — a Point \[blue\] drawn in plot (location=(8, 4)); dots\_9 — a Point \[blue\] drawn in plot (location=(9, 10)); dots\_10 — a Point \[blue\] drawn in plot (location=(10, 6)); rise\_legs — a Line \[green\] drawn in plot (start=(2, 7), end=(4, 9)); rise\_legs\_2 — a Line \[green\] drawn in plot (start=(4, 9), end=(9, 10)); fall\_legs — a Line \[red\] drawn in plot (start=(2, 7), end=(5, 5)); fall\_legs\_2 — a Line \[red\] drawn in plot (start=(5, 5), end=(8, 4))

Actions:
- [04:35.646](https://academa.ai/lectures/pigeonhole-principle-boxes?t=275.6461875): plot moves to a new place on the board.
- [04:35.646](https://academa.ai/lectures/pigeonhole-principle-boxes?t=275.6461875): def\_u is shown on the screen, written out.
- [04:39.408](https://academa.ai/lectures/pigeonhole-principle-boxes?t=279.4081875): def\_d is shown on the screen, written out.
- [04:42.554](https://academa.ai/lectures/pigeonhole-principle-boxes?t=282.5541875): example is shown on the screen, written out.

##### [04:44.872](https://academa.ai/lectures/pigeonhole-principle-boxes?t=284.8721875)

Narration: 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.

Board: def\_u — a Math \[text\] that says "$u\_i = upright("longest rise from") thin i$"; def\_d — a Math \[text\] that says "$d\_i = upright("longest fall from") thin i$"; example — a Math \[text\] that says "$u\_2 = 3, quad d\_2 = 3$"; plot — an Axes (x\_range=(0.0, 11.0), y\_range=(0.0, 11.0), x\_ticks\_every=1.0); head\_seq — a Heading that says "Ten Numbers in Some Order"; dots — a Point \[blue\] drawn in plot (location=(1, 3)); dots\_2 — a Point \[blue\] drawn in plot (location=(2, 7)); dots\_3 — a Point \[blue\] drawn in plot (location=(3, 2)); dots\_4 — a Point \[blue\] drawn in plot (location=(4, 9)); dots\_5 — a Point \[blue\] drawn in plot (location=(5, 5)); dots\_6 — a Point \[blue\] drawn in plot (location=(6, 1)); dots\_7 — a Point \[blue\] drawn in plot (location=(7, 8)); dots\_8 — a Point \[blue\] drawn in plot (location=(8, 4)); dots\_9 — a Point \[blue\] drawn in plot (location=(9, 10)); dots\_10 — a Point \[blue\] drawn in plot (location=(10, 6)); rise\_legs — a Line \[green\] drawn in plot (start=(2, 7), end=(4, 9)); rise\_legs\_2 — a Line \[green\] drawn in plot (start=(4, 9), end=(9, 10)); fall\_legs — a Line \[red\] drawn in plot (start=(2, 7), end=(5, 5)); fall\_legs\_2 — a Line \[red\] drawn in plot (start=(5, 5), end=(8, 4))

Actions:
- [04:44.872](https://academa.ai/lectures/pigeonhole-principle-boxes?t=284.8721875): rise\_legs is hidden from the screen.
- [04:44.872](https://academa.ai/lectures/pigeonhole-principle-boxes?t=284.8721875): rise\_legs\_2 is hidden from the screen.
- [04:44.872](https://academa.ai/lectures/pigeonhole-principle-boxes?t=284.8721875): fall\_legs is hidden from the screen.
- [04:44.872](https://academa.ai/lectures/pigeonhole-principle-boxes?t=284.8721875): fall\_legs\_2 is hidden from the screen.
- [04:49.539](https://academa.ai/lectures/pigeonhole-principle-boxes?t=289.5391875): four\_legs is shown on the screen, drawn.
- [04:49.839](https://academa.ai/lectures/pigeonhole-principle-boxes?t=289.8391875): four\_legs\_2 is shown on the screen, drawn.
- [04:50.139](https://academa.ai/lectures/pigeonhole-principle-boxes?t=290.1391875): four\_legs\_3 is shown on the screen, drawn.

##### [04:57.308](https://academa.ai/lectures/pigeonhole-principle-boxes?t=297.30818750000003)

Narration: 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.

Board: def\_u — a Math \[text\] that says "$u\_i = upright("longest rise from") thin i$"; def\_d — a Math \[text\] that says "$d\_i = upright("longest fall from") thin i$"; example — a Math \[text\] that says "$u\_2 = 3, quad d\_2 = 3$"; plot — an Axes (x\_range=(0.0, 11.0), y\_range=(0.0, 11.0), x\_ticks\_every=1.0); head\_seq — a Heading that says "Ten Numbers in Some Order"; dots — a Point \[blue\] drawn in plot (location=(1, 3)); dots\_2 — a Point \[blue\] drawn in plot (location=(2, 7)); dots\_3 — a Point \[blue\] drawn in plot (location=(3, 2)); dots\_4 — a Point \[blue\] drawn in plot (location=(4, 9)); dots\_5 — a Point \[blue\] drawn in plot (location=(5, 5)); dots\_6 — a Point \[blue\] drawn in plot (location=(6, 1)); dots\_7 — a Point \[blue\] drawn in plot (location=(7, 8)); dots\_8 — a Point \[blue\] drawn in plot (location=(8, 4)); dots\_9 — a Point \[blue\] drawn in plot (location=(9, 10)); dots\_10 — a Point \[blue\] drawn in plot (location=(10, 6)); four\_legs — a Line \[yellow\] drawn in plot (start=(3, 2), end=(5, 5)); four\_legs\_2 — a Line \[yellow\] drawn in plot (start=(5, 5), end=(7, 8)); four\_legs\_3 — a Line \[yellow\] drawn in plot (start=(7, 8), end=(9, 10))

Actions:
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): def\_d is hidden from the screen — left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): def\_u is hidden from the screen — left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): example is hidden from the screen — left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): head\_seq is hidden from the screen — left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): plot is hidden from the screen — left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): dots is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): dots\_2 is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): dots\_3 is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): dots\_4 is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): dots\_5 is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): dots\_6 is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): dots\_7 is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): dots\_8 is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): dots\_9 is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): dots\_10 is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): four\_legs is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): four\_legs\_2 is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): four\_legs\_3 is hidden from the screen — plot left the board.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): grid is shown on the screen, written out.
- [05:6.928](https://academa.ai/lectures/pigeonhole-principle-boxes?t=306.9276875): cells is shown on the screen, written out.
- [05:7.008](https://academa.ai/lectures/pigeonhole-principle-boxes?t=307.0076875): cells\_2 is shown on the screen, written out.
- [05:7.168](https://academa.ai/lectures/pigeonhole-principle-boxes?t=307.1676875): cells\_3 is shown on the screen, written out.
- [05:7.408](https://academa.ai/lectures/pigeonhole-principle-boxes?t=307.4076875): cells\_4 is shown on the screen, written out.
- [05:7.728](https://academa.ai/lectures/pigeonhole-principle-boxes?t=307.7276875): cells\_5 is shown on the screen, written out.
- [05:8.128](https://academa.ai/lectures/pigeonhole-principle-boxes?t=308.1276875): cells\_6 is shown on the screen, written out.

##### [05:8.128](https://academa.ai/lectures/pigeonhole-principle-boxes?t=308.1276875)

Narration: 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.

Board: grid — a Figure (x\_range=(-0.1, 4.6), y\_range=(-0.1, 4.6), aspect=(1.0, 1.0)); cells — a Polygon \[gray\] drawn in grid (vertices=((0.75, 0.75), (1.75, 0.75), (1.75, 1.75), (0.75, 1.75)), filled=False); cells\_2 — a Polygon \[gray\] drawn in grid (vertices=((1.9, 0.75), (2.9, 0.75), (2.9, 1.75), (1.9, 1.75)), filled=False); cells\_3 — a Polygon \[gray\] drawn in grid (vertices=((3.05, 0.75), (4.05, 0.75), (4.05, 1.75), (3.05, 1.75)), filled=False); cells\_4 — a Polygon \[gray\] drawn in grid (vertices=((0.75, 1.9), (1.75, 1.9), (1.75, 2.9), (0.75, 2.9)), filled=False); cells\_5 — a Polygon \[gray\] drawn in grid (vertices=((1.9, 1.9), (2.9, 1.9), (2.9, 2.9), (1.9, 2.9)), filled=False)

Actions:
- [05:8.128](https://academa.ai/lectures/pigeonhole-principle-boxes?t=308.1276875): cells\_6 is shown on the screen, written out.
- [05:8.128](https://academa.ai/lectures/pigeonhole-principle-boxes?t=308.1276875): head\_grid is shown on the screen, written out.
- [05:8.348](https://academa.ai/lectures/pigeonhole-principle-boxes?t=308.3481875): claim is shown on the screen, written out.
- [05:8.608](https://academa.ai/lectures/pigeonhole-principle-boxes?t=308.6076875): cells\_7 is shown on the screen, written out.
- [05:9.168](https://academa.ai/lectures/pigeonhole-principle-boxes?t=309.1676875): cells\_8 is shown on the screen, written out.
- [05:9.808](https://academa.ai/lectures/pigeonhole-principle-boxes?t=309.8076875): cells\_9 is shown on the screen, written out.
- [05:10.528](https://academa.ai/lectures/pigeonhole-principle-boxes?t=310.5276875): col\_tags is shown on the screen, written out.
- [05:11.328](https://academa.ai/lectures/pigeonhole-principle-boxes?t=311.3276875): col\_tags\_2 is shown on the screen, written out.
- [05:12.208](https://academa.ai/lectures/pigeonhole-principle-boxes?t=312.2076875): col\_tags\_3 is shown on the screen, written out.
- [05:13.168](https://academa.ai/lectures/pigeonhole-principle-boxes?t=313.1676875): row\_tags is shown on the screen, written out.
- [05:13.828](https://academa.ai/lectures/pigeonhole-principle-boxes?t=313.8281875): proof is shown on the screen, written out.
- [05:14.208](https://academa.ai/lectures/pigeonhole-principle-boxes?t=314.2076875): row\_tags\_2 is shown on the screen, written out.
- [05:15.328](https://academa.ai/lectures/pigeonhole-principle-boxes?t=315.3276875): row\_tags\_3 is shown on the screen, written out.
- [05:15.328](https://academa.ai/lectures/pigeonhole-principle-boxes?t=315.3276875): u\_tag is shown on the screen, written out.
- [05:15.328](https://academa.ai/lectures/pigeonhole-principle-boxes?t=315.3276875): d\_tag is shown on the screen, written out.

##### [05:18.748](https://academa.ai/lectures/pigeonhole-principle-boxes?t=318.7476875)

Narration: Two numbers, three choices each. Three times three is nine possible pairs, and there are the nine of them, one box apiece.

Board: claim — a Tex \[text\] that says "Suppose no monotone run of four."; grid — a Figure (x\_range=(-0.1, 4.6), y\_range=(-0.1, 4.6), aspect=(1.0, 1.0)); head\_grid — a Heading that says "Nine Boxes for Ten Positions"; cells — a Polygon \[gray\] drawn in grid (vertices=((0.75, 0.75), (1.75, 0.75), (1.75, 1.75), (0.75, 1.75)), filled=False); cells\_2 — a Polygon \[gray\] drawn in grid (vertices=((1.9, 0.75), (2.9, 0.75), (2.9, 1.75), (1.9, 1.75)), filled=False); cells\_3 — a Polygon \[gray\] drawn in grid (vertices=((3.05, 0.75), (4.05, 0.75), (4.05, 1.75), (3.05, 1.75)), filled=False); cells\_4 — a Polygon \[gray\] drawn in grid (vertices=((0.75, 1.9), (1.75, 1.9), (1.75, 2.9), (0.75, 2.9)), filled=False); cells\_5 — a Polygon \[gray\] drawn in grid (vertices=((1.9, 1.9), (2.9, 1.9), (2.9, 2.9), (1.9, 2.9)), filled=False); cells\_6 — a Polygon \[gray\] drawn in grid (vertices=((3.05, 1.9), (4.05, 1.9), (4.05, 2.9), (3.05, 2.9)), filled=False); cells\_7 — a Polygon \[gray\] drawn in grid (vertices=((0.75, 3.05), (1.75, 3.05), (1.75, 4.05), (0.75, 4.05)), filled=False); cells\_8 — a Polygon \[gray\] drawn in grid (vertices=((1.9, 3.05), (2.9, 3.05), (2.9, 4.05), (1.9, 4.05)), filled=False); cells\_9 — a Polygon \[gray\] drawn in grid (vertices=((3.05, 3.05), (4.05, 3.05), (4.05, 4.05), (3.05, 4.05)), filled=False); col\_tags — a Math \[text\] that says "$1$" drawn in grid; col\_tags\_2 — a Math \[text\] that says "$2$" drawn in grid; col\_tags\_3 — a Math \[text\] that says "$3$" drawn in grid; row\_tags — a Math \[text\] that says "$1$" drawn in grid; row\_tags\_2 — a Math \[text\] that says "$2$" drawn in grid; row\_tags\_3 — a Math \[text\] that says "$3$" drawn in grid; u\_tag — a Math \[green\] that says "$u$" drawn in grid; d\_tag — a Math \[red\] that says "$d$" drawn in grid

Actions:
- [05:23.229](https://academa.ai/lectures/pigeonhole-principle-boxes?t=323.2291875): cells is indicated — a transient flash.
- [05:23.309](https://academa.ai/lectures/pigeonhole-principle-boxes?t=323.3091875): cells\_2 is indicated — a transient flash.
- [05:23.389](https://academa.ai/lectures/pigeonhole-principle-boxes?t=323.38918750000005): cells\_3 is indicated — a transient flash.
- [05:23.469](https://academa.ai/lectures/pigeonhole-principle-boxes?t=323.46918750000003): cells\_4 is indicated — a transient flash.
- [05:23.549](https://academa.ai/lectures/pigeonhole-principle-boxes?t=323.5491875): cells\_5 is indicated — a transient flash.
- [05:23.629](https://academa.ai/lectures/pigeonhole-principle-boxes?t=323.6291875): cells\_6 is indicated — a transient flash.
- [05:23.709](https://academa.ai/lectures/pigeonhole-principle-boxes?t=323.7091875): cells\_7 is indicated — a transient flash.
- [05:23.789](https://academa.ai/lectures/pigeonhole-principle-boxes?t=323.7891875): cells\_8 is indicated — a transient flash.
- [05:23.869](https://academa.ai/lectures/pigeonhole-principle-boxes?t=323.8691875): cells\_9 is indicated — a transient flash.

##### [05:28.078](https://academa.ai/lectures/pigeonhole-principle-boxes?t=328.0781875)

Narration: But there are ten positions, and each position hands you one pair. Ten items, nine boxes.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [05:31.027](https://academa.ai/lectures/pigeonhole-principle-boxes?t=331.0271875): proof is shown on the screen, written out.
- [05:32.919](https://academa.ai/lectures/pigeonhole-principle-boxes?t=332.9191875): chips is shown on the screen, written out.
- [05:33.079](https://academa.ai/lectures/pigeonhole-principle-boxes?t=333.0791875): chips\_2 is shown on the screen, written out.
- [05:33.239](https://academa.ai/lectures/pigeonhole-principle-boxes?t=333.2391875): chips\_3 is shown on the screen, written out.
- [05:33.399](https://academa.ai/lectures/pigeonhole-principle-boxes?t=333.39918750000004): chips\_4 is shown on the screen, written out.
- [05:33.559](https://academa.ai/lectures/pigeonhole-principle-boxes?t=333.5591875): chips\_5 is shown on the screen, written out.
- [05:33.719](https://academa.ai/lectures/pigeonhole-principle-boxes?t=333.71918750000003): chips\_6 is shown on the screen, written out.
- [05:33.879](https://academa.ai/lectures/pigeonhole-principle-boxes?t=333.8791875): chips\_7 is shown on the screen, written out.
- [05:34.039](https://academa.ai/lectures/pigeonhole-principle-boxes?t=334.0391875): chips\_8 is shown on the screen, written out.
- [05:34.199](https://academa.ai/lectures/pigeonhole-principle-boxes?t=334.1991875): chips\_9 is shown on the screen, written out.
- [05:34.359](https://academa.ai/lectures/pigeonhole-principle-boxes?t=334.3591875): chips\_10 is shown on the screen, written out.

##### [05:35.4](https://academa.ai/lectures/pigeonhole-principle-boxes?t=335.4001875)

Narration: So two positions, i somewhere to the left of j, carry the identical pair. Same u, same d.

Board: claim — a Tex \[text\] that says "Suppose no monotone run of four."; grid — a Figure (x\_range=(-0.1, 4.6), y\_range=(-0.1, 4.6), aspect=(1.0, 1.0)); head\_grid — a Heading that says "Nine Boxes for Ten Positions"; cells — a Polygon \[gray\] drawn in grid (vertices=((0.75, 0.75), (1.75, 0.75), (1.75, 1.75), (0.75, 1.75)), filled=False); cells\_2 — a Polygon \[gray\] drawn in grid (vertices=((1.9, 0.75), (2.9, 0.75), (2.9, 1.75), (1.9, 1.75)), filled=False); cells\_3 — a Polygon \[gray\] drawn in grid (vertices=((3.05, 0.75), (4.05, 0.75), (4.05, 1.75), (3.05, 1.75)), filled=False); cells\_4 — a Polygon \[gray\] drawn in grid (vertices=((0.75, 1.9), (1.75, 1.9), (1.75, 2.9), (0.75, 2.9)), filled=False); cells\_5 — a Polygon \[gray\] drawn in grid (vertices=((1.9, 1.9), (2.9, 1.9), (2.9, 2.9), (1.9, 2.9)), filled=False); cells\_6 — a Polygon \[gray\] drawn in grid (vertices=((3.05, 1.9), (4.05, 1.9), (4.05, 2.9), (3.05, 2.9)), filled=False); cells\_7 — a Polygon \[gray\] drawn in grid (vertices=((0.75, 3.05), (1.75, 3.05), (1.75, 4.05), (0.75, 4.05)), filled=False); cells\_8 — a Polygon \[gray\] drawn in grid (vertices=((1.9, 3.05), (2.9, 3.05), (2.9, 4.05), (1.9, 4.05)), filled=False); cells\_9 — a Polygon \[gray\] drawn in grid (vertices=((3.05, 3.05), (4.05, 3.05), (4.05, 4.05), (3.05, 4.05)), filled=False); col\_tags — a Math \[text\] that says "$1$" drawn in grid; col\_tags\_2 — a Math \[text\] that says "$2$" drawn in grid; col\_tags\_3 — a Math \[text\] that says "$3$" drawn in grid; row\_tags — a Math \[text\] that says "$1$" drawn in grid; row\_tags\_2 — a Math \[text\] that says "$2$" drawn in grid; row\_tags\_3 — a Math \[text\] that says "$3$" drawn in grid; u\_tag — a Math \[green\] that says "$u$" drawn in grid; d\_tag — a Math \[red\] that says "$d$" drawn in grid; chips — a Point \[blue\] drawn in grid (location=(1.25, 1.25)); chips\_2 — a Point \[blue\] drawn in grid (location=(2.4, 1.25)); chips\_3 — a Point \[blue\] drawn in grid (location=(3.55, 1.25)); chips\_4 — a Point \[blue\] drawn in grid (location=(1.25, 2.4)); chips\_5 — a Point \[yellow\] drawn in grid (location=(2.1799999999999997, 2.4)); chips\_6 — a Point \[yellow\] drawn in grid (location=(2.62, 2.4)); chips\_7 — a Point \[blue\] drawn in grid (location=(3.55, 2.4)); chips\_8 — a Point \[blue\] drawn in grid (location=(1.25, 3.55)); chips\_9 — a Point \[blue\] drawn in grid (location=(2.4, 3.55)); chips\_10 — a Point \[blue\] drawn in grid (location=(3.55, 3.55))

Actions:
- [05:39.545](https://academa.ai/lectures/pigeonhole-principle-boxes?t=339.5451875): proof is shown on the screen, written out.
- [05:41.147](https://academa.ai/lectures/pigeonhole-principle-boxes?t=341.14718750000003): chips\_5 is indicated — a transient flash.
- [05:41.547](https://academa.ai/lectures/pigeonhole-principle-boxes?t=341.54718750000006): chips\_6 is indicated — a transient flash.

##### [05:43.565](https://academa.ai/lectures/pigeonhole-principle-boxes?t=343.5646875)

Narration: And now it breaks. The numbers are all different, so either a i is below a j or above it. Suppose it is below.

Board: Unchanged from the preceding beat in this scene.

Actions:
- None.

##### [05:52.889](https://academa.ai/lectures/pigeonhole-principle-boxes?t=352.88918750000005)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [06:2.839](https://academa.ai/lectures/pigeonhole-principle-boxes?t=362.83918750000004): proof is shown on the screen, written out.

##### [06:6.69](https://academa.ai/lectures/pigeonhole-principle-boxes?t=366.6901875)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [06:10.637](https://academa.ai/lectures/pigeonhole-principle-boxes?t=370.6371875): proof is shown on the screen, written out.
- [06:17.15](https://academa.ai/lectures/pigeonhole-principle-boxes?t=377.1501875): verdict is shown on the screen, written out.
- [06:20.32](https://academa.ai/lectures/pigeonhole-principle-boxes?t=380.32018750000003): A box is drawn around verdict.

##### [06:22.72](https://academa.ai/lectures/pigeonhole-principle-boxes?t=382.7196875)

Narration: 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.

Board: claim — a Tex \[text\] that says "Suppose no monotone run of four."; verdict — a Tex \[text\] that says "So a monotone run of four always exists."; grid — a Figure (x\_range=(-0.1, 4.6), y\_range=(-0.1, 4.6), aspect=(1.0, 1.0)); head\_grid — a Heading that says "Nine Boxes for Ten Positions"; cells — a Polygon \[gray\] drawn in grid (vertices=((0.75, 0.75), (1.75, 0.75), (1.75, 1.75), (0.75, 1.75)), filled=False); cells\_2 — a Polygon \[gray\] drawn in grid (vertices=((1.9, 0.75), (2.9, 0.75), (2.9, 1.75), (1.9, 1.75)), filled=False); cells\_3 — a Polygon \[gray\] drawn in grid (vertices=((3.05, 0.75), (4.05, 0.75), (4.05, 1.75), (3.05, 1.75)), filled=False); cells\_4 — a Polygon \[gray\] drawn in grid (vertices=((0.75, 1.9), (1.75, 1.9), (1.75, 2.9), (0.75, 2.9)), filled=False); cells\_5 — a Polygon \[gray\] drawn in grid (vertices=((1.9, 1.9), (2.9, 1.9), (2.9, 2.9), (1.9, 2.9)), filled=False); cells\_6 — a Polygon \[gray\] drawn in grid (vertices=((3.05, 1.9), (4.05, 1.9), (4.05, 2.9), (3.05, 2.9)), filled=False); cells\_7 — a Polygon \[gray\] drawn in grid (vertices=((0.75, 3.05), (1.75, 3.05), (1.75, 4.05), (0.75, 4.05)), filled=False); cells\_8 — a Polygon \[gray\] drawn in grid (vertices=((1.9, 3.05), (2.9, 3.05), (2.9, 4.05), (1.9, 4.05)), filled=False); cells\_9 — a Polygon \[gray\] drawn in grid (vertices=((3.05, 3.05), (4.05, 3.05), (4.05, 4.05), (3.05, 4.05)), filled=False); col\_tags — a Math \[text\] that says "$1$" drawn in grid; col\_tags\_2 — a Math \[text\] that says "$2$" drawn in grid; col\_tags\_3 — a Math \[text\] that says "$3$" drawn in grid; row\_tags — a Math \[text\] that says "$1$" drawn in grid; row\_tags\_2 — a Math \[text\] that says "$2$" drawn in grid; row\_tags\_3 — a Math \[text\] that says "$3$" drawn in grid; u\_tag — a Math \[green\] that says "$u$" drawn in grid; d\_tag — a Math \[red\] that says "$d$" drawn in grid; chips — a Point \[blue\] drawn in grid (location=(1.25, 1.25)); chips\_2 — a Point \[blue\] drawn in grid (location=(2.4, 1.25)); chips\_3 — a Point \[blue\] drawn in grid (location=(3.55, 1.25)); chips\_4 — a Point \[blue\] drawn in grid (location=(1.25, 2.4)); chips\_5 — a Point \[yellow\] drawn in grid (location=(2.1799999999999997, 2.4)); chips\_6 — a Point \[yellow\] drawn in grid (location=(2.62, 2.4)); chips\_7 — a Point \[blue\] drawn in grid (location=(3.55, 2.4)); chips\_8 — a Point \[blue\] drawn in grid (location=(1.25, 3.55)); chips\_9 — a Point \[blue\] drawn in grid (location=(2.4, 3.55)); chips\_10 — a Point \[blue\] drawn in grid (location=(3.55, 3.55))

Actions:
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): claim is hidden from the screen — left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): grid is hidden from the screen — left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): cells is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): cells\_2 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): cells\_3 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): cells\_4 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): cells\_5 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): cells\_6 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): cells\_7 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): cells\_8 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): cells\_9 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): col\_tags is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): col\_tags\_2 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): col\_tags\_3 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): row\_tags is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): row\_tags\_2 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): row\_tags\_3 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): u\_tag is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): d\_tag is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): chips is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): chips\_2 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): chips\_3 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): chips\_4 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): chips\_5 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): chips\_6 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): chips\_7 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): chips\_8 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): chips\_9 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): chips\_10 is hidden from the screen — grid left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): head\_grid is hidden from the screen — left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): proof is hidden from the screen — left the board.
- [06:34.747](https://academa.ai/lectures/pigeonhole-principle-boxes?t=394.74675): verdict is hidden from the screen — left the board.

### Scene 4: [Boxes That Are Intervals](https://academa.ai/lectures/pigeonhole-principle-boxes?t=395.78841666666665)

Span: 06:35.788–10:51.573 (395.78841666666665s–651.5731458333332s).

#### Objects

- answer: a Math \[text\] that says "$q = 5, quad p = 7, quad abs(sqrt(2) - 7 / 5) \< 1 / 25$"
- closing: a Tex \[text\] that says "The last sentence was the same all three times."
- g0: a Math \[text\] that says "$brace.l k alpha brace.r, quad k = 0, 1, dots, N$"
- g1: a Math \[text\] that says "$N + 1 thin upright("numbers,") quad N thin upright("intervals")$"
- g2: a Math \[text\] that says "$abs(brace.l j alpha brace.r - brace.l i alpha brace.r) \< 1 / N$"
- g3: a Math \[text\] that says "$q = j - i, quad p = floor(j alpha) - floor(i alpha)$"
- g4: a Math \[text\] that says "$abs(q alpha - p) \< 1 / N$"
- g5: a Math \[text\] that says "$abs(alpha - p / q) \< 1 / (q N) lt.eq 1 / q^2$"
- head\_int: a Heading that says "Cutting Up the Unit Interval"
- head\_proof: a Heading that says "From Two Dots to a Fraction"
- head\_recap: a Heading that says "Three Choices of Box"
- head\_thm: a Heading that says "What Dirichlet Promised"
- marks: a Math \[text\] that says "$0$" drawn in unit
- marks\_2: a Math \[text\] that says "$0.2$" drawn in unit
- marks\_3: a Math \[text\] that says "$0.4$" drawn in unit
- marks\_4: a Math \[text\] that says "$0.6$" drawn in unit
- marks\_5: a Math \[text\] that says "$0.8$" drawn in unit
- marks\_6: a Math \[text\] that says "$1$" drawn in unit
- pens: a Polygon \[gray\] drawn in unit (vertices=((0.0, -0.09), (0.2, -0.09), (0.2, 0.09), (0.0, 0.09)), filled=False)
- pens\_2: a Polygon \[gray\] drawn in unit (vertices=((0.2, -0.09), (0.4, -0.09), (0.4, 0.09), (0.2, 0.09)), filled=False)
- pens\_3: a Polygon \[gray\] drawn in unit (vertices=((0.4, -0.09), (0.6, -0.09), (0.6, 0.09), (0.4, 0.09)), filled=False)
- pens\_4: a Polygon \[gray\] drawn in unit (vertices=((0.6, -0.09), (0.8, -0.09), (0.8, 0.09), (0.6, 0.09)), filled=False)
- pens\_5: a Polygon \[gray\] drawn in unit (vertices=((0.8, -0.09), (1.0, -0.09), (1.0, 0.09), (0.8, 0.09)), filled=False)
- promise: a Math \[text\] that says "$abs(alpha - p / q) \< 1 / q^2$"
- recap: a Block \[text\] that says "Party: items are people, boxes are the possible answers. Sequence: items are positions, boxes are pairs $(u\_i, d\_i)$. Approximation: items are multiples of $alpha$, boxes are intervals."
- seeds: a Point \[blue\] drawn in unit
- seeds\_2: a Point \[blue\] drawn in unit (location=(0.41421356237309515, 0.0))
- seeds\_3: a Point \[blue\] drawn in unit (location=(0.8284271247461903, 0.0))
- seeds\_4: a Point \[blue\] drawn in unit (location=(0.24264068711928566, 0.0))
- seeds\_5: a Point \[blue\] drawn in unit (location=(0.6568542494923806, 0.0))
- seeds\_6: a Point \[blue\] drawn in unit (location=(0.0710678118654755, 0.0))
- setup: a Tex \[text\] that says "Six numbers, five intervals."
- thm: a Panel that says "For every real $alpha$ and every whole number $N gt.eq 1$ there are integers $p$ and $q$ with $1 lt.eq q lt.eq N$ and $abs(alpha - p / q) \< 1 / (q N)$."
- unit: a Figure (x\_range=(-0.08, 1.08), y\_range=(-0.34, 0.3), aspect=(1.16, 0.64))

#### Beats

##### [06:35.788](https://academa.ai/lectures/pigeonhole-principle-boxes?t=395.78841666666665)

Narration: 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.

Board: Empty.

Actions:
- [06:35.788](https://academa.ai/lectures/pigeonhole-principle-boxes?t=395.78841666666665): head\_thm is shown on the screen, written out.

##### [06:46.965](https://academa.ai/lectures/pigeonhole-principle-boxes?t=406.9649166666666)

Narration: 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.

Board: head\_thm — a Heading that says "What Dirichlet Promised"

Actions:
- None.

##### [07:1.59](https://academa.ai/lectures/pigeonhole-principle-boxes?t=421.5899166666666)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [07:2.507](https://academa.ai/lectures/pigeonhole-principle-boxes?t=422.50741666666664): thm is shown on the screen, written out.

##### [07:13.73](https://academa.ai/lectures/pigeonhole-principle-boxes?t=433.72991666666667)

Narration: 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.

Board: thm — a Panel that says "For every real $alpha$ and every whole number $N gt.eq 1$ there are integers $p$ and $q$ with $1 lt.eq q lt.eq N$ and $abs(alpha - p / q) \< 1 / (q N)$."; head\_thm — a Heading that says "What Dirichlet Promised"

Actions:
- [07:17.979](https://academa.ai/lectures/pigeonhole-principle-boxes?t=437.9794166666666): promise is shown on the screen, written out.
- [07:22.194](https://academa.ai/lectures/pigeonhole-principle-boxes?t=442.19441666666665): promise (the "1 / q^2" part) is emphasized.
- [07:23.715](https://academa.ai/lectures/pigeonhole-principle-boxes?t=443.71541666666667): promise (the "1 / q^2" part) is no longer emphasized.
- [07:26.165](https://academa.ai/lectures/pigeonhole-principle-boxes?t=446.16491666666667): head\_thm is hidden from the screen — left the board.
- [07:26.165](https://academa.ai/lectures/pigeonhole-principle-boxes?t=446.16491666666667): promise is hidden from the screen — left the board.
- [07:26.165](https://academa.ai/lectures/pigeonhole-principle-boxes?t=446.16491666666667): thm is hidden from the screen — left the board.
- [07:26.165](https://academa.ai/lectures/pigeonhole-principle-boxes?t=446.16491666666667): unit is shown on the screen, written out.

##### [07:27.365](https://academa.ai/lectures/pigeonhole-principle-boxes?t=447.36491666666666)

Narration: 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.

Board: unit — a Figure (x\_range=(-0.08, 1.08), y\_range=(-0.34, 0.3), aspect=(1.16, 0.64))

Actions:
- [07:27.365](https://academa.ai/lectures/pigeonhole-principle-boxes?t=447.36491666666666): head\_int is shown on the screen, written out.

##### [07:43.813](https://academa.ai/lectures/pigeonhole-principle-boxes?t=463.81291666666664)

Narration: 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.

Board: unit — a Figure (x\_range=(-0.08, 1.08), y\_range=(-0.34, 0.3), aspect=(1.16, 0.64)); head\_int — a Heading that says "Cutting Up the Unit Interval"

Actions:
- [07:52.648](https://academa.ai/lectures/pigeonhole-principle-boxes?t=472.64841666666666): seeds is shown on the screen, written out.
- [07:52.808](https://academa.ai/lectures/pigeonhole-principle-boxes?t=472.80841666666663): seeds\_2 is shown on the screen, written out.
- [07:52.968](https://academa.ai/lectures/pigeonhole-principle-boxes?t=472.96841666666666): seeds\_3 is shown on the screen, written out.
- [07:53.128](https://academa.ai/lectures/pigeonhole-principle-boxes?t=473.1284166666667): seeds\_4 is shown on the screen, written out.
- [07:53.288](https://academa.ai/lectures/pigeonhole-principle-boxes?t=473.28841666666665): seeds\_5 is shown on the screen, written out.
- [07:53.448](https://academa.ai/lectures/pigeonhole-principle-boxes?t=473.4484166666666): seeds\_6 is shown on the screen, written out.

##### [07:54.235](https://academa.ai/lectures/pigeonhole-principle-boxes?t=474.23541666666665)

Narration: 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.

Board: unit — a Figure (x\_range=(-0.08, 1.08), y\_range=(-0.34, 0.3), aspect=(1.16, 0.64)); head\_int — a Heading that says "Cutting Up the Unit Interval"; seeds — a Point \[blue\] drawn in unit; seeds\_2 — a Point \[blue\] drawn in unit (location=(0.41421356237309515, 0.0)); seeds\_3 — a Point \[blue\] drawn in unit (location=(0.8284271247461903, 0.0)); seeds\_4 — a Point \[blue\] drawn in unit (location=(0.24264068711928566, 0.0)); seeds\_5 — a Point \[blue\] drawn in unit (location=(0.6568542494923806, 0.0)); seeds\_6 — a Point \[blue\] drawn in unit (location=(0.0710678118654755, 0.0))

Actions:
- [07:56.789](https://academa.ai/lectures/pigeonhole-principle-boxes?t=476.7894166666666): pens is shown on the screen, written out.
- [07:56.929](https://academa.ai/lectures/pigeonhole-principle-boxes?t=476.9294166666666): pens\_2 is shown on the screen, written out.
- [07:57.069](https://academa.ai/lectures/pigeonhole-principle-boxes?t=477.06941666666665): pens\_3 is shown on the screen, written out.
- [07:57.209](https://academa.ai/lectures/pigeonhole-principle-boxes?t=477.20941666666664): pens\_4 is shown on the screen, written out.
- [07:57.349](https://academa.ai/lectures/pigeonhole-principle-boxes?t=477.3494166666666): pens\_5 is shown on the screen, written out.
- [07:57.349](https://academa.ai/lectures/pigeonhole-principle-boxes?t=477.3494166666666): marks is shown on the screen, written out.
- [07:57.449](https://academa.ai/lectures/pigeonhole-principle-boxes?t=477.44941666666665): marks\_2 is shown on the screen, written out.
- [07:57.649](https://academa.ai/lectures/pigeonhole-principle-boxes?t=477.64941666666664): marks\_3 is shown on the screen, written out.
- [07:57.949](https://academa.ai/lectures/pigeonhole-principle-boxes?t=477.94941666666665): marks\_4 is shown on the screen, written out.
- [07:58.349](https://academa.ai/lectures/pigeonhole-principle-boxes?t=478.3494166666666): marks\_5 is shown on the screen, written out.
- [07:58.849](https://academa.ai/lectures/pigeonhole-principle-boxes?t=478.8494166666666): marks\_6 is shown on the screen, written out.
- [08:1.7](https://academa.ai/lectures/pigeonhole-principle-boxes?t=481.7004166666666): setup is shown on the screen, written out.

##### [08:6.642](https://academa.ai/lectures/pigeonhole-principle-boxes?t=486.64191666666665)

Narration: 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.

Board: unit — a Figure (x\_range=(-0.08, 1.08), y\_range=(-0.34, 0.3), aspect=(1.16, 0.64)); setup — a Tex \[text\] that says "Six numbers, five intervals."; head\_int — a Heading that says "Cutting Up the Unit Interval"; seeds — a Point \[blue\] drawn in unit; seeds\_2 — a Point \[blue\] drawn in unit (location=(0.41421356237309515, 0.0)); seeds\_3 — a Point \[blue\] drawn in unit (location=(0.8284271247461903, 0.0)); seeds\_4 — a Point \[blue\] drawn in unit (location=(0.24264068711928566, 0.0)); seeds\_5 — a Point \[blue\] drawn in unit (location=(0.6568542494923806, 0.0)); seeds\_6 — a Point \[blue\] drawn in unit (location=(0.0710678118654755, 0.0)); pens — a Polygon \[gray\] drawn in unit (vertices=((0.0, -0.09), (0.2, -0.09), (0.2, 0.09), (0.0, 0.09)), filled=False); pens\_2 — a Polygon \[gray\] drawn in unit (vertices=((0.2, -0.09), (0.4, -0.09), (0.4, 0.09), (0.2, 0.09)), filled=False); pens\_3 — a Polygon \[gray\] drawn in unit (vertices=((0.4, -0.09), (0.6, -0.09), (0.6, 0.09), (0.4, 0.09)), filled=False); pens\_4 — a Polygon \[gray\] drawn in unit (vertices=((0.6, -0.09), (0.8, -0.09), (0.8, 0.09), (0.6, 0.09)), filled=False); pens\_5 — a Polygon \[gray\] drawn in unit (vertices=((0.8, -0.09), (1.0, -0.09), (1.0, 0.09), (0.8, 0.09)), filled=False); marks — a Math \[text\] that says "$0$" drawn in unit; marks\_2 — a Math \[text\] that says "$0.2$" drawn in unit; marks\_3 — a Math \[text\] that says "$0.4$" drawn in unit; marks\_4 — a Math \[text\] that says "$0.6$" drawn in unit; marks\_5 — a Math \[text\] that says "$0.8$" drawn in unit; marks\_6 — a Math \[text\] that says "$1$" drawn in unit

Actions:
- [08:7.838](https://academa.ai/lectures/pigeonhole-principle-boxes?t=487.8384166666666): pens is indicated — a transient flash.
- [08:10.775](https://academa.ai/lectures/pigeonhole-principle-boxes?t=490.7754166666666): seeds: give the object a name where it had none (show\_label).
- [08:13.329](https://academa.ai/lectures/pigeonhole-principle-boxes?t=493.32941666666665): seeds\_6: give the object a name where it had none (show\_label).

##### [08:20.919](https://academa.ai/lectures/pigeonhole-principle-boxes?t=500.91891666666663)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [08:32.018](https://academa.ai/lectures/pigeonhole-principle-boxes?t=512.0179166666667): unit moves to a new place on the board.
- [08:32.018](https://academa.ai/lectures/pigeonhole-principle-boxes?t=512.0179166666667): head\_int is hidden from the screen — left the board.
- [08:32.018](https://academa.ai/lectures/pigeonhole-principle-boxes?t=512.0179166666667): setup is hidden from the screen — left the board.

##### [08:33.218](https://academa.ai/lectures/pigeonhole-principle-boxes?t=513.2179166666666)

Narration: 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.

Board: unit — a Figure (x\_range=(-0.08, 1.08), y\_range=(-0.34, 0.3), aspect=(1.16, 0.64)); seeds — a Point \[blue\] drawn in unit; seeds\_2 — a Point \[blue\] drawn in unit (location=(0.41421356237309515, 0.0)); seeds\_3 — a Point \[blue\] drawn in unit (location=(0.8284271247461903, 0.0)); seeds\_4 — a Point \[blue\] drawn in unit (location=(0.24264068711928566, 0.0)); seeds\_5 — a Point \[blue\] drawn in unit (location=(0.6568542494923806, 0.0)); seeds\_6 — a Point \[blue\] drawn in unit (location=(0.0710678118654755, 0.0)); pens — a Polygon \[gray\] drawn in unit (vertices=((0.0, -0.09), (0.2, -0.09), (0.2, 0.09), (0.0, 0.09)), filled=False); pens\_2 — a Polygon \[gray\] drawn in unit (vertices=((0.2, -0.09), (0.4, -0.09), (0.4, 0.09), (0.2, 0.09)), filled=False); pens\_3 — a Polygon \[gray\] drawn in unit (vertices=((0.4, -0.09), (0.6, -0.09), (0.6, 0.09), (0.4, 0.09)), filled=False); pens\_4 — a Polygon \[gray\] drawn in unit (vertices=((0.6, -0.09), (0.8, -0.09), (0.8, 0.09), (0.6, 0.09)), filled=False); pens\_5 — a Polygon \[gray\] drawn in unit (vertices=((0.8, -0.09), (1.0, -0.09), (1.0, 0.09), (0.8, 0.09)), filled=False); marks — a Math \[text\] that says "$0$" drawn in unit; marks\_2 — a Math \[text\] that says "$0.2$" drawn in unit; marks\_3 — a Math \[text\] that says "$0.4$" drawn in unit; marks\_4 — a Math \[text\] that says "$0.6$" drawn in unit; marks\_5 — a Math \[text\] that says "$0.8$" drawn in unit; marks\_6 — a Math \[text\] that says "$1$" drawn in unit

Actions:
- [08:33.218](https://academa.ai/lectures/pigeonhole-principle-boxes?t=513.2179166666666): head\_proof is shown on the screen, written out.
- [08:35.389](https://academa.ai/lectures/pigeonhole-principle-boxes?t=515.3894166666666): g0 is shown on the screen, written out.

##### [08:42.583](https://academa.ai/lectures/pigeonhole-principle-boxes?t=522.5834166666666)

Narration: 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.

Board: unit — a Figure (x\_range=(-0.08, 1.08), y\_range=(-0.34, 0.3), aspect=(1.16, 0.64)); seeds — a Point \[blue\] drawn in unit; seeds\_2 — a Point \[blue\] drawn in unit (location=(0.41421356237309515, 0.0)); seeds\_3 — a Point \[blue\] drawn in unit (location=(0.8284271247461903, 0.0)); seeds\_4 — a Point \[blue\] drawn in unit (location=(0.24264068711928566, 0.0)); seeds\_5 — a Point \[blue\] drawn in unit (location=(0.6568542494923806, 0.0)); seeds\_6 — a Point \[blue\] drawn in unit (location=(0.0710678118654755, 0.0)); pens — a Polygon \[gray\] drawn in unit (vertices=((0.0, -0.09), (0.2, -0.09), (0.2, 0.09), (0.0, 0.09)), filled=False); pens\_2 — a Polygon \[gray\] drawn in unit (vertices=((0.2, -0.09), (0.4, -0.09), (0.4, 0.09), (0.2, 0.09)), filled=False); pens\_3 — a Polygon \[gray\] drawn in unit (vertices=((0.4, -0.09), (0.6, -0.09), (0.6, 0.09), (0.4, 0.09)), filled=False); pens\_4 — a Polygon \[gray\] drawn in unit (vertices=((0.6, -0.09), (0.8, -0.09), (0.8, 0.09), (0.6, 0.09)), filled=False); pens\_5 — a Polygon \[gray\] drawn in unit (vertices=((0.8, -0.09), (1.0, -0.09), (1.0, 0.09), (0.8, 0.09)), filled=False); marks — a Math \[text\] that says "$0$" drawn in unit; marks\_2 — a Math \[text\] that says "$0.2$" drawn in unit; marks\_3 — a Math \[text\] that says "$0.4$" drawn in unit; marks\_4 — a Math \[text\] that says "$0.6$" drawn in unit; marks\_5 — a Math \[text\] that says "$0.8$" drawn in unit; marks\_6 — a Math \[text\] that says "$1$" drawn in unit; g0 — a Math \[text\] that says "$brace.l k alpha brace.r, quad k = 0, 1, dots, N$"; head\_proof — a Heading that says "From Two Dots to a Fraction"

Actions:
- [08:43.117](https://academa.ai/lectures/pigeonhole-principle-boxes?t=523.1174166666666): g1 is shown on the screen, written out.
- [08:54.576](https://academa.ai/lectures/pigeonhole-principle-boxes?t=534.5764166666667): g2 is shown on the screen, written out.

##### [08:57.394](https://academa.ai/lectures/pigeonhole-principle-boxes?t=537.3939166666667)

Narration: 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.

Board: unit — a Figure (x\_range=(-0.08, 1.08), y\_range=(-0.34, 0.3), aspect=(1.16, 0.64)); seeds — a Point \[blue\] drawn in unit; seeds\_2 — a Point \[blue\] drawn in unit (location=(0.41421356237309515, 0.0)); seeds\_3 — a Point \[blue\] drawn in unit (location=(0.8284271247461903, 0.0)); seeds\_4 — a Point \[blue\] drawn in unit (location=(0.24264068711928566, 0.0)); seeds\_5 — a Point \[blue\] drawn in unit (location=(0.6568542494923806, 0.0)); seeds\_6 — a Point \[blue\] drawn in unit (location=(0.0710678118654755, 0.0)); pens — a Polygon \[gray\] drawn in unit (vertices=((0.0, -0.09), (0.2, -0.09), (0.2, 0.09), (0.0, 0.09)), filled=False); pens\_2 — a Polygon \[gray\] drawn in unit (vertices=((0.2, -0.09), (0.4, -0.09), (0.4, 0.09), (0.2, 0.09)), filled=False); pens\_3 — a Polygon \[gray\] drawn in unit (vertices=((0.4, -0.09), (0.6, -0.09), (0.6, 0.09), (0.4, 0.09)), filled=False); pens\_4 — a Polygon \[gray\] drawn in unit (vertices=((0.6, -0.09), (0.8, -0.09), (0.8, 0.09), (0.6, 0.09)), filled=False); pens\_5 — a Polygon \[gray\] drawn in unit (vertices=((0.8, -0.09), (1.0, -0.09), (1.0, 0.09), (0.8, 0.09)), filled=False); marks — a Math \[text\] that says "$0$" drawn in unit; marks\_2 — a Math \[text\] that says "$0.2$" drawn in unit; marks\_3 — a Math \[text\] that says "$0.4$" drawn in unit; marks\_4 — a Math \[text\] that says "$0.6$" drawn in unit; marks\_5 — a Math \[text\] that says "$0.8$" drawn in unit; marks\_6 — a Math \[text\] that says "$1$" drawn in unit; g0 — a Math \[text\] that says "$brace.l k alpha brace.r, quad k = 0, 1, dots, N$"; g1 — a Math \[text\] that says "$N + 1 thin upright("numbers,") quad N thin upright("intervals")$"; g2 — a Math \[text\] that says "$abs(brace.l j alpha brace.r - brace.l i alpha brace.r) \< 1 / N$"; head\_proof — a Heading that says "From Two Dots to a Fraction"

Actions:
- None.

##### [09:10.463](https://academa.ai/lectures/pigeonhole-principle-boxes?t=550.4634166666666)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [09:11.972](https://academa.ai/lectures/pigeonhole-principle-boxes?t=551.9724166666666): g3 is shown on the screen, written out.
- [09:20.076](https://academa.ai/lectures/pigeonhole-principle-boxes?t=560.0764166666667): g4 is shown on the screen, written out.

##### [09:24.89](https://academa.ai/lectures/pigeonhole-principle-boxes?t=564.8904166666666)

Narration: 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.

Board: unit — a Figure (x\_range=(-0.08, 1.08), y\_range=(-0.34, 0.3), aspect=(1.16, 0.64)); seeds — a Point \[blue\] drawn in unit; seeds\_2 — a Point \[blue\] drawn in unit (location=(0.41421356237309515, 0.0)); seeds\_3 — a Point \[blue\] drawn in unit (location=(0.8284271247461903, 0.0)); seeds\_4 — a Point \[blue\] drawn in unit (location=(0.24264068711928566, 0.0)); seeds\_5 — a Point \[blue\] drawn in unit (location=(0.6568542494923806, 0.0)); seeds\_6 — a Point \[blue\] drawn in unit (location=(0.0710678118654755, 0.0)); pens — a Polygon \[gray\] drawn in unit (vertices=((0.0, -0.09), (0.2, -0.09), (0.2, 0.09), (0.0, 0.09)), filled=False); pens\_2 — a Polygon \[gray\] drawn in unit (vertices=((0.2, -0.09), (0.4, -0.09), (0.4, 0.09), (0.2, 0.09)), filled=False); pens\_3 — a Polygon \[gray\] drawn in unit (vertices=((0.4, -0.09), (0.6, -0.09), (0.6, 0.09), (0.4, 0.09)), filled=False); pens\_4 — a Polygon \[gray\] drawn in unit (vertices=((0.6, -0.09), (0.8, -0.09), (0.8, 0.09), (0.6, 0.09)), filled=False); pens\_5 — a Polygon \[gray\] drawn in unit (vertices=((0.8, -0.09), (1.0, -0.09), (1.0, 0.09), (0.8, 0.09)), filled=False); marks — a Math \[text\] that says "$0$" drawn in unit; marks\_2 — a Math \[text\] that says "$0.2$" drawn in unit; marks\_3 — a Math \[text\] that says "$0.4$" drawn in unit; marks\_4 — a Math \[text\] that says "$0.6$" drawn in unit; marks\_5 — a Math \[text\] that says "$0.8$" drawn in unit; marks\_6 — a Math \[text\] that says "$1$" drawn in unit; g0 — a Math \[text\] that says "$brace.l k alpha brace.r, quad k = 0, 1, dots, N$"; g1 — a Math \[text\] that says "$N + 1 thin upright("numbers,") quad N thin upright("intervals")$"; g2 — a Math \[text\] that says "$abs(brace.l j alpha brace.r - brace.l i alpha brace.r) \< 1 / N$"; g3 — a Math \[text\] that says "$q = j - i, quad p = floor(j alpha) - floor(i alpha)$"; g4 — a Math \[text\] that says "$abs(q alpha - p) \< 1 / N$"; head\_proof — a Heading that says "From Two Dots to a Fraction"

Actions:
- [09:25.366](https://academa.ai/lectures/pigeonhole-principle-boxes?t=565.3664166666666): g5 is shown on the screen, written out.
- [09:31.113](https://academa.ai/lectures/pigeonhole-principle-boxes?t=571.1134166666666): g5 (the "1 / (q N)" part) is emphasized.
- [09:37.568](https://academa.ai/lectures/pigeonhole-principle-boxes?t=577.5684166666666): g5 (the "1 / (q N)" part) is no longer emphasized.
- [09:37.568](https://academa.ai/lectures/pigeonhole-principle-boxes?t=577.5684166666666): g5 (the "1 / q^2" part) is emphasized.
- [09:38.741](https://academa.ai/lectures/pigeonhole-principle-boxes?t=578.7414166666666): g5 (the "1 / q^2" part) is no longer emphasized.

##### [09:40.119](https://academa.ai/lectures/pigeonhole-principle-boxes?t=580.1194166666667)

Narration: 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.

Board: unit — a Figure (x\_range=(-0.08, 1.08), y\_range=(-0.34, 0.3), aspect=(1.16, 0.64)); seeds — a Point \[blue\] drawn in unit; seeds\_2 — a Point \[blue\] drawn in unit (location=(0.41421356237309515, 0.0)); seeds\_3 — a Point \[blue\] drawn in unit (location=(0.8284271247461903, 0.0)); seeds\_4 — a Point \[blue\] drawn in unit (location=(0.24264068711928566, 0.0)); seeds\_5 — a Point \[blue\] drawn in unit (location=(0.6568542494923806, 0.0)); seeds\_6 — a Point \[blue\] drawn in unit (location=(0.0710678118654755, 0.0)); pens — a Polygon \[gray\] drawn in unit (vertices=((0.0, -0.09), (0.2, -0.09), (0.2, 0.09), (0.0, 0.09)), filled=False); pens\_2 — a Polygon \[gray\] drawn in unit (vertices=((0.2, -0.09), (0.4, -0.09), (0.4, 0.09), (0.2, 0.09)), filled=False); pens\_3 — a Polygon \[gray\] drawn in unit (vertices=((0.4, -0.09), (0.6, -0.09), (0.6, 0.09), (0.4, 0.09)), filled=False); pens\_4 — a Polygon \[gray\] drawn in unit (vertices=((0.6, -0.09), (0.8, -0.09), (0.8, 0.09), (0.6, 0.09)), filled=False); pens\_5 — a Polygon \[gray\] drawn in unit (vertices=((0.8, -0.09), (1.0, -0.09), (1.0, 0.09), (0.8, 0.09)), filled=False); marks — a Math \[text\] that says "$0$" drawn in unit; marks\_2 — a Math \[text\] that says "$0.2$" drawn in unit; marks\_3 — a Math \[text\] that says "$0.4$" drawn in unit; marks\_4 — a Math \[text\] that says "$0.6$" drawn in unit; marks\_5 — a Math \[text\] that says "$0.8$" drawn in unit; marks\_6 — a Math \[text\] that says "$1$" drawn in unit; g0 — a Math \[text\] that says "$brace.l k alpha brace.r, quad k = 0, 1, dots, N$"; g1 — a Math \[text\] that says "$N + 1 thin upright("numbers,") quad N thin upright("intervals")$"; g2 — a Math \[text\] that says "$abs(brace.l j alpha brace.r - brace.l i alpha brace.r) \< 1 / N$"; g3 — a Math \[text\] that says "$q = j - i, quad p = floor(j alpha) - floor(i alpha)$"; g4 — a Math \[text\] that says "$abs(q alpha - p) \< 1 / N$"; g5 — a Math \[text\] that says "$abs(alpha - p / q) \< 1 / (q N) lt.eq 1 / q^2$"; head\_proof — a Heading that says "From Two Dots to a Fraction"

Actions:
- [09:42.347](https://academa.ai/lectures/pigeonhole-principle-boxes?t=582.3474166666666): answer is shown on the screen, written out.

##### [09:50.819](https://academa.ai/lectures/pigeonhole-principle-boxes?t=590.8194166666666)

Narration: 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.

Board: unit — a Figure (x\_range=(-0.08, 1.08), y\_range=(-0.34, 0.3), aspect=(1.16, 0.64)); seeds — a Point \[blue\] drawn in unit; seeds\_2 — a Point \[blue\] drawn in unit (location=(0.41421356237309515, 0.0)); seeds\_3 — a Point \[blue\] drawn in unit (location=(0.8284271247461903, 0.0)); seeds\_4 — a Point \[blue\] drawn in unit (location=(0.24264068711928566, 0.0)); seeds\_5 — a Point \[blue\] drawn in unit (location=(0.6568542494923806, 0.0)); seeds\_6 — a Point \[blue\] drawn in unit (location=(0.0710678118654755, 0.0)); pens — a Polygon \[gray\] drawn in unit (vertices=((0.0, -0.09), (0.2, -0.09), (0.2, 0.09), (0.0, 0.09)), filled=False); pens\_2 — a Polygon \[gray\] drawn in unit (vertices=((0.2, -0.09), (0.4, -0.09), (0.4, 0.09), (0.2, 0.09)), filled=False); pens\_3 — a Polygon \[gray\] drawn in unit (vertices=((0.4, -0.09), (0.6, -0.09), (0.6, 0.09), (0.4, 0.09)), filled=False); pens\_4 — a Polygon \[gray\] drawn in unit (vertices=((0.6, -0.09), (0.8, -0.09), (0.8, 0.09), (0.6, 0.09)), filled=False); pens\_5 — a Polygon \[gray\] drawn in unit (vertices=((0.8, -0.09), (1.0, -0.09), (1.0, 0.09), (0.8, 0.09)), filled=False); marks — a Math \[text\] that says "$0$" drawn in unit; marks\_2 — a Math \[text\] that says "$0.2$" drawn in unit; marks\_3 — a Math \[text\] that says "$0.4$" drawn in unit; marks\_4 — a Math \[text\] that says "$0.6$" drawn in unit; marks\_5 — a Math \[text\] that says "$0.8$" drawn in unit; marks\_6 — a Math \[text\] that says "$1$" drawn in unit; g0 — a Math \[text\] that says "$brace.l k alpha brace.r, quad k = 0, 1, dots, N$"; g1 — a Math \[text\] that says "$N + 1 thin upright("numbers,") quad N thin upright("intervals")$"; g2 — a Math \[text\] that says "$abs(brace.l j alpha brace.r - brace.l i alpha brace.r) \< 1 / N$"; g3 — a Math \[text\] that says "$q = j - i, quad p = floor(j alpha) - floor(i alpha)$"; g4 — a Math \[text\] that says "$abs(q alpha - p) \< 1 / N$"; g5 — a Math \[text\] that says "$abs(alpha - p / q) \< 1 / (q N) lt.eq 1 / q^2$"; answer — a Math \[text\] that says "$q = 5, quad p = 7, quad abs(sqrt(2) - 7 / 5) \< 1 / 25$"; head\_proof — a Heading that says "From Two Dots to a Fraction"

Actions:
- [09:55.358](https://academa.ai/lectures/pigeonhole-principle-boxes?t=595.3584166666666): A box is drawn around answer.

##### [10:2.576](https://academa.ai/lectures/pigeonhole-principle-boxes?t=602.5764166666665)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): answer is hidden from the screen — left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): g0 is hidden from the screen — left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): g1 is hidden from the screen — left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): g2 is hidden from the screen — left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): g3 is hidden from the screen — left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): g4 is hidden from the screen — left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): g5 is hidden from the screen — left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): head\_proof is hidden from the screen — left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): unit is hidden from the screen — left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): seeds is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): seeds\_2 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): seeds\_3 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): seeds\_4 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): seeds\_5 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): seeds\_6 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): pens is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): pens\_2 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): pens\_3 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): pens\_4 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): pens\_5 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): marks is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): marks\_2 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): marks\_3 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): marks\_4 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): marks\_5 is hidden from the screen — unit left the board.
- [10:12.178](https://academa.ai/lectures/pigeonhole-principle-boxes?t=612.1779166666665): marks\_6 is hidden from the screen — unit left the board.

##### [10:13.378](https://academa.ai/lectures/pigeonhole-principle-boxes?t=613.3779166666666)

Narration: 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.

Board: Empty.

Actions:
- [10:13.378](https://academa.ai/lectures/pigeonhole-principle-boxes?t=613.3779166666666): head\_recap is shown on the screen, written out.
- [10:15.316](https://academa.ai/lectures/pigeonhole-principle-boxes?t=615.3164166666667): recap is shown on the screen, written out.
- [10:18.822](https://academa.ai/lectures/pigeonhole-principle-boxes?t=618.8224166666666): recap (the "boxes are the possible answers" part) is emphasized.

##### [10:26.946](https://academa.ai/lectures/pigeonhole-principle-boxes?t=626.9459166666666)

Narration: 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.

Board: recap — a Block \[text\] that says "Party: items are people, boxes are the possible answers. Sequence: items are positions, boxes are pairs $(u\_i, d\_i)$. Approximation: items are multiples of $alpha$, boxes are intervals."; head\_recap — a Heading that says "Three Choices of Box"

Actions:
- [10:28.966](https://academa.ai/lectures/pigeonhole-principle-boxes?t=628.9664166666666): recap (the "boxes are pairs" part) is emphasized.
- [10:28.966](https://academa.ai/lectures/pigeonhole-principle-boxes?t=628.9664166666666): recap (the "boxes are the possible answers" part) is no longer emphasized.
- [10:36.118](https://academa.ai/lectures/pigeonhole-principle-boxes?t=636.1184166666667): recap (the "boxes are intervals" part) is emphasized.
- [10:36.118](https://academa.ai/lectures/pigeonhole-principle-boxes?t=636.1184166666667): recap (the "boxes are pairs" part) is no longer emphasized.
- [10:39.833](https://academa.ai/lectures/pigeonhole-principle-boxes?t=639.8334166666666): recap (the "boxes are intervals" part) is no longer emphasized.

##### [10:40.433](https://academa.ai/lectures/pigeonhole-principle-boxes?t=640.4334166666666)

Narration: 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.

Board: Unchanged from the preceding beat in this scene.

Actions:
- [10:41.06](https://academa.ai/lectures/pigeonhole-principle-boxes?t=641.0604166666667): closing is shown on the screen, written out.
- [10:50.531](https://academa.ai/lectures/pigeonhole-principle-boxes?t=650.5314791666666): closing is hidden from the screen — left the board.
- [10:50.531](https://academa.ai/lectures/pigeonhole-principle-boxes?t=650.5314791666666): head\_recap is hidden from the screen — left the board.
- [10:50.531](https://academa.ai/lectures/pigeonhole-principle-boxes?t=650.5314791666666): recap is hidden from the screen — left the board.