The Pigeon Hole Principle: 7 gorgeous proofs 

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

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

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

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!

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".

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!

"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... ;)

Very subtle post dubbing in the last chapter ;)

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

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!

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.

I am a simple man. I see mathologer upload Einstein, I click!

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

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.

This day just got a lot better 🥰

If you find the “infinite tail of zeroes” hard to swallow, it might help to realize that the only thing that controls whether a particular fraction has an infinite tail of zeroes or an infinite tail of something else is your choice of numeric base (which is not a fundamental property of numbers); for example 1/3 is 0.333... in decimal, but it’s 0.1 in ternary. If you’re still unwilling to accept tails of infinitely many zeroes as equivalent, then take this: 3/4 = 0.75 = 0.75000... but also exactly = 0.749999999... a sequence of infinitely many 9’s.

These videos are so interesting that I use them in my math essays' citations. Great job!

These are remarkable results. Thanks for putting these together to share with us!

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 :-).

31:00 Your card is Queen of Hearts. It’s clearly Hearts; and, since the order MBT stands for a distance of 3, your card is 9+3=12, which translates to Queen. 👸🏼❤

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

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 !

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)

This is awesome! :) I always love Mathologer videos. Do one on symmetric polynomials! :D And connections to the infinite product for sine!

It's worth pointing out that the question posed in the thumbnail ("Do you have a hair doppelganger?") is that question which is not actually answered by the Pigeonhole Principle: the proof only tells you that hair doppelgangers must exist, but not whether a specific person will have one.

Some new ones for me there. always nice to see. out of the many Combs books I have, I have to say that many of the PHP examples feel a bit contrived in that you have to have a go through a lot of hoops to spot the pigeons and holes. my favorite is "10 players in a complete Round Robin chess tournament. 1 point for a win, -1 for a loss, 0 for a draw. more than 70% of all games ended in a draw. Show that at least 2 players had the same total score." From Principles and Techniques in Combinatorics by KOH, KHEE-MENG; CHEN, CHUAN-CHONG

Mathologer just roasting introverts that go to parties

11:41 This genuinely made me happy I never thought about that before.

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

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.

26:09 I saw others commenting {1,2,4,8,16,32,64} but I have another solution and it was fun to find it. It's part of a sequence. We starts with 1. We add 2 because we already have 1, we can't add numbers that we already have and we add the smallest possible number. So 1 + 2 = 3. Our sequence is 1, 3 so far. We can't add 1 and 3 but we can't add 2 either because that's the difference between 3 and 1, so we can't add the difference between any two number in the sequence. We add 4. 3 + 4 = 7. We have 1, 3, 7. We can't add 1, 3, 2, 7, 4 (= 7 - 3) and 6 (= 7 - 1). The smallest number we can add is 5, 7 + 5 = 12. If we continue in this manner, we get 1, 3, 7, 12, 20, 30, 44, 59, 75, 96, and I just took the 7 largest numbers from these and it worked. I just checked OEIS, it has this sequence, it's the prime numbers of measurement sequence.

I really want to thank you Mathologer for your work. I'm a maths teacher and I run a science club in my school and I often take subjects from your videos. I really really like the long format. It's peaceful. :) And of course, the maths is always so interesting! I kwen about this principle and about the magic trick at the end thanks to the channel Up and atom. I really enjoyed the video anyway! Maybe my favourite proof is the olympiad one...

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❤....

I like the Pigeons at the Olympiad proof best. For the challenge at the end of chapter 3: Because every repeating decimal can be written in the form (x+y)/10^n + x/10^2n + x/10^3n ... for some integers x,n,y. We can factor out x, and we can rewrite: 1/10^n + 1/10^2n + 1/10^3n ... as 1/(10^n - 1) Noticing that when n is an integer, 10^n and (10^n)-1 are integers, we have the sum of two rationals, y/10^n + x/(10^n - 1) which is therefore rational, QED. For the challenge at the end of chapter 6: 7 integers from 1 to 100 such that no 2 different collections from that set have the same sum: {1,2,4,8,16,32,64} This is easily seen by putting the sum in binary form. Each bit in the sum is set by exactly one number from the collection, so if collection A sets a given bit, disjoint collection B lacks the only element that can set it. For the think-about-it pause at the beginning of chapter 7, I found a much harder and clunkier solution: There are 2*3*4 = 48 permutation of 4 cards. That's almost enough to pick out 1 card among 52 - if only somebody removed 4 cards from the deck. But somebody did! The mystery card can't be any of the 4 cards you passed to your assistant, which leaves 48. So we place some natural ordering on the 4 cards. Say, suit is the primary sort key and number/jack/queen/king is the secondary. We also number the permutations of 4 items - so we have a table that gives us a bijection from a permutation like C D A B to/from a unique index. And we number the remaining cards in the deck. Same idea: force an ordering, make a table. Then we look up that card in the deck table, look up that index in the permutations, and arrange the cards in that permutation. Our assistant does the reverse: Sees what permutation we handed him, looks up its index, constructs a deck table for the ordered deck minus the 4 cards he sees, looks up the permutation index in that, and announces that card as his answer. Ta daah, except that we need to build large tables on the fly. On the plus side, we can do it for any mystery card, we don't have to choose it ourselves from among 5 cards.

