Pigeonholes

TooManyPigeons

(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 \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:

Let’s work under the assumption that friendship is an irreflexive, symmetric relation.
That essentially means person P is not a friend of himself and if P and Q are friends then Q and P are friends (and conversely).
The number of friends of person P is therefore a number in \{0,1,...,n-1\}.
If P has n-1 friends then P is friends with everyone and since the relation is symmetric, there can be no person with 0 friends.
Similarly if P has 0 friends then there can be no person with n-1 friends.
Thus these two cases cannot occur simultaneously, i.e if someone has 0 friends then no one can have n-1 friends and if someone has n-1 friends then no one can have 0 friends.
Therefore the number of friends of P is either in \{1,...,n-1\} or in \{0,1,...,n-2\}
Both sets are of size n-1.
We are now in a position to apply the pigeonhole principle:
Pigeons: n people
Pigeonholes: n-1 possible friendship relations (P belongs to pigeonhole k iff P has k friends)
Hence by the pigeonhole principle there must be two people with the same number of friends.
                                                                                                                                                                                               \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:

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 \{Ace=0,...,King=12\} and work mod\;13.
The clockwise distance between two card ranks r,s is easily seen to satisfy either dist(r,s) \leq 6 or dist(s,r) \leq 6.
This again is a simple consequence of the pigeonhole principle, for if both distances were > 6 then we can count up at least 7.2=14 cards of the same suit (by going clockwise and anti-clockwise between r and s)
The pigeonhole principle applied with:
Pigeons: The 14 cards of same suit
Pigeonholes: 13 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 \leq 6 by switching the roles of the spade cards if necessary (why?).
Let’s now impose a second ordering on the deck
\heartsuit Ace=0\leq...\leq\heartsuit King=12\leq  \spadesuit Ace=13\leq...\leq\spadesuit King=25\leq  \diamondsuit Ace=26\leq...\leq\diamondsuit King=38\leq  \clubsuit Ace=39\leq...\leq\clubsuit King=51
With remaining 3 cards he can achieve 3!=6 distinct permutations.
Hence the magician and accomplice can agree to represent each of the 6 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:
Lowest,Mid,Highest \Rightarrow Distance = 1
Lowest,Highest,Mid \Rightarrow Distance = 2
Mid,Lowest,Highest \Rightarrow Distance = 3
Mid,Highest,Lowest \Rightarrow Distance = 4
Highest,Lowest,Mid \Rightarrow Distance = 5
Highest,Mid,Lowest \Rightarrow Distance = 6
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 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:
\forall i \in \{1,...,6\} let C_{i} denote the set of id numbers belonging to Country_{i}
Clearly \bigsqcup _{i=1}^6 C_{i} = \{1,...,1978\} (disjoint union)
By the generalized pigeonhole principle there must be at least \lceil\frac{1978}{6}\rceil = 330 members belonging to one of the countries.
w.l.o.g assume |C_{1}|\geq 330.
If \exists c_1,c_2,c_3 \in C_{1} s.t c_1 + c_2 = c_3 then we are done, so let us assume there are no such triples.
Let m_{1}=max\{c:c \in C_{1}\} and form M_{1}=\{m_{1}-c:c \in C_{1} \backslash \{m_{1}\}\}.
Then |M_{1}|\geq329 and M_{1} \bigcap C_{1} = \emptyset by our assumption of non-existance of c_1,c_2 \in C_{1} s.t c_1 + c_2 = m_{1}.
This means M_{1} \subseteq \bigsqcup _{i=2}^6 C_{i}.
We may now repeat the argument for M_{1} instead of C_{1} applying the principle on remaining 5 countries.
This yields at least \lceil\frac{329}{5}\rceil = 66 members in M_{1} belonging to one of the remaining 5 countries.
W.l.o.g assume S \subseteq M_{1} \bigcap C_{2} s.t |S| \geq 66.
We repeat the argument by putting m_{2}=max\{s:s \in S\} and form M_{2}=\{m_{2}-s:s \in S \backslash \{m_{2}\}\} so that |M_{2}|\geq65 with M_{2} \bigcap C_{2} = \emptyset.
We need to be a bit careful here.
What if M_{2} \bigcap C_{1} \neq \emptyset?
Suppose for a contradiction that m_{2}-c \in M_{2} \bigcap C_{1}.
Then m_{2},c \in M_{1}\Rightarrow \exists c_{1},c_{2} \in C_{1} s.t m_{2} = m_{1} - c_{1}, c = m_{1} - c_{2}.
Thus m_{2}-c = (m_{1} - c_{1}) - (m_{1} - c_{2}) = c_{2} - c_{1} \in C_{1}.
This is of course a contradiction since by assumption \nexists c \in C_{1} s.t c = c_{2} - c_{1}.
Hence M_{2} \subseteq \bigsqcup _{i=3}^6 C_{i}.
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 \lceil\frac{65}{4}\rceil = 17 members belonging to one of remaining 4 countries and |M_{3}|\geq16 s.t M_{3} \subseteq \bigsqcup _{i=4}^6 C_{i}.
There are at least \lceil\frac{16}{3}\rceil = 6 members belonging to one of remaining 3 countries with |M_{4}|\geq5 s.t M_{4} \subseteq \bigsqcup _{i=5}^6 C_{i}.
There are at least \lceil\frac{5}{2}\rceil = 3 members belonging to one of remaining 2 countries with |M_{5}|\geq2 s.t M_{5} \subseteq \bigsqcup _{i=6}^6 C_{i}= C_{6}.
Finally the elements of M_{6} either belong to C_{6} in which case we are done (note that there is at least one since |M_{5}|\geq2), or they do not belong to any C_{i} in which case we have a contradiction since \bigsqcup _{i=1}^6 C_{i} = \{1,...,1978\}.
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.
Advertisements
This entry was posted in Combinatorics, Uncategorized and tagged , , , , , , . Bookmark the permalink.

One Response to Pigeonholes

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s