.png)
Generally, the pigeonhole principle is stated as follows: If M objects are put into N boxes > N then there exists at least one box with more than one item. Once you process the statement it’s easy to take it to be stupidly obvious and stating it seems redundant.
One can argue that the principle's simplicity is what makes it so powerful as a tool, the case that its applicability hinges on the connections hiding in plain sight makes it special. When the use case for something so simply stated is so vast… maybe we shouldn’t be surprised with its praise and the apparent glory assigned to it; But if the deducing logical step hinges on this simple principle, does that mean the theorem we are trying to prove is also simple when stripped down?
When I set out to cover this topic, I wanted to find concepts that are considered hard and take them apart with the principle, almost disturbingly so… It makes the topic in question seem like a logical gimmick. During the process I could see how much pushing and shoving you can subject mathematical reasoning to, to boil it down, till its simplicity is unnerving and can be solved using elementary arguments.
The first problem is a puzzle that I got from here. The premise is a football gambling form called a toto.
The following is the setup:
The coming Sunday 13 football matches are going to be played.
Each match has 3 possible outcomes 1,2 or x.
A toto form consists of 13 columns for each of the matches
An example of a filled toto form for 7 games
S.No | Game 1 | Game 2 | Game 3 | Game 4 | Game 5 | Game 6 |
|---|---|---|---|---|---|---|
1) | 1 | 1 | x | 2 | 2 | 1 |
2) | x | 2 | 2 | 2 | x | x |
It can be seen that the total number of possible results are 3^13.
Our aim is to find the minimum number of rows that we have to fill so that at least in one of the rows we predict correctly at least 5 of the results of Sunday.
Solution:
If we fill 3 columns each with a separate entry for 1st row, we are guaranteed a match in one of the columns. The catch is that the puzzle is easily solvable if you repeat the same entry in all of the columns as below, take 3 toto forms and fill one as [1,1,1,1….1] the other as [2,2,2,2…..2] and yet the last one with [x,x,x,x,x,…..x]
This guarantees us the 5 match predictions will match in at least one of the columns;
Now you may be asking how does this even happen?
We can verify it as follows— suppose someone decides to fix the matches to thwart your efforts; a “best” they could achieve is this [1,1,1,1,2,2,2,2,x,x,x,x, 1 ]
Notice the last entry is highlighted, this is the important aspect in this puzzle. The reasoning behind the four 1s, 2s and ‘x’s is that if they place any more they let you “win”; but the 13th entry forces them to let you match 5 times in the first row.
How all this is related to pigeons and holes is discussed in length in the disposition linked above.
Now this very line of logic can be used to prove a result from the study of vector spaces; We can show that if the union of subspaces is a subspace then the individual sub-spaces have to be subsets of each other; this method is, I suspect, the only way to prove it without using contradiction; which if true is probably a good thing; goes to show that between all the wordplay of vectors and spaces… the theorem is in fact nothing more than a reiteration of the same rule in a different context.
Overusing the same deductive logic to prove these different seeming results questions may bring the question if the results are mathematical elegance or just plain cumbersome. The more we delve into these theorems concerned about the mathematical connections and patterns, the more it seems to lack in most ways unknown information or knowledge; its intricacy lies arguably in the way it presents itself.
Next is the use of principle for a proof of a result from combinatorics called Sperner’s lemma,
There is a need to specify what a Sperner colouring is, to discuss the lemma.
The Sperner colouring of vertices is as follows:
Take a triangle, colour each edge uniquely (3 vertices so 3 colours to be exact)
Now make any number of small triangles inside the triangle as in the figure.
Now colour all of the vertices, but only using colour of vertices if the vertex lies on the edge of the parent triangle. (If one of the vertices of the triangle ends up on the edge of the parent triangle ABC in figure… say on AB it has to have the color A or color B)
The lemma states that there is at least one child triangle with 3 distinct coloured vertices.
Proof:
Observation 1:
If a triangle has 3 distinctly coloured vertices, then if we walk around it from a vertex to itself, we observe the vertex switches colour 3 times.
Observation 2:
If we sum the colour switches for a triangle with anything other than 3 distinct coloured vertices we get an even number of switches.
Deduction 1:
If we walk around all the triangles once and sum the colour switches the sum is going to be odd only if there is a triangle as in observation 1.
Observation 3:
The net sum obtained in deduction 1 can also be computed by selecting each edge in the diagram and counting it if it connects vertices of varying colours.
Observation 4:
All edges completely in the interior of ABC must be counted twice (as they are shared by 2 triangles) and the rest lying on ABC are counted once.
Deduction 2:
The sum from the interior edges is always going to be an even number as explained in observation 3; the sum from edges on the outskirts is going to be odd.
(The is a critical point in proving and it works only because of the weird property of Sperner coloring [property 3])
And there we have it… the net sum must be odd.
{the principle here is in the form of grouping into even baskets-an odd number to get an overflow or an underflow}
The analogue of this lemma in topology is the Borsuk-Ulam Theorem, which gives the “cool” results like “there will always be two points on the opposite end of earth that have the same temperature and pressure”. And if nothing… There is at least something humbling about it relying in a way on the same pillar as the pigeonhole principle.
Commentaires