One of the more enjoyable videos ive seen on youtube in the past month. Definitely deserving of 700k subscribers

Haha I was reading books on recreational mathematics in my teen years (90s-00s), so nice to hear the concept is so old!

Amazing explanation about Rubik's cubes!

I first learned about the Pigeon Hole Principle while studying Computer Science. It is of fundamental importance in a variety of areas, ranging from databases to sensors. Recognizing situations where it applies always results in problem simplification, leading to savings in space and/or run-time.

Wow, I thought I was really good at math until I started watching your videos. It’s fun to watch you blitz through math that I barely understand.

thank you so much for this video. i haven’t really felt like i’ve truly learned something useful in a long time and this is so amazing and simple. you are classic. i am grateful

Due to the PHP, you'll always have a pair with the same suit. Put one of those two cards in the front, so you get the suit. The same does not work for the value of the card, though, so we need another plan... At this point, you have 3 cards of encoding to figure out which of the 12 remaining cards (same digit, not the card that encodes the suit). My first idea for encoding the digit of the card was to use the order of the cards. Since the first card is necessarily at the front, you only have three cards, or 3x2x1 permutations to work with, which isn't enough. My second idea was to use high-low order of the cards, which could use the first card for encoding. This gets to 2^3 or 8 different values, still not enough. In the second idea, though, an edge case popped out where the card indicating the suit is the highest or the lowest value, and can't be "higher or lower" than the next. That can be solved by giving different suits higher values (i.e. diamonds are "lower" than hearts, etc. However, the edge case does point out that we can choose which of the cards to take, which gives us another "digit" to encode with. For clarity, we'll call them the numbers 1 through 13. So how do we use those digits? If you always take the lower card, you get a worst case of 1, which still gives you 12 possibilities, which is not less than the 8 we need. What if we always take the card closer to 7, though? Well, 7 is the worst case, and give us 12 cards to dig through still. 6 would give you 1-5, 8-13, so 11 I gave up here and watched the video. Makes sense.

Dirichlet's approximation theorem states that any irrational number x is approximated well by infinitely many rational numbers p/q, in the sense that x differs from p/q by at most 1/q^2. This is proved by the pigeonhole principle!

We can also extend the result from chapter 6: it is possible to prove that for any 9 positive integers less than 100, there is are two disjoint non-empty sets of these numbers with the same sum. Also there is a set of 8 positive integers less than 100 such that any two different sets of these numbers have different sums. The proofs are pretty hard though, so I’ll leave that for someone else. Also, I’m not sure what souped-up version of the IMO was occurring with 10 problems, because usually they only have 6!

Hi Loger, happy anniversary.... I hope you will come to the soirees again.... Love the work you did do.... Keep it as that.... And again : good anniversary again !

At 25:55 you exclaim "full credit!" but I do not yet award you full credit. Removing the common elements leaves two non-overlapping sets, but you still need to show that both sets are non-empty. Which, yes, is very easy to do.

A mathologer video with less than 50 comments? That must be brand new. Must watch now!!!

8:13 Going with the previous method, we can have two on the equator, and of the remaining five at least three would reside in one of the hemesphere, totaling 5 out of 7.

I had been trying to solve the card puzzle for quite some time. I had figured out the part of communicating the suit but I had not worked out how to communicate the number. Finally, I found it here.

