The pigeonhole principle is a good starting point for students who want to get to know the creative side of proofs.
pigeonhole
The word “pigeonhole” can refer to a hole in which pigeon roosts or a series of roughly square recesses in a desk in which one could sort correspondence. Either way, the firs and easiest version of the pigeonhole principle is that if you have more “things” (e.g. pigeon) than you have “containers” (e.g pigeonhole) there must be a container holding at least two things.
pigeonhole
Consider the following: we have 6 pigeons trying to roost in a coop with 5 pigeonholes; two birds will have to share. If we have 7 letters to sort and we have 6 pigeonholes in our desk, we have to put two letters in the same compartment.
The “things” and the “containers” don’t necessarily have to be interpreted in the strict sense that things go into the containers. One can also apply with, for instance, 13 people in a room some pair of people will have been born in the same month – things are the people and the months of the year as the container.
The abstract way to phrase the pigeonhole principle is:
Note that an injectives implies the uniqueness of the preimages - a one to one correspondence between the range and the domain.
Pigeonhole principle is very powerful. We can use it to prove a host of existential results – some are fairly silly, others are deep.
- There are two people in New York City having exactly the same number of hairs on their heads
- There are two books in the library that have the same number of pages
- Given n married couples if we choose n+1 people we will be forced to choose both members of some couple
- If you pick five numbers from the integers 1 to 8, then two of them must add up to nine.
- For every 27 word sequence in the US constitution, at least two words will start will the same letter.
Stronger Pigeonhole Principle
Suppose we have 6 pigeonholes in a desk each can hold 10 letters.
What number of letters will guarantee that one of the pigeonholes is full?
The largest number of letters we could have without having 10 in some pigeonhole is 9x6=54, so if there are 55 letters we must have 10 letters in some pigeonhole.
Generally, if we have n containers, each capable of holding m objects, than if there are nx(m-1) + 1 objects placed in the containers, we will be assured that one of the containers is at capacity. The ordinary pigeonhole is the special case m=2 of this stronger version. There is even a stronger version where m varies.
The strong form of the pigeonhole principle:
Application of the strong Pigeonhole Principle
Consider the following example [1]:
A box contains three pairs of socks colored red, blue, and white, respectively. Suppose I take out the socks without looking at them. How many socks must I take out to be sure that they will include a matching pair?
In this problem, the "things" are the socks, while the 3 colors are the "containers". With this example, we set m1 = 2, m2=2, m3=2 and so using the strong Pigeonhole Principle we have (1+ (2-1) + (2-1) + (2-1)) = 4, in order for at least a pair or a matching socks is taken out.
Disclaimer: this is a summary of section 7.3 from the book A Gentle Introduction to the Art of Mathematics: by Joe Fields, the content apart from rephrasing is identical, most of the equations are screenshots of the book and the same examples are treated.
Thank you for reading ...
