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.
A scanned copy of Récréation mathématique: Composée de plusieurs problèmes plaisants et ... by Jean Leurechon on Google books. For the hair puzzle check out page 130) tinyurl.com/3b6amaxk
The Pigeonhole Principle, Two Centuries Before Dirichlet by Albrecht Heeffer and Benoit Rittaud A very nice article about the origins of the pigeon principle and the hairy twins problem. Also features an English translation of the relevant page in Récréation mathématique tinyurl.com/hpkcuepx
The 4/5 pigeons in a hemisphere puzzle was problem A2 of the 63rd Putnam competition in 2002 prase.cz/kalva/putnam/psoln/p...
Why are repeated decimals fractions? Watch this video on why 9.999... =10 for a big hint • 9.999... really is equ... Or just skip straight to the answer en.wikipedia.org/wiki/Decimal...
If you don't own a Rubik's cube you can use this simulator to test what happens when you repeat some algorithms (move the faces using the keyboard) ruwix.com/online-puzzle-simul...
The website of the International Mathematical Olympiad. www.imo-official.org . The problem I am considering in this video is Problem 1 of the 1972 olympiad. You can download all the problems from here.
www.imo-official.org/problems...
Check out this very nice article about the Fitch Cheney five-card trick by Colm Mulcahy tinyurl.com/wttkfdwe
Today's music is English Country Garden (and as usual Morning Mandolin at the end) from the free KZbin music library. Today's t-shirt I got from here www.theshirtlist.com/pizzibon...
Enjoy!
Burkard

[@irvingg2342]

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

[@pierrecurie]

but are those subgroups normal?

[@Jack_Callcott_AU]

He doesn't need to use the PP if he knows some group theory. In a finite group every element has a finite order, execute the element that many times and we come back to the identity.

[@pierrecurie]

@@Jack_Callcott_AU That's... basically using the PP lol

[@nin10dorox]

@@pierrecurie If we chose our algorithm to be just a single turn, the subgroup will just have order 4. It won't take too long to check the cosets with a single rotation of an adjacent side, and you can verify that rotating the adjacent side first makes a different coset than rotating it after. So in general they aren't normal.

[@Jack_Callcott_AU]

@@pierrecurie I think you are right.

[@nanamacapagal8342]

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

[@Mathologer]

Very good :)

[@phjorland]

@@Mathologer Yes. He/she is now officially your assistent :)

[@RishabhSharma10225]

@@phjorland Just use 'they are' in such instances instead of He/she is :)

[@farrankhawaja9856]

@@RishabhSharma10225 Do people really do that? I've never actually seen that :)

[@adeeb1787]

Man you do your homework seriously.

[@behnamashjari3003]

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!

[@EebstertheGreat]

So one magician got to see the five cards and the one picked, then had to arrange the remaining four cards while the other magician was off stage (or back turned or whatever)? How did you communicate the suit of the fifth card with just one bit of information? Wouldn't it require two bits for four suits?

[@steffahn]

@@EebstertheGreat I guess it should work out: 4 cards are already out, 52 in total, so there's 48 to choose from. The order of the 4 cards gives 4*3*2*1=24 possibilities. Add the choice of hand and it's exactly 48 possibilities.

[@EebstertheGreat]

@@steffahn Yeah, that checks out.

[@kevinmartin7760]

I heard a variant on this that involved phoning the assistant's hotel room to tell them the 4 cards. The extra bit was transmitted by having the assistant have two connecting rooms and the extra bit was encoded in which room number was called. Of course, you can only do this trick once for each audience or they might notice that the room number called isn't always the same. If you can do the right-hand, left-hand trick you could also do a lot with finger and arm positions, facial expressions, how many steps the magician takes to hand off the cards, etc. at which point actually passing the cards themselves to the assistant is pretty much just misdirection.

[@tim40gabby25]

@@steffahn great post, thanks :)

[@gamestarz2001]

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

[@OmarLakkis]

Except in a British maths department, where you always find your snailmail in your pigeonhole.

[@KaiHenningsen]

@@OmarLakkis ... as long as snailmail is a significant part of one's life. That's fading.

[@ytseberle]

Thanks for pointing this out. I know it's just trivia, but I'm surprised this misinformation persists, and doubly surprised that the Mathologer (a German) would make this mistake!

[@m.rieger8856]

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

[@KaiHenningsen]

To go to a related question in biology: who has more hairs, a hairy chimp or a naked human? Turns out they both have approximately the same number, only many human hairs are extremely short and hard to see.

[@jamaluddin9158]

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!

[@raphner2759]

I tried to prove all rational numbers have repeating decimal expansions before this video and found the proof down in it

[@jamaluddin9158]

@@raphner2759 wow nice

[@TheChzoronzon]

Did it hurt?

[@zswu31416]

I always tried to prove that too! It's group theory, in a finite group any element has a finite order.

[@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?

[@TrimutiusToo]

I am pretty sure upper bound can be improved to googleplex

[@Mathologer]

Last time I counted it was around 300 :)

[@Alex_Deam]

@@Mathologer question is if you have 300 wardrobes or fewer for these shirts

[@brainlessbot3699]

@@Alex_Deam then one wardrobe must have atleast two shirts.

[@praharmitra]

@@Mathologer where can I buy these shirts?

[@cH3rtzb3rg]

Very subtle post dubbing in the last chapter ;)

[@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.

[@gregwochlik9233]

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!

[@kk-lr5ud]

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

[@BardaKWolfgangTheDrug]

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

[@flymypg]

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.

[@Jason4195]

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

[@lennywintfeld924]

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

[@ohth8047]

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

[@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.

[@theonetrueignus]

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.

[@Mathologer]

It definitely worth pointing out and not surprisingly it is pointed out in the video :)

[@l.w.paradis2108]

Sure. It's a lot like the birthday paradox in probability. We knew that.

[@notahotshot]

John Petters, 4:40

[@tulliusexmisc2191]

But we can observe from Stand-up Maths that Burkard does indeed have an Australian hair twin.

[@Piffsnow]

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

[@probablyapproximatelyok8146]

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)

[@Charles_Reid]

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.

[@paulb75]

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.

[@PapaFlammy69]

69 x 10k subs, nice :^D

[@alexpotts6520]

Or Jens' constant million

[@shanmukeshr1696]

O c'mon not that again 🤣🤣🤣

[@spaghettiking653]

Nice

[@Pedro-fh9ec]

(6+9+6×9)(6!×9+(6×9×6×9)+(6÷9%)(6+9−6)+√9+((69−(6+√9))÷6−9) = 690.000

[@paradoxicallyexcellent5138]

@@spaghettiking653 nice.

[@bloggermitavii]

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.

[@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 !

[@Mathologer]

Glad you enjoy the videos so much :)

[@avidreader100]

@@Mathologer I also enjoy the way you enjoy some of your own points, may be ahead of them. What is the name for the kind of short laugh you express?

[@aimersclasseslko9089]

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

[@mrpotatohed4]

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

[@kcmichaelm]

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

[@m.rieger8856]

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

[@ethanjensen7967]

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

[@euromicelli5970]

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.

[@rmdavidov]

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

[@cepatwaras]

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

[@Mathologer]

:)

[@cepatwaras]

@Bhavya Gadhwal 33:26

[@roylavecchia1436]

Actually 6 pigeons :)

[@HereWasDede]

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

[@rudrapratapsingh8904]

I am guessing the card which you are hiding is King of hearts. If I am not mistaken, the suit of the hidden card is the same as the first card and the distance is determined by the last three card by calculating the dictionary rank of them.

[@dickybannister5192]

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

[@chompyzilla]

There would be 45 games played at such a tournament. >70% draw means at least 32 or at most 13 games that change the score. Let’s assume the players all have different scores. One of the players might have a zero score, but the others must then be positive or negative. By PHP, we know at least five of them went the same way. Let’s say the five went positive. The lowest score they could have is 1+2+3+4+5=15. However, we only have at most 13 positive points to go around, assuming none of them cancelled with the negative points. This doesn’t work. A similar argument applies if the five went negative. This shows that the assumption they all had different scores was false, and thus there exists two of them with the same score.

[@Tehom1]

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.

[@onemadscientist7305]

Good thinking, but I must point out that as 4! is equal to 24 and not 48, your proposed solution doesn't work.

[@bourhinorc1421]

And for chapter 4 problem? Idk where to begin whith this problem

[@Tehom1]

@@bourhinorc1421 The Rubik's cube one? I didn't try it.

[@dragonspight]

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.

[@johnchessant3012]

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!

[@tgwnn]

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

[@evejoyce4352]

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.

[@JordonPatrickMears11211988]

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.

[@maxwellsequation4887]

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

[@garrysekelli6776]

Im a simple man. I see pizza arranged in a cornucopia. I eat the big slices first.

[@maxwellsequation4887]

@@garrysekelli6776 lol

[@TheKivifreak]

@@garrysekelli6776 brilliant

[@blue_blue-1]

Vielen Dank für das Video. Mathematische Entspannung.

[@TheBlackHeagle]

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 !

[@danbollows2871]

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!

[@JUk3Ak47]

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.

[@aleksakocijasevic6613]

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

[@sinpi314]

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

[@rayhanmansoor2951]

This day just got a lot better 🥰

[@pierfrancescopeperoni]

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

[@abhirishi6200]

Amazing explanation about Rubik's cubes!

[@williamrhopkins]

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.

[@lukechavhunduka2970]

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

[@Jodabomb24]

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

[@bryantames3716]

1, 2, 4, 8, 16, 32, 64

[@richardfredlund3802]

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.

[@toxicore1190]

PHP has exponential sized resolution proofs, but by extended resolution there is a super neat polynomial sized proof

[@eliyasne9695]

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.

[@NXTangl]

For a perfect 100% [Insert "it's an old meme, sir, but it checks out."]

[@Grrblt]

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.

[@redandblue1013]

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

[@PC_Simo]

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

[@trigonzobob]

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

[@gabor6259]

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.

[@shawon265]

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

[@mattgsm]

Mathologer just roasting introverts that go to parties

[@Mathologer]

:)

[@totheknee]

Except I'm an introvert who shakes everyone's hand that I know, and then I leave as soon as possible. That way everyone is happy I was there, and I'm happy to be outside. 🤣

[@falquicao8331]

My favorite proof technique❤️

[@IshanBanerjee]

That's so amazing , I love pigeon hole principle

[@ccuny1]

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

[@phasm42]

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

[@Mathologer]

I suspect so far neither you nor anybody else did not roll all the way to the end. Nobody appears to have noticed the Easter egg hiding there :)

[@phasm42]

I saw the throwback to 2.5 pigeons 😁

[@NessHX]

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.

[@paladindonut5254]

What a nice maths video!

[@Sam_on_YouTube]

Scam School did this card trick a couple of weeks ago. I highly recommend watching their presentation and explanation of it.

[@vishybloke]

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

[@MrSigmaSharp]

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 KZbin or not)

[@AdamAttia007]

@SigmaSharp, as a creator in KZbin studio, you can view how many returning Subscribers are coming to a video from notifications but not how many people are Subscribed to a channel with notifications.

[@KillianDefaoite]

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

[@KillianDefaoite]

My favorites were a tie between the handshakes and the olympiad problem. The handshake problem is a not so surprising, but still pleasant result. The olympiad problem is truly surprising, but the solution is very easy to follow for an olympiad level problem.

[@thomashughes4859]

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!

[@henryginn7490]

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

[@richardschreier3866]

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.

[@Mathologer]

or just 1,2,4,8,16,32, 64 :)

[@richardschreier3866]

@@Mathologer Thanks for the ❤️. It was my mistake in not remembering that the problem statement allowed single-digit numbers. BTW, I did a brute-force check and found that there are plenty of examples of 8 two-digit numbers

[@mapron1]

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

[@mhadzovic]

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

[@raphner2759]

Could you please do a video on minimal polynomials as you said you would in your 2019 Xmas video (the rational root theorem one)?

[@godknifetube]

I find this coding easier to remember for the distance between the cards: BMT 1, BTM 2, MTB 3; MBT 4, TBM 5, TMB 6 for the card trick.

[@Punklusky]

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

[@ericmckenny6748]

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

[@Mathologer]

That is correct :) Unlikely but if you got that special distribution of points on a sphere there is no way to place four of them within a hemisphere :)

[@hallfiry]

The repeating tail giving a fraction can be shown by expressing said tail as a geometric series, which then has a fractional limit. Adding that to the fractional head of the number gives a fraction. QED

[@mz1rek]

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

[@nicholasrhodes1729]

Fantastic video!

[@adityansingla5656]

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 KZbin!

[@drewduncan5774]

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

[@abj136]

I once executed the Rubik's cube sequence FRBL (turn front turn right turn back turn left) until it got back to the solved state. I believe it took 1200 turns. I didn't count to 1200. Instead, along the way, it alternately solved the corners and the edges over and over, and I believe 1200 is the LCM of the number of turns to solve edges and to solve corners. I think it was 60 for the corners. (my memory may be off and the numbers are slightly different.)

[@CraigNull]

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.

[@Mathologer]

When the word algorithm is used in conjunction with Rubik's cubes it has a specific meaning (=a sequence of twists of the faces which are uniquely determined by the color of their middle square). Using any other word gets you killed by members of the various cubing communities :)

[@CraigNull]

​@@Mathologer Thanks for the reply, was not aware of that Rubik community context!

[@OrlandoRiveraLetelier]

@@Mathologer I was looking for this. That part of the video got me thinking a lot because I did not know about the meaning of algorithm in that context. Thanks!!

[@IterativeTheoryRocks]

That little laugh is infectious. Lols. 😂

[@radchwistek7800]

Love it!

[@jackman5163]

My favourite topic is covered , thanks ...

[@thedoublehelix5661]

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.

[@abrvalg321]

5:51 it's usually generalized to "for mn+1 objects over n spots at least one spot would contain m+1 or more".

[@crazy4hitman755]

17:35 I found this and was super amazed that one algorithm required 216 turns to get back to the solved cube

[@sergniko]

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

[@01binaryboy]

That Card Trick Mind blowing....

[@IshanBanerjee]

16:55 Assume handshakes to be edges with red colour and no handshake to be blue coloured edges . Considering the scenario , there we get a complete graph with two edge colours . Now if we consider one vertex , A , one of the coloured edges must be at least 3 in number (Say red) . Now considering those 3 vertices attached with the initial vertex we chose (B , C ,D) . If BC or BD or CD is red then we get a triangle with all same coloured vertices (ABC , ABD , ACD) . And if all of them are connected by blue lines , then we get BCD as our required triangle with same edge colour . The process can be similarly continued for the other case .