The Pigeon Hole Principle: 7 gorgeous proofs

Let's say there are more pigeons than pigeon holes. Then, if all the pigeons are in the holes, at least one of the holes must house at least two of the pigeons. Completely obvious. However, this unassuming pigeon hole principle strikes all over mathematics and yields some really surprising, deep and beautiful results. In this video I present my favourite seven applications of the pigeon hole principle.

Starting with a classic, the puzzle of hairy twins, we then have a problem with pigeons on a sphere, a pigeon powered explanation of recurring decimals, some party maths, a very twisty property of the Rubik’s cube, a puzzler from the 1972 International Mathematical Olympiad, and, finally, what some people consider to be the best mathematical card trick of all time.

00:00​ Intro
01:49​ Chapter 1: Hairy twins
06:46​ Chapter 2: Five pigeons on a sphere
08:16​ Chapter 3: Repeating decimals
13:14 Chapter 4: Partying pigeons
17:00​ Chapter 5: Repeating Rubik
22:20​ Chapter 6: Pigeons at the Olympiad
26:18 Chapter 7: The best mathematical card trick ever
31:24​ Supporters

Here are some links for you to explore.

Enjoy!

Burkard

[irvingg]

Always appreciate when a Rubik’s cube example “accidentally” gets you some group theory ;)

[nanamacapagal]

Challenges:

1) We can guarantee at least 5 on one side. There are two ways to split the pigeons: 3-2 and 4-1. The max you can hit for both of them is 3 and 4 respectively. So we have at least 3 pigeons on one side. Add in the two pigeons on the equator and we have 5.

2) let the mystery value equal x. by multiplying by 10^some integer until the digits line up again, and then subtracting, we have 10^whatever*x - x = the non-repeating part you're left with. Factor out x on the left and that 10^whatever - 1 becomes a bumch of 9s. Then divide and we have the non-repeating remainder over a bunch of 9s. If ever the remainder isn't an integer just multiply both the numerator and denominator by 10 to knock out the decimal.
Example: 0.4318181818...
x = 0.4318181818...
100x = 43.18181818....
99x = 42.75 (all the 18s afterward cancel out)
x = 42.75/99
x = 4275/9900
x = 19/44 (simplify)

3) let's pretend we color the "didn't shake hands" white. We leave the "shook hands" black. So all we have to do is prove a triangle exists somewhere, and it doesn't matter what color. Note that each dot will always have at least three lines of the same color connecting to it, for the same reason the pigeons in challenge 1 can be split into a side with at least 3 and a side with less.
Look at a point, and follow three lines of the same color (I'll choose black) to three other points. Any line connecting two of these three points would either be black or white. If it were black, that would make a triangle with the two points and the starting point. If it weren't, then the three dots all have white lines between them, which makes another different triangle.

4) 315. And no, I didn't count manually. Here's how I found out:
The 7 edges UB, UR, RB, DB, DL, LB, and UL, all commute in one big cycle of length 7. The remaining 5 edges do the same. The 5 corners URF, ULF, DRF, DLF, and DRB go back in their positions but in the wrong orientation. So it takes 3 cycles to get back to their original orientation. The same thing happens with the other 3 corners in the back, only this time they take 9 cycles because they permute around each other too as well as reorient themselves.
All that's left is to compute the lcm of 7, 5, 3, and 9, which turns out to be 315.

5) 1, 2, 4, 8, 16, 32, and 64. Any collection just results in the binary representation of the number. Since every number can be written in binary in only one way, every single collection will add to a different number.

6) Queen of Hearts. The 9 of Hearts at the start signals the suit of the missing card is Hearts. The remaining three kings can be sorted as MBT (Diamond, Club, Spade), which is assigned 3. 3 spots after 9 is the Queen, and putting it all together we have Queen of Hearts.


Edit: I forgot one, challenge 5 at chapter 6

[jamaluddin]

Wow, I had ventured into speedcubing back in 10th grade and I conjectured to my friend that no matter what repetitive steps you use you'll get back to solved state and we discussed about it at great length. This video has brought those memories back and how I never thought about it afterwards even after doing a course on group theory but now you have opened my third eye. Thank you!

[behnamashjari]

Professor Polster,
The Mathologer is THE best thing that happens to me in all of the media including Internet, blogs, youtube, social media, podcasts, TV, radio, movies, lectures, courses, and print. I can not describe how much pleasure I derive from watching Mathologer. At times, it's like a detective solving a crime (the crime being the difficult math problem at hand). Thank YOU, MARTY ROSS and OTHER GOOD PEOPLE who make Mathologer, such a good unusual program, possible. May you continue to produce your programs for at least another 50 years.
Behnam Ashjari, PhD EE

