The counting methods and pigeonhole principle is firstly created by Johann Dirichlet in year 1834 with the name Schubfachprinzip (shelf principle or drawer principle). Hence it is also generally known as Dirichlet's box principle or Dirichlet's drawer principle. In French it is known as "le principe des tiroirs de Dirichlet" for the principle of the drawers of Dirichlet, and in Portugese it is called "principio da casa dos pombos" for the house of pigeons principle. Besides that, in Russian and some other languages, it is constricted to simply "Dirichlet principle"- which could be refer to the minimum principle for harmonic functions. The original name of "principio dei cassetti" is still in used in Italy. Although the most straight forward application is to finite sets (such as pigeons and boxes), it is also used with infinite sets that cannot be put into one-to-one correspondence. In order to do so it requires the formal statement of the pigeonhole principle, which is "there does not exist an injective function on finite sets whose codomain is smaller than its domain". The more advanced mathematical proofs such as Siegel's lemma build upon this more general concept.
What is the Pigeonhole Principle? In mathematics as well as computer science, the pigeonhole principle states that if a items are put into b pigeonholes with a > b, then at least one pigeonhole will contain more than one item. In real-life, this theorem is exemplified by truisms such as "there must be at least two left shoes or two right shoes in a group of three shoes". This is an example of a counting argument, and even though it seems instinctive it can be used to exhibit possibly unpredicted results. For instance, there are 5 pigeonholes around. A pigeon is delivering 6 mails and has to place all its mails into the available pigeonholes. With only 5 pigeonholes around, there bound to be 1 pigeonhole with at least 2 mails. Thus, the general rule states when there are k pigeonholes and there are k+1 mails, then there will be 1 pigeonhole with at least 2 mails. A more advanced version of the principle will be the following: If ab + 1 pigeons are placed in b pigeonholes, then there will be at least one pigeonhole with a + 1 or more pigeons in it.
3. Results of research and real world examples
(i) Pigeonhole Principle and Geometry
a. Dartboard applications
In this example, a specified number of darts are thrown onto a dartboard where its general shape and size are known. Then, we are to determine the possible maximum distance between two darts. As all the questions are concerning the pigeonhole principle, identifying the pigeons and pigeonholes is the hardest part.
Example 1:
Nine darts are thrown onto a circular dartboard of radius 20 units. Can we prove that there will always be two darts which are at most 20 units apart?
To show that the last statement is always true, we first divide the circle into eight equal sectors as shown;
Untitled.png
Let each dart to be a pigeon and each sector to be a pigeonhole, we will have nine pigeons to go into eight pigeonholes. According to the pigeonhole principle, there will be a minimum of two darts in at least one sector. Since the greatest distance between two points lying in a sector is 20 units, the statement is proven to be true in any case.
In fact, it is also possible to prove the situation with only seven darts. In this case, the circle is divided into six sectors and all the others follow. However, take note that this is not always true any longer with only five darts or less.
Example 2:
Nineteen darts are thrown onto a dartboard which is shaped as a regular hexagon with side length of 1 unit. Can we prove that there are two darts within units of each other? Again, we identify our pigeonholes by dividing the hexagon into six equilateral triangles as shown below.
With the six triangles as our pigeonholes and the 19 darts as pigeons, we find that there must be at least one triangle with a minimum of 4 darts in it.
Now, considering the best case scenario, we will have to try an equilateral triangle of side 1 unit with 4 points inside.
If we try to put the points as far apart from each other as possible, we will end up assigning each of the first three points to the vertices of the triangle. The last point will then be at the exact centre of the triangle. As we know that the distance from the centre of the triangle to each vertex is two-third of the altitude of this triangle, that is, units, we can see that it is definitely possible to find two darts which are units apart within the equilateral triangle.
b. Encompassing problems
Consider the following problem:
If there are 19 points placed in a random way, into a square of side 1 unit. How are we able to prove that 3 of these points can be enclosed by a circle of radius units?
In order to prove the outcome, we can divide the square into 9 equal smaller squares of side units each. According to the Pigeonhole Principle, at least one of these small squares (known as "pigeonholes") should contain at least 3 points (known as "pigeons"). Or else, each of the small squares will have 2 or less points which make the total number of points less than 18.This is incorrect as it contradict to the fact that we have 19 points in the first case.
radius
Then the circle circumvented in the region of the particular square with the three points inside should have the radius = = = < = units .
The technique mentioned above can be useful in analyzing the accuracy and precision of weapons in shooting tests and practices.
(ii) Application of pigeonhole principle in card games
We would like to explain the application of pigeonhole principle in two exciting card tricks:
a. Combinatorial Card Trick :
The trick is:
An unsuspecting spectator is asked by a magician to pick five cards from a regular deck of playing cards randomly. These cards are not shown to the magician by the spectator, but it is shown to the magician's assistant. After looking at the five cards, the assistant chooses four of them, and these four cards in certain ordered manner is shown to the magician. The fifth hidden card is immediately identified by the magician.
How does the trick work?
The following is an explanation of our working approach:
(1) Firstly, note that there must be two cards of the same suit in any hand of five cards (an application of Pigeonhole Principle). The first card shown by the assistant to the magician is one of these two cards. The hidden card which the magician must discover is the other card of the same suit that never shown. Hence, the assistant could simply converse the suit of the hidden card since the hidden card has identical suit as the first card shown to the magician. In order to specify the value of the hidden card is a little hard but can be done with a little "circular counting" method which we will explain below.
Number the cards in a circular set from 1(ace) to 11 (jack), 12 (queen) and 13 (king) so that 1 follows 13 and arrange the list in a clockwise direction.
Let any two cards to be X and Y. The distance (X,Y) is known as the clockwise distance from X to Y. For any two cards X and Y either distance (X,Y) or distance (Y,X) will always be less than or equal to 6. According to the Pigeonhole Principle, we know that if they are both 7 or more, then there will be at least 2 x 7 = 14 cards in a standard suit of cards!!
Example :
Cards: 4 and Queen (12)
distance (Queen, 4) = 5; distance (4, Queen) = 8
Cards: Ace (1) and 8
distance (Ace, 8) = 7; distance (8, Ace) = 6
(2) The following is the solving methods:
The two cards of the same suit, X and Y, the assistant shows the magician card X such that distance (X, Y) is less than or equal to 6.
For instance, given the option between the four of clubs and the Queen of clubs, the assistant reveals the Queen (since distance (Queen, 4) = 5 and distance (4, Queen) = 8). The four of clubs remains hidden.
When the two same-suit cards are the four of hearts and the five of hearts, the assistant chooses the four (since distance (4,5) = 1 but distance (5,4) = 12) leaving the five of hearts as the hidden card.
(3) Lastly, the assistant arrange the last three cards to instruct a number from 1 to 6 which is the distance from the value of first card to that of the hidden card. A fast calculation lets the magician determine the value of the hidden card. Note that although the magician must interpret only one of 6 possibilities, it should not be a problem even to a slowest magician.
To simplify the explanation for the last step involved, we can rank each card a number from 1 to 52. For instance,
the ace of spade can be numbered 1 (the highest ranking card),
ace of heart numbered 2,
ace of club numbered 3,
ace of diamond numbered 4,
king of spade numbered 5,
……………………………..,
queen of spade numbered 9,
……………………………….,
jack of spade numbered 13,
……………………………….,
10 of spade numbered 17,
……………………………. ,
……………………………. ,
2 of diamond numbered 52 (the lowest ranking card).
We will now proceed to explain the last step using the following example:
Example:
Suppose the five cards chosen are the following:
3 of Hearts (numbered 46)
5 of Spades (numbered 37)
6 of Clubs (numbered 35)
7 of Hearts (numbered 30)
2 of Diamonds (numbered 52)
The accomplice notices that the 3 and the 7 have the same suit-- hearts. Since the distance( 3 ,7) = 4 and distance(7, 3) = 9, the accomplice chooses the 3 as the first card to show the magician, leaving the 7 of hearts as the hidden card. The magician now knows that the suit of the mystery card is hearts. The accomplice's next task is thus to let the magician know that he must add the value 4 to the number 3 to obtain the final value of 7 for the hidden card!
How can he achieve this? Basically, he can arrange the other three cards in 3! = 6 ways. Based on the numbering method explained earlier, the 3 remaining cards can be ranked 1st, 2nd and 3rd . In our example, the 6 of Clubs will be ranked 1, the 5 of Spades will be ranked 2 and the 2 of Diamonds will be ranked 3. The accomplice may agree with the magician earlier that the arrangement of these 3 cards represent specific numbers as shown below:
Order in which 3 remaining cards are shown
Number represented by the arrangement
1, 2, 3
1
1, 3, 2
2
2, 1, 3
3
2, 3, 1
4
3, 1, 2
5
3, 2, 1
6
Thus in our example, the accomplice should display the cards in the following manner: firstly, the 5 of Spades, then the 2 of Diamonds and lastly, the 6 of Clubs !
b. Permutation Card Trick:
Here's the trick:
A magician asks an unsuspecting observer to randomly arrange 10 cards which are labelled 1 to 10 in a hidden "face down" manner. The participant does not show the arrangement of these cards to the magician, but does show them to the magician's accomplice. The accomplice looks at the ten cards and flips over six of the cards in a certain ordered manner to reveal their values to the magician. The magician immediately identifies the values of the four remaining unknown cards.
How does the trick work?
We first note that by applying the Pigeonhole Principle, we can show that in any permutation of 10 distinct numbers there exists an increasing subsequence of at least 4 numbers or a decreasing subsequence of at least 4 numbers. (refer next section of our discussion). These are the numbers that remain hidden in our trick. The magician will know that the sequence is increasing if the accomplice flips over the other six cards from the left to right and it is decreasing if the other six cards are flipped over from the right to the left.
We will now proceed to explain the trick behind the game:
The trick behind the game:
Given any sequence of mn+1 real numbers, some subsequence of (m+1) numbers is increasing or some subsequence of (n+1) numbers is decreasing.
We shall prove the result by 'Contradiction' method.
Assume that the result is false. For each number x in the sequence, we have the ordered pair (i, j), where i is the length of the longest increasing subsequence beginning with x, and j is the length of the longest decreasing subsequence ending with x. Then, since the result is false, 1 ï‚£ i ï‚£ m and 1 ï‚£ j ï‚£ n. Thus we have mn+1 ordered pairs, of which at most mn are distinct. Hence by the Pigeonhole Principle, two members of the sequence, say a and b, are associated with the same ordered pair (s, t). Without loss of generality, we may assume that a precedes b in the sequence.
If a<b, then a, together with the longest increasing subsequence beginning with b, is an increasing subsequence of length (s+1), contradicting the fact that s is the length of the longest increasing subsequence beginning with a. Hence a  b. But then, b, together with the longest decreasing subsequence ending with a, is a subsequence of length (t+1), contradicting that the longest decreasing subsequence ending with b is of length t. This is clearly a contradiction to our assumption and so the result must be true.
Thus, in our trick, we should have an increasing subsequence of at least (3+1) numbers or a decreasing subsequence of at least ( 3+ 1) numbers in a permutation of (3x3+ 1) distinct numbers!
Here is an example of how the trick can be performed:
Example: Suppose a person arrange the 10 cards in the following manner:
5, 7, 8, 10, 9, 1, 6, 4, 2, 3
He notices that an increasing subsequence can be 5, 7, 8, 10 whereas a decreasing subsequence can be 10, 9, 6, 4
For the increasing subsequence, he should leave the first four cards untouched and flips the other six cards over in a leftward manner as shown:
9
4
6
2
3
1
Direction of flip
The magician on realising that the four missing numbers are 5, 7, 8 and 10 and the leftward direction of flip, will thus proclaim the 4 hidden numbers to be 5, 7, 8, and 10 respectively!
9
7
8
2
3
5For the decreasing subsequence, he should leave the cards bearing the numbers 10, 9, 6, 4 untouched and flips the other six cards over in a rightward manner as shown:
Direction of flip
The magician on realising that the four missing numbers are 4, 6, 9 and 10 and the rightward direction of flip, will thus proclaim the 4 hidden numbers (from left to right) to be 10, 9, 6, 4 respectively.
Conclusion
Although the Pigeonhole Principle seems simple and trivial, it is extremely useful in helping one to formulate and facilitate calculation and proving steps for numerous important Mathematical results and applications. We have included just a substantial amount of its applications in our project discussion. More importantly, we will like to show that a simple Mathematical concept like the Pigeonhole Principle does have numerous interesting and beneficial applications in our daily life.