For the card trick I dis-carded (no pun intended) the color/suit of the cards and just imagined the cards as numbers 1 to 52 in a circle with "52" right next to "1". That you can encode 24 possibilities with 4 cards is quite straight forward with (4*3*2*1) but it took me quite a while to figure out how to reduce the 48 remaining cards to 24 possibilities. The answer had to lie inside of the chosen card. Not every card of the 5 can be chosen. Since I imagined the cards in a circle you can be sure that if you choose the "right" 4 cards that the fifth is at most at a distance of +-12 cards from the edge of chosen cards if you connect the 4 chosen cards as points on the circle with a minimum distance (For example "52","1" get a connection of 1 distance and not 51. Same principle for 4 cards). If that were not the case you would have to have 5 cards where every card is at least 13 cards away from the edge. 5*13 is 65 and bigger than the amount of cards (52). Of course in principle its the same trick. The suits of the cards don't give any more information than reducing the card to a number so the trick has to be possible without looking at the suit but I have to confess its way more intuitive the way Matholger explained it.

17:35 I had that hypothesis as well, but never got around to proving it. It was just something I felt when I was playing around with a Rubik's Cube

Vielen Dank für das Video. Mathematische Entspannung.

31:00 I guess the Queen of Hearts is the missing card.

This is the only channel which gets an instant watch as soon as the notification goes off.

For some reason, I'm gonna remember this video as the Pigeon Pizza Pi Hole Principle.

A mathologer video with a full section about cubes! Am I dreaming? :O

mathologer pleeeese ur the best math youtuber please make an video on diophantine equation

Given that there are 7! = 5040 possible orderings of the 7 proofs and a subscriber count in the hundreds of thousands, I can say with certainty that multiple viewers of this video will have the same ordering of most liked to least liked :)

That's so amazing , I love pigeon hole principle

What a nice maths video!

My favorite proof technique❤️

I came up with a slightly different method for the cards: With the two cards of the same suit, if the sum (counting face cards as 11, 12, 13) is even, pick the lower, if the sum is odd, pick the higher. The other card in the sum goes in the first position. So, for your assistant, if the first card is odd, they know then the sum was either even and the picked card is lower and odd, or the sum was odd and the picked card is higher and even. (likewise, if the first card is even, then the picked card is either lower and even, or higher and odd.) Regardless this gives your assistant 6 possible options, and then the permutation of the three other cards picks one of those.

Love the video and your T-Shirt. Thank you.

Fractions are equivalent to repeating decimals… HOW DID I NOT KNOW THIS And knowing how long the repetition might be from the denominator is extremely cool

I'm a bit late to the party, but excited as always for a Mathologer video!!

Fantastic video!

Can’t wait for yet another amazing video! It’s waiting for me when I’m done with work for today :)

Beautiful video! I liked the IMO proof the most. It was amazing! P.S. Mathologer, why are some of your videos link only? Like the hidden cube in Simpsons one. Also, Are you still working on the gallois theory video? I am waiting for that amazing video :) And also, I want to learn problem solving like that in IMO. Can you suggest some nice books for the same? Thanks for making such wonderful content on RU-vid!

Queen of hearts was pretty easy :-D I haven’t taken the time for the other challenges yet. Amazing video (as always I must say…).

Now that I have watched this video it's been up for 50 minutes and 94 likes so at least two people liked it in the same minute. This is not interesting up to here, but this number will initially increase for a bit and then decrease later. And the peak is dependent on the number of notification bells and subscribers. So with this simple thing we can find out about the number of notification bells set on any channel. (Disclaimer, I don't know if you can actually see this number anywhere on RU-vid or not)

Content is amazing as usual, but I have to compliment you for something else. You got really good at recording this, hiding cuts by chapter transitions instead of if the middle of a sentence makes this much more enjoyable compared to few years back.

13:16 I am dead, you have great sense of humour!

That Card Trick Mind blowing....

That IS the best math card trick I've ever seen

What's great about the rubies cube algorithm trick is you can add in rotations or flips of the cube itself as part of the algorithm and it still works... was doing it as a parry trick in high school.