[noahtaul]

I once performed a version of the trick at 26:18 where the AUDIENCE got to choose the card to keep, and the only choice the magicians had was the arrangements of the 4 cards. Of course that’s normally be impossible, so we cheated a little and used an extra bit, a right-hand vs left-hand choice. It goes pretty smoothly if you’re quick at mental math, and the audience never suspects a thing!

[gamestarz]

4:54 This actually isn't quite the origin of the name. From Wikipedia:

Dirichlet published his works in both French and German, using either the German Schubfach or the French tiroir. The strict original meaning of these terms corresponds to the English drawer, that is, an open-topped box that can be slid in and out of the cabinet that contains it. (Dirichlet wrote about distributing pearls among drawers.) These terms were morphed to the word pigeonhole in the sense of a small open space in a desk, cabinet, or wall for keeping letters or papers, metaphorically rooted in structures that house pigeons.

Because furniture with pigeonholes is commonly used for storing or sorting things into many categories (such as letters in a post office or room keys in a hotel), the translation pigeonhole may be a better rendering of Dirichlet's original drawer metaphor. That understanding of the term pigeonhole, referring to some furniture features, is fading—especially among those who do not speak English natively but as a lingua franca in the scientific world—in favour of the more pictorial interpretation, literally involving pigeons and holes. The suggestive (though not misleading) interpretation of "pigeonhole" as "dovecote" has lately found its way back to a German back-translation of the "pigeonhole principle" as the "Taubenschlagprinzip".

[aikumaDK]

The number of math-related shirts Burkard owns, is somewhere between 12 and Graham's Number.
Burkard, do you ever throw out old shirts?

[cHrtzbrg]

Very subtle post dubbing in the last chapter ;)

[m.rieger]

"Things are even much hairier in Australia than they appear at first sight." At first sight of this video - it looks really rather un-hairy, I agree... ;)

[gregwochlik]

You made me do the Rubik's cube experiment twice! The first attempt made me tear the cube apart and reassemble it in its solved configuration. I lost track of the algorithm and "got lost. After 30 spent "fixing" the cube, I tried again. I repeated your algorithm, with certain configurations teasingly close to the actual solution. Eventually, the cube did cycle back to the solved state!

[kenhnsy]

Like most everyone here, I ask, "Where the f were you when I was studying!!!?"
Your explanations combined with graphics are incredibly easy to follow.
I put you to the test to see if you had something on Euler's theorem and there were several videos.
Students will thank you for years to come. Keep up the great work.

[macronencer]

I love that card trick! The one drawback is that it needs an assistant, but aside from that, I think it definitely is the best mathematical card trick I've seen.

[kk-lrud]

😊 Gorgeous to see a new Mathologer video, , and thank you for introducing so much hearty content!

[aimersclasseslko]

The hidden card is the queen of hearts❤....This has became one of my favourite card tricks...I have probably watched this part of the video 3-4 times...I absolutely love this stuff❤....

[lennywintfeld]

The repeating decimal tail explanation was great! I never would have thought it was so. My head was spinning from it so much, I missed the next couple of pigeon puzzles descriptions. I'll be 73 in a couple of weeks so I must be forgiven for my astonishment :-).

[ohth]

About to teach pigeon-hole to a bunch of year elevens, just did groups. That Rubik's cube example is absolute magic thank you

[paulb]

To echo everyone else: amazing videos. Thanks so much for making them I think they will last down the ages, like the Feynman lectures books.

[cepatwaras]

6:11 He LIED! Three pigeons were hurt in the end of the video 😅

[probablyapproximatelyok]

For the Rubik’s cube order, I got 315 repetitions when I calculated the orders of all the edge and corner cycles (keeping track of piece orientations) and took the lcm. Recently I’ve been thinking about the connection between the pigeonhole principle and the Steinitz exchange lemma, since the pigeonhole principle could be seen as a consequence of the lemma with each of the pigeons and each of the boxes both being regarded as vectors over F_2, with the boxes forming a basis. While the latter perspective is overly complicated in this case, if you could find a different vector space that some problem could be interpreted in terms of, you might be able to use the exchange lemma in a similar way, but get better results than you would by using the pigeonhole principal directly. (The way in which the exchange lemma is used is that any collection of vectors with cardinality larger than the dimension of the space they are contained in must be linearly dependent)

[TranSylvainie]

I've been a follower since the beginning of the channel and my hype for newcoming videos is growing as the content keeps on improving. Congratulations and please do keep that amazing project running. We need math videos if we are due to stay home !