## Pigeonholes

(Picture uploaded to wikipedia by Brendan McKay)

#### Meanwhile let’s state a slight generalization of the principle:

Proposition: Generalized pigeonhole principle

If n pigeons are placed into m pigeonholes then there is at least one pigeonhole containing at least $\lceil\frac{n}{m}\rceil$ pigeons

To illustrate the principle in action, lets consider below three problems.
The main challenge is usually to identify a suitable pigeonhole.

Problem 1 (Friendship):

Prove that in any group of n>1 people there exist at least two people having the same number of friends (among the group).

Solution:

##### $\square$

Problem 2 (Magic Trick):
A magician is to perform a card trick to an audience using a standard deck of 52 cards.
He asks a member of the audience to choose 5 arbitrary cards from the deck, and only show them to the magicians accomplice.
The accomplice looks at the 5 cards, selects 4 and shows them to the magician one at a time.
The magician subsequently identifies the fifth hidden card.

How does he do it?

Solution:

##### Hence lo and behold the magician can uniquely determine the suit and rank of the hidden fifth card! $\;\;\square$

Problem 3 (IMO 1978 Q6):
There is an international society with 1978 members.
All members are from 6 distinct countries and each has a unique id number in {1,2,…,1978}.
Prove that there exist three members from the same country such that the sum of the id numbers of two of them equals the third.
Solution:

##### This concludes our argument. $\square$

I hope you found at least one of these problems to be interesting applications of this deceivingly obvious principle.
It turns out that this idea can be generalized further into something called Ramsey Theory (which is the study of partitions of larger structures). A post on this may appear at some point in the future since there are many nice applications using only the basics.

Below are some more problems for you to try:

Exercise 1 (Divisibility – Easy):
Prove that among 11 arbitrary integers there exist at least two whose difference is divisible by 10 (Hint: work mod 10).

Exercise 2 (Darts – Easy):
6 darts are thrown at a dartboard of radius 1.
Prove that there exist two darts which are of distance less than 1 apart.

Exercise 3 (Erdos-Szekeres Theorem – Intermediate):
Prove that for any sequence of $n^{2}+1$ real numbers there exist a non-increasing subsequence of length $n$ or a non-decreasing subsequence of lenght $n$.