[ky3]

re: Chapter 15.8 on the so-called pigeonhole principle

Following Dijkstra’s EWD1094, here’s a way to solve the hairs-on-heads problem eschewing the language of pigeonholes and employing the fact that the mean is at most the maximum of a non-empty bag of numbers.

We are given that Boston has 500,000 non-bald people. The human head has at most 200,000 hairs. Show that there must be at least 3 people in Boston who have the same number of hairs on their head.

Each non-bald Bostonian must have a hair count between 1 and 200,000. The average number of such people per hair count is 500,000 / 200,000 = 2.5. The maximum is at least that; moreover, it must be a round number. So the maximum >= 3. QED.

[MaxBarraclough]

For good measure here's a link to Dijkstra's The undeserved status of the pigeon-hole principle.

https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD109...

[ky3]

For even better measure here's a slice of HN reactions to EWD1094:

https://news.ycombinator.com/item?id=46085897