(Picture uploaded to wikipedia by Brendan McKay)

#### In this post we shall be looking at a seemingly obvious fact from extremal combinatorics, namely the *pigeonhole principle.*

#### The principle states that putting *n* pigeons into *m* pigeonholes, with *n > m* implies there must be at least one pigeonhole containing more than one pigeon.

#### This elementary counting argument, despite its simplicity has some dazzling applications. We will look at a few of varying difficulty.

#### 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 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:**

##### Let’s work under the assumption that friendship is an irreflexive, symmetric relation.

That essentially means person is not a friend of himself and if and are friends then and are friends (and conversely).

##### The number of friends of person is therefore a number in .

##### If has friends then is friends with everyone and since the relation is symmetric, there can be no person with friends.

##### Similarly if has friends then there can be no person with friends.

##### Thus these two cases cannot occur simultaneously, i.e if someone has friends then no one can have friends and if someone has friends then no one can have friends.

##### Therefore the number of friends of is either in or in

Both sets are of size .

##### We are now in a position to apply the pigeonhole principle:

**Pigeons**: people

**Pigeonholes**: possible friendship relations ( belongs to pigeonhole iff has friends)

##### Hence by the pigeonhole principle there must be two people with the same number of friends.

**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:**

##### By the pigeonhole principle there must be at least two cards of the same suit among the 5 chosen cards.

##### W.l.o.g assume there are at least two cards of spade suit.

##### The accomplice can make sure the 4 cards he chooses does not contain both spades, and communicate the suit of the fifth card by revealing the remaining spade card first.

##### The accomplice has now left to communicate the rank of the fifth card using the remaining 3 cards.

This can be accomplished using modular arithmetic.

We can assign a natural number to each card as follows and work .

The clockwise distance between two card ranks is easily seen to satisfy either or .

This again is a simple consequence of the pigeonhole principle, for if both distances were then we can count up at least cards of the same suit (by going clockwise and anti-clockwise between and )

The pigeonhole principle applied with:

**Pigeons**: The cards of same suit

**Pigeonholes**: ranks in a standard deck

implies there are at least two cards of the same suit and rank which is a contradiction.

##### The accomplice will want to express the clockwise distance to the hidden spade card from the spade card revealed first.

Note that the clockwise distance can always be made by switching the roles of the spade cards if necessary (why?).

##### Let’s now impose a second ordering on the deck

With remaining 3 cards he can achieve distinct permutations.

Hence the magician and accomplice can agree to represent each of the distances according to the relative ranks on the 3 cards by virtue of the ordering in which they are presented.

##### For instance distances could be interpreted according to below ordering scheme:

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

**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 problem can be attacked through repeated applications of the pigeonhole principle, each time eliminating a pigeon hole until we reach an absurdity.

##### You can probably guess what the pigeonholes are going to be, namely the countries (you guessed it).

##### Let’s introduce some notation:

let denote the set of id numbers belonging to

##### Clearly (disjoint union)

##### By the generalized pigeonhole principle there must be at least members belonging to one of the countries.

w.l.o.g assume .

##### If s.t then we are done, so let us assume there are no such triples.

##### Let and form .

##### Then and by our assumption of non-existance of s.t .

##### This means .

##### We may now repeat the argument for instead of applying the principle on remaining 5 countries.

##### This yields at least members in belonging to one of the remaining 5 countries.

W.l.o.g assume s.t .

##### We repeat the argument by putting and form so that with .

##### We need to be a bit careful here.

What if ?

##### Suppose for a contradiction that .

Then s.t .

Thus .

This is of course a contradiction since by assumption s.t .

##### Hence .

##### Now streamlining remaining iterations of the argument, at each step assuming no two ids sum up to a third within the same set (otherwise nothing left to prove),

##### we find at least members belonging to one of remaining 4 countries and s.t .

##### There are at least members belonging to one of remaining 3 countries with s.t .

##### There are at least members belonging to one of remaining 2 countries with s.t .

##### Finally the elements of either belong to in which case we are done (note that there is at least one since ), or they do not belong to any in which case we have a contradiction since .

##### This concludes our argument.

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 real numbers there exist a non-increasing subsequence of length or a non-decreasing subsequence of lenght .

Pingback: Fermat’s Last Theorem (mod p) | Mathematical Mélange