Burkard, thanks for sharing the ubiquity of this highly intuitive principle. There may be an application to distributional evenness of modular sequences. James Grime has a card trick on Numberphile implicitly relying on the pigeonhole principle (cf video "James

wait a minute is 20:22 is a really nice proof for everyone's favourite linear algebra 1 theorem "for any element a of a finite group (G,e,*) there is an m

Professeur ! I don't know if you remember, but it would be neat if you did something fun on Metronome-styled pendulums. Just a thought for ideas on moment of intertia and torque in maths. ¡Saludos desde México!

Paul Erdos talks about this Ramsey theory question with 6 people at a party and you have a triangle. After hearing about it I liked the question so did some playing around with 5 people party. There you either have a triangle or a pentagon.

My favourite topic is covered , thanks ...

Listening to Morning Mandolin is a reason to leave the video rolling to the end 😁

21:09 That's a good visualization of the orbits and stabilisers theorem.

I am late to the party but I loved the Rubik's Cube argument that there could be no loops due to reversibility. The thinking about precursors reminded me of the Schroeder-Bernstein Theorem. Perhaps there is some material there for a future video. In a younger day I discussed filing systems with my father who would point out the futility of having more pigeon holes than items to file. To answer the card question MBT is 3 according to my reckoning so Q of H.

Amazing video. I loved it!

Here's a question I found interesting from my complex analysis course that uses the pigeonhole principle for an uncountable set not having an injection into a countable set. f:C-->C is an entire function and for each z_0 in C, the power series expansion sum from n=0 to infinity of c_N * (z-z_0)^n has at least one c_n = 0. Prove that f is a polynomial Another interesting application: for m>n, if you drill m holes into n pigeons, one pigeon will have at least 2 holes in it

Love it!

In the section on returning to the solved state on a Rubik's cube we have to be careful about what we mean by an algorithm. Some rule that dictated different rotations depending on the color of a specific square, for instance, could create a non-injective (and thus non-reversible) mapping on the set of states, which can cause you to get stuck in a loop not containing your initial state.

The Fitch-Cheney five-card trick is wonderful. I had heard this trick described but had no idea how to make it work. Thanks for filling yet another hole in my understanding of the universe! I can't wait to share this trick with my friends! As for 7 2-digit numbers for which no two subsets have the same sum, how about 64+(0,1,2,4,8,16,32), i.e. (64,65,66,68,72,80,96)? If the common sum were S, then the 6 LSBs of the binary version of S dictate which of the last 6 elements are needed to yield S. Non-overlapping subsets with a common sum therefore cannot use any of these 6 elements, leaving only the first element. Since you can't form two non-empty non-overlapping subsets with only 1 element, no two non-empty non-overlapping subsets have the same sum.

Love your videos!!!!!!!!!

10:30 - finally, part of a mathologer video I can understand!

Thank you!

Card trick and Rubik's cube algorithm are the best!

Practice hand hidden card is Queen of Hearts; let me get my heart :)

It's been 2 months. Feels like a new video is on the horizon :3

Very enjoyable. Thanks m8.

That little laugh is infectious. Lols. 😂

4:20 "The Argument is really weird [...] Although we can be absolutely certain that Australia has hair-doppelgängers, the argument gives us absolutely no clue about how to find such hairy twins." I actually think you are doing your proof injustice here ;) The argument you gave, by itself, gives a perfectly fine algorithmic description of how one would go about finding hair-doppelgängers. More abstractly it's an easily implemented algorithm for finding a pair of elements which both have the same value for a (decidable) property and the side condition "there are more elements then values for the property" guarantees termination of that algorithm. So we actually know exactly how to find those twins! The weirdness then rather comes down to the infeasibility of actually doing this in real life. I would compare this to some situations in complexity theory, where there are problems which are known to have solutions; Solutions however that are well beyond practical.

Infinite repeating series: Example 0._14_ It is equal to sum(0.14*0.01^(n)) The series is 0.14* 1/(1-0.01) = 14/99 In general, 0._abcdef_ = abcdef/999999 (as many nines as repeating digits)

Dr. Polster, I worked out y=x^x (x to the power of x) and found for x=0, y approaches 1. Also for x=1, y will be 1. For x=1/e=~0.3678, y will have its minimum which will be 0.6922. beyond x=1, y increases continuously until +infinity. Here's my problem and I need your help, perhaps a Mathologer: for x= -infinity, y=0. For all even negative integers, y>0. For all odd negative integers, y

2:52 Proper pronunciation of "forte". Very nice.

Every repeating decimal is a fraction because repeating decimals are basically just geometric series. Geometric series have a nice 1/1-x formula which will output a rational number if what was put in is a rational number.