pigeonhole

concept:

• there are 9 holes, 10 pigeons
• if there are n+1 items to go in n containers, at least 1 container must contain 2 or more items
• i.e.: if there are n items to go in k containers where n>k then at least one container must contain at least $\frac{n}{k}$ items

School example:

At a school with 1000 students, what is the maximum and the minimum number of students that can share the same birthday?

• Max = 1000
• $\frac{1000}{365}=2\frac{270}{365}$ → rounded up: minimum is 3

Proof of the pigeonhole principle

Assume that all contain less than $\frac{n}{k}$ items.

• tf total number of items $<k\ast \frac{n}{k}$
• Total number of items $<n$
  But there are n items, so the assumption must be false;
  tf At least one container must contain at least $\frac{n}{k}$ items.