More Things Than Places
Last timeCounting the Same Thing Twice
If there are more things than places, two of them share. The certain version is obvious; the probable version arrives far sooner than intuition allows, and it is why collisions must be designed for.
Thirteen people are in a room. Two of them were born in the same month.
That is not a probability, it is a certainty, and the argument takes one line:
there are twelve months, and if every month held at most one person the room
could not hold more than twelve.
| step | step | the claim | why |
|---|---|---|---|
| 1 | suppose not | suppose no two people share a month | this is the thing to be ruled out |
| 2 | what that means | each of the twelve months holds at most one person | that is what sharing nothing means |
| 3 | count the people | then the room holds at most twelve people | twelve months, at most one each |
| 4 | but | the room holds thirteen | given |
| 5 | so | the supposition is impossible, and two people share a month | there is no other way out |
| 6 | notice what was not used | nothing about who the people are or how birthdays are distributed | which is why the conclusion is a certainty rather than a probability |
Two consequences of that one line argument are worth having, because neither
is obvious.
No compression scheme can shrink every input. If it could, then every file of a
thousand bits would map to some shorter file, and there are fewer short files
than thousand bit files, so two different inputs would compress to the same
thing and could not both be recovered. That is the pigeonhole principle and
nothing else, and it settles a claim that otherwise invites endless argument.
In any group of people, two of them have the same number of friends within the
group, provided nobody is friends with themself and the group is larger than
one. The possible friend counts in a group of n people run from nought to n
minus one, which is n values, but nought and n minus one cannot both occur, so
there are really n minus one available values for n people.
Likely long before it is certain
The certainty needs three hundred and sixty six people to force a shared
birthday. The interesting number is far smaller, and the fourth lesson already
produced it.
The lesson stops here
2 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents