What Is the Pigeonhole Principle?

The Pigeonhole Principle is a simple-sounding mathematical idea, but it has a lot of various applications across a wide range of problems. Learning to recognize pigeons and pigeonholes as they appear in different problems can help in discovering possible solutions.

0:00 Pigeonhole Principle
1:39 Chessboard Puzzle
4:07 Planet Puzzle
6:12 Compression
7:47 Pigeons and Pigeonholes

***

***

[loremipsumpj]

Thank you. My old math teacher tried to explain this to me, but they used hamsters instead of pigeons and I was completely confused.

[AlmogBokobza-jhun]

As a software engineering student, when I first came across this problem during my studies, it seemed so obvious and it was hard for me to grasp in which problems and observations this principle applies.
I feel like your video emphasizes the importance of this principle, and showcases how complex problems can be solved using this simple principle.
I loved it!

[SealMeall]

*Me procrastinating by watching more enjoyable math*

[yveslegrand]

This is one the best mathematical video I ever seen. It explains what math are and this is way more important than the specific pigeon stuff. Keep on you are doing a great job for the public education

[md.yasinarafathpiyal]

what we see is just a 8 minute video .BUT making it would take hours and hours. keep it up bro. Loved your explanation. I don't know how can someone even unlike this video

[hellohumans]

one pigeon had a good buddy willing to share his space

[lautaromelchiori]

Oh man what a fantastic explanation! Love this kind of content, keep it up!

[dragonshivers]

I had the concept of 'pigeon hole' all wrong XD
I always thought a 'pigeon hole' was a small opening just large enough to fit a pigeon, meaning you aren't giving yourself any wiggle room for change. "When you don't consider other options, you pigeon hole yourself", I was way off.
This was interesting, thanks for the info ^^

[brendanchamberlain]

I'm extremely surprised you don't have more subscribers, the quality of all these videos are really great! A bit of criticism: consider removing percussion instruments from the background music, or at least turning the background music down. At times, I found the beating of the drums (and to a lesser extent, the violin) to be distracting from your narration. Maybe something more subtle like piano, or simply turning the background music down a bit could help fix this.

[filippoarceci]

Came for the pigeons, stayed for the math.

[WendyLee]

Perfectly explained. I can understand and was amazed by those examples! Keep up the good work!!!! You deserve all the LIKES 👍🏼

[lettuce]

Idk about pigeon hole but as a tetris player. This is tapping into some tetris principles that not many people talk about.

The chessboard example touches on the parity principle in tetris where the t piece is the only piece that (if on a chessboard background) does not fill 2 black and 2 white tiles. Therefore making the board messy or harder to play until you place a second t piece.

[mateoz]

This is one of, if not the best channel to learn mathematical and computer science related concepts. I've been watching videos for an hour straight and was not once stuck or confused on some problems that are not that trivial. The quality of the videos is really good and you can tell that they are well thought out.

[PotatoForce]

I absolutely love the add humor and extra focus on graphical effects in your videos. Great content!

[nsgvector]

i seriously loved ur explanation, weve been taught to solve maths problems but the purpose of the principal was never taught to us thnx

[truegreen]

Let's apply Pigeonhole Principle to the American economy. All the pigeons are in one guy's bank account.

[anuragsuresh]

I knew that voice sounded familiar! Hi Brian from CS50.

[cmyip]

If there are 10 people going into the lift while only 9th floor buttons were pressed, then at least more than one person going out at the same floor! ( This is what I learn from my brother about this principle! Of course, it may have a chance that some people might forgot to press button. )

[bhupenhazarika]

For the first time ever heard about the pigeon hole principle and understood it in just 8 minutes! What an explanation!

[TheVenerableMrKrieg]

I think it's worth mentioning that the compression bit is maybe missing some key info. As stated, it makes it sound like _lossless compression_ is some kind of myth, but it is definitely a thing. The trick is that true lossless compression techniques cheat a bit by using look-up tables, and then breaking the data into "words" in that table. Put simply, if you have 256 bits of (256 zeroes or ones), but a table of, say, 15 "words" consisting of common 8 bit strings (even better if the compression can look at the data and find the most common strings!), you can effectively use 4 bits a lot of the time to losslessly represent 8 bits. Normally, 4 bits can give you up to 16 results, so 15 of those can call a position on the table and effectively say "put that string here" while the 16th result can be an escape to simply read the next bits verbatim in case they create strings outside the table.

The problem is two-fold, however. First, it's a bit of a cheat to say the table isn't part of the data, so generally speaking you'd either need it supplied separately or to be packaged in with the compressed data, and that alone chews up a chunk. For very large files this can be pretty economical (if you have millions of bits, you might be able to store strings of them as words that can reproduce the bulk of it in a fraction of the size, effectively turning each repeated section into a single instance with a little overhead), but as files get smaller this can break down as the included table can start heavily offsetting the saved space. Worse, the escape mechanism for strings of bits outside the dictionary of words can mirror other data, and so you may end up _adding_ data into some spots _just_ so you don't accidentally read actual data as decompression instructions and garble the output. There are workarounds to mitigate these issues as well, but the net result when taken altogether is the conclusion in the video-- while lossless compression _is_ a very real thing, there is no method that can _always_ produce a smaller result. Best case scenario, the algorithm being used can recognise those failure states and adjust to a different method that may still work, but at the end of the day it's still easy to prove. You obviously can't turn 1 bit into 0 bits and be able to go back again with certainty of what that bit was.