What Is the Pigeonhole Principle?
Vložit
- čas přidán 31. 05. 2024
- 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
***
Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
***
Earth texture courtesy of www.solarsystemscope.com/text...
Thank you. My old math teacher tried to explain this to me, but they used hamsters instead of pigeons and I was completely confused.
Pigeons better
What were the hamsters even _doing_ in the dovecote in the first place? Must have scared away the pigeons from their holes.
Hamster hole principle
@@chessmaster2041 that’s a different game altogether. Just ask the ER staff. 😂
But hamsters are a bit smaller and tend to group together, wouldn't you end up with 5 hamsters in one hole and zero in the others? Or at least 3 in one hole, 2 in another the rest empty?
Hamster hole principle is a completely different thing.
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!
great video with no doubt, but in my opinion the pigeon principle has not much to do with the first two problems. In the first problem the crucial part is noticing that every domino covers two differently colored squares, not applying the pigeon principle. The same is for the second problem. The third one tho is strictly linked with the principle
Honestly, given how simple it is, it seems to usually be taken as implicit, hence the difficulty in trying to come up with uses.
i still don’t get it 🥺
@@ily____ you don’t get the idea of the principle?
@@AlmogBokobza-jh8un at first i did, but then it got complicated and then i got confused which made me afraid so i had to grab a blanket to cover myself then i got hungry so i ate an ice cream sandwich then i completely forgot the concept in general which made me doubt myself and then i was thinking what color i want to paint my toes tomorrow which made me feel better, but then you just responded and reminded me of the whole thing and now i’m having ptsd… 🫠
in short no, i do not understand the idea of the principle 😐
one pigeon had a good buddy willing to share his space
Came for the pigeons, stayed for the math.
came for the pigeons, stayed for the holes
"Came" for the pigeons you say???
🤨📸
@@kevinfernandez9999 yes, and stayed for your mum's onlyfans
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
Well now they can't
Probably because it was mediocre no offense. (To those who do not know, this is a meme, I actually really enjoyed the video)
@@p0358 they can. You just don't see it. But wait until the button itself disappears
@@shufflecat3334 was it? I would like to see you try to make a similar video
@@thenamelessking375
Oh man what a fantastic explanation! Love this kind of content, keep it up!
Thanks!
Ver very Gud
I like your explanation idea Nice man
U did it❤️
@@SpanningTree It is debatable if the 2 points on the arbitrary equator line belong to any of the 2 hemispheres.
@@KRYPTOS_K5 It is not. They belong to both closed hemispheres, by definition. He explained the definition of a closed hemisphere in the video.
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
You should check out VSauce if you haven't yet.
The BEST ever? And what are math?
this is not what pigeon holing means or where it comes from. To pigeon hole some one is to 'typecast' them, and it come from the message tubes that replaced carrier pigeons not pigeon sleeping holes.
@@erikred8217 How does a message tube relate to typecasting? It seems more like if you are in a pigeon hole, you must be a pigeon.
@@BariumCobaltNitrog3n narf i don't care. just making a simple history correction. the term originates from message tubes, not nesting or roosting holes. cry about it.
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.
" Best case scenario, the algorithm being used can recognise those failure states and adjust to a different method that may still work"
not it will not
becouse if you have
F(X)->Y and want lossless compression
you can't have x1=/=x2 : f(x1)=f(x2)
and no metter what
and you just make some function G and H and said
F(X)=G(X) for x in X_1
F(X)=H(X) for x in X_2
but still the function must be bijective
F(X)->Y
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.
I absolutely love the add humor and extra focus on graphical effects in your videos. Great content!
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 ^^
You're right too outside of a mathematics context. As an English idiom, if you pigeon hole somebody, you're metaphorically putting them in a box with no other options. It's like an actor being typecast as a baddie - they're being pigeon-holed in that role.
the difference would be that the prevailing usage is pretty much never thought of as reflexive concept; things are routinely pigeonholed by people, but people are only pigeonholed by asshole CEOs, the govt, fate, etc.
you wouldn't pigeonhole yourself because you aren't a pigeon, but even when you get treated like one anyways by an outside force, the understanding is that pigeonholing is something strictly out of your control. kind of why it's called a "principle" and not a theorem or similar
A pigeon hole is just where you keep a pigeon.
@@SplendidKunoichi most people pigeonhole themselves by believing their are less capable than they really are
@@SplendidKunoichi It is a mathematical theorem, though, but not all mathematical theorems are called by the name "theorem."
*Me procrastinating by watching more enjoyable math*
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.
Thanks for the feedback!
@@SpanningTree Just want to endorse Brendan's criticism. Too many excellent presentations (not just yours) are spoiled by 'enhancement' of this kind. Just because you can do a thing, doesn't mean you must do that thing.
Yes I agree, the background music was rather distracting
I think subs have improved, but I also think data structures is a bit of a quaint field. Although it's more important than ever.
@@peNdantry Presidential comment.
I knew that voice sounded familiar! Hi Brian from CS50.
How did you find out?
@@addy1154 Look at the about page on his channel.
Anurag suresh see the description
Theres his name
Tbh, the pigeonhole principle is usually just a last, obvious step. Especially in the first two puzzles, the real heavy lifters were observations that were unrelated to the pigeonhole principle. For the chess board, it was that a dominoe always covers a single light and dark square. For the hemisphere, it was first imagining a hemisphere intersecting 2 of them, and realizing you can choose which side for it to go on. After these steps, the solution is fairly obvious without need of thinking about the pigeonhole principle. Our brains make those simply inferences unconsciously.
Correct
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. )
Ten people start on the first floor and enter the lift, that means there are only eight floors left and ten people
@@petensue2708 The definition of "first floor" varies (e.g. with language; as you can see CM isn't a native English speaker).
@@petensue2708 You're assuming that the building has only 9 floors. It can have 30 and only 9 of those were pressed, you'll be left with the scenario that the original comment suggested.
@@hermesthegreek5247 my thought exactly, that's how I interpreted it
Perfectly explained. I can understand and was amazed by those examples! Keep up the good work!!!! You deserve all the LIKES 👍🏼
this is not what pigeon holing means or where it comes from. To pigeon hole some one is to 'typecast' them, and it come from the message tubes that replaced carrier pigeons not pigeon sleeping holes.
i seriously loved ur explanation , weve been taught to solve maths problems but the purpose of the principal was never taught to us thnx
I was going to argue about lossless compression producing a smaller output, but then I listened again. "Always produces" is what you said, and always is the key principle. Then I realized you are correct. There are many lossless compression algorithms that result in a smaller output than the input - otherwise they wouldn't be useful for compression. All of those algorithms suffer from edge cases though. These edge cases result in a larger output than the input, so therefore, those algorithms do not always produce a smaller output than input as per your statement. Lossy always produces a smaller output, but it's lossy.
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.
this is not what pigeon holing means or where it comes from. To pigeon hole some one is to 'typecast' them, and it come from the message tubes that replaced carrier pigeons not pigeon sleeping holes.
For the first time ever heard about the pigeon hole principle and understood it in just 8 minutes! What an explanation!
this is not what pigeon holing means or where it comes from. To pigeon hole some one is to 'typecast' them, and it come from the message tubes that replaced carrier pigeons not pigeon sleeping holes.
I understand the concept that there’s always going to be one more in another piece but what’s the point of knowing this??
This concept is analogous to surjective functions in Math where the pigeons make up a restricted domain set and the pigeonholes make up the range /co-domain set. It's crazy how everything is so connected. 🤯
I mean, everything is just math
It has nothing to do with surjective functions, there is no restriction that every hole has to be filled. The principle actually says that a function from a finite domain to a finite codomain where the size of the domain is larger than the size of the codomain cannot be an injective function.
@@theodoregossett9230 It does have to do with surjective functions, though, since the "size" of a set (technically, its cardinality or numerousity) is _defined_ in terms of bijective functions. Two sets X, Y are equinumerous if and only if a bijection f : X -> Y exists. This is how equinumerousity is defined. Equinumerousity is an equivalence relation, and it partitions the universe of sets into equivalence classes, called cardinality classes. The cardinality class of a set X can be denoted |X|, and with the axiom of choice, these cardinality classes can be totally ordered. Now, we can say that for two sets X, Y, |X| =< |Y| if and only if there exists an injective function g : X -> Y. If X and Y are finite sets, then in order for them actually be finite, it must be the case that there exist functions p0 : X -> N, p1 : Y -> N which are injective, where N is the set of natural numbers, since this is how the finitude of a set is defined. To be able to say that |X| < |Y| is to be able to say that that some injective function g : X -> Y exists, but that no surjective function h : X -> Y exists. Your "formulation" of the pigeonhole principle, that if |X| < |Y| < |N|, then there is no injective function g : X -> Y, is a tautology, since the consequence is precisely the definition of the condition, and thus, this is not actually a formulation of the pigeonhole principle.
Technically, the pigeonhole principle actually is the following statement: if |X| < |N|, and |Y| < |N|, and there exists a surjection h : X -> Y which is not injective, then |X| < |Y|. In essence, this is just saying that surjectivity and injectivity are dual, in the sense of category theory, at least when it comes to finite sets.
Another formulation is to say that if |X| < |Y|, and Y is a subset of the power set of X, then there exists some S in Y such that |S| > 1. This one is the more straightforward formulation from the English wording.
Like an octopus wiggling it’s multiple arms but the right one is cut off and by this you can tell the direction lol
The compression example was beautiful, really made me understand how this can be useful
I’m sure I’ll put this to use at some point in my life. It’s almost so obvious at first introduction its easy to not recognize that the approach is quite powerful. Thanks for a great introduction with excellent graphics.
I literally wrestled with this concept while training my pet pigeons to accept my younger rescue pigeon into their coop and allow him to occupy one of their boxed perches while placing two "friendlies" together on a larger one. It took them two days to accept the new sleeping arrangement until my rescue was safely returned to the wild. He would visit me everyday after that at 3pm with his girlfriend for a treat!
this is not what pigeon holing means or where it comes from. To pigeon hole some one is to 'typecast' them, and it come from the message tubes that replaced carrier pigeons not pigeon sleeping holes.
@erik red Do you know what 'literally' means? Note the cute graphics with the birds in nesting boxes that the video features - that was literally my situation with my birds. Hence my comment.
(Also, try to loosen up just a tad. I promise you that you won't regret it. Literally:)
But, I also want to add that your additional information on the more precise context of 'pigeon holes' is fascinating in itself! Thank you!
I wish this video existed when I was still learning discrete math back in university. It would have been so useful!
is your mind pigeon holed?
Very well explained! I'm not that advanced yet how you explained it helped me understand the principle! The globe examining was the most useful in understanding it. Thank you again!
Really great explanation, thanks. I'm a programmer, but never thought of this concept directly.
Insane Explaination and Insane graphics you deserves a million subcribers dude ..
Keep growing
Yeah in computer science you run across this all the time. And remembering it lets you solve some complex problems almost instantly.
I must be an idiot cause I dont see the groundbreaking application.
@@cryp0g00n4 Lol...Perfectly said.
More of this please!!! The applications were beautifully explained I watched it once, twice, ... and lost the count :)
The animations are very nice and the buildup in the way it teaches things is also very well thought out.
I never heard of this principle, but it is interesting to hear. Thank you 😊
this is not what pigeon holing means or where it comes from. To pigeon hole some one is to 'typecast' them, and it come from the message tubes that replaced carrier pigeons not pigeon sleeping holes.
I like your animation very much. I think it's easy if we learn programming lessons with this animation method. I mean leaner's have a better idea of what's happening to each bit.
I use this a lot this logic when playing minesweeper. I remember reaching this way of thought when stuck at a game and it completely changed the way of playing... I did not know it had this name. Great video thanks!
This is the type of content I just love. Stimulates my brain so good
the point of lossless compression is not that you can ALWAYS get a smaller output from ANY given input, because for this you would have to create a special input that passes by all compression mechanics. In practical uses this does not happen, if you use normal content the compression was made for. The advantage of lossless compression is, that you can reconstruct the original 100% but have a smaller filesize.
How do you decompress it, then? In the video he said that the output wasn't able to reconstruct the input. Then how does it work?
@@NotASpyReally I think the point was that if you have a Lossless compression algorithm, it will produce compressed output files that are bigger than the input file at least some of the time (for certain specific files). Otherwise you go against the Pigeonhole Principle.
Like if you have a compression algorithm for input files that have a thousand 10-letter "words" each, it could work by making the output file be a table which merely records in which places (so also how many times) each 10-letter word appears in the input file. So this is a Lossless algorithm, because you can reconstruct the original file perfectly.
But for some input files, the compressed file will be larger. For example, for all the input files that contain a thousand different 10-letter words (no duplicates), the output will just be all the "words" again, plus the "locations" of each word, which is extra data space in the file.
So this is a Lossless compression algorithm that doesn't break the Pigeonhole Principle.
@@Albtraum_TDDC Ooh so sometimes you can compress files and sometimes you can't, right?
Excellent visualization! Way back when i was still a student, the only way for many of us to learn this is ( and other discrete math topics ) is through textbooks. And they were hard
Our schoolbooks were badly written on purpose.
Thank you! I think this is what I'm missing when I was playing some puzzles when I was younger. Since it was a computer game, I just try multiple answers until, by chance, I solve the puzzle.
This channel is massively underrated. Giving this to me was the single best thing that CZcams algorithms had ever done.
way better explanation than my college professor. Thanks so much
I think the point was that if you have a Lossless compression algorithm, it will produce compressed output files that are bigger than the input file at least some of the time (for certain specific files). Otherwise you go against the Pigeonhole Principle.
Like if you have a compression algorithm for input files that have a thousand 10-letter "words" each, it could work by making the output file be a table which merely records in which places (so also how many times) each 10-letter word appears in the input file. So this is a Lossless algorithm, because you can reconstruct the original file perfectly.
But for some input files, the compressed file will be larger. For example, for all the input files that contain a thousand different 10-letter words (no duplicates), the output will just be all the "words" again, plus the "locations" of each word, which is extra data space in the file.
So this is a Lossless compression algorithm that doesn't break the Pigeonhole Principle.
In fact, lossless compression also use statistics for coding rare numbers with longer outputs and frequent numbers as shorter output. Hence files with high entropy has compression efficiency near zero, and compressed files has ultimate high entropy (in perfect model).
Exactly, so the example made in compression is not very helpful. In such case we frequently have a larger compressed picture file for a very busy picture. Compression is for us to remove inefficiencies, which is orthogonal to the pigeon theory.
That is a brilliant explanation! Thank you very much. Please keep making the videos
Please make more such videos they are so easy to understand with your explanation.
Good explanation. I want to pointout one thing which I feels like it's incorrect, which is your 3rd example about lossless compression. Because in lossless compression bits are encoded in such a way that it can be always decoded to actual input hence there's no loss of information and so, maybe we can say that one bit is representing multiple input bits according to pigeonhole but we can always retrieve those bits. So, pigenhole reveals the limit of lossless compression from which we cannot further compress data without loss. Can you explain it in case my understanding is wrong about this?
The explanation in the video was perhaps a bit... compressed. Since I'm not sure if I understand your question, I'll try to explain it in another way.
Given n bits of data, there are 2^n possible combinations of 0 and 1. To losslessly compress the data, an algorithm would need to map each combination onto a unique string of bits of length that's shorter than the original. The video showed that this is impossible if the algorithm always compresses to a fixed length m (since 2^m < 2^n if m < n). However, I think it's worth pointing out that this is true even if the algorithm is more sophisticated and compresses to a variety of lengths m, where m depends on the original data. The powers of 2 have this interesting property that the sum 2^(n-i) for i from 1 to n = 2^n - 1. Therefore, even if the algorithm uses all the unique strings with lengths up to n-1, there is one combination it cannot fit.
@@bladdnun3016 Ok, now I got the point. in video they were talking about possible input data and possible number of outputs where we can't map every single input to unique output because domain of function is greater then the sample space or range. And for same output it will create ambiguity that how can you retrieve two different data from single output.
@@bladdnun3016 you are right but picking this example gives the impression that lossless compression is impossible
@@sudqi True. Obviously not what I wanted to say. Compression typically takes advantage of repeating patterns and other constraints within the data. What I stated above and what's said in the video applies in the general case, where no assumptions about the data can be made. In real life, this is rarely the case.
@@bladdnun3016 Anyway, great effort. Thanks for the video.
Thank you for explaining the pigeon hole principle. I am a programmer and I really need to learn this.
Shut up madrasi
WOW! Thank you!!!! This video made the concept really easy to understand.
I remember watching this when i was at 12th grade, now I am studying Pure Maths in University and my number theory teacher used this principle to solve a fun logic problem and I understood it better
Awesome explanation brother, Love the pigeons. You just got a subscriber.
The Pigeonhole Principle: If there are n+1 holes in n pigeons, then there must be at least one pigeon with at least 2 holes in it
This is very helpful thank you. I'm thinking this is probably helpful when tackling numerical problems but checking if you will actually find a solution. It doesn't provide you a solution but tells you, you should be able to find a solution given enough time and compute power
I had to come back and comment. @spanningTree uploaded only 21 videos but has 105K subscribers. It is very telling about the content. I had to watch them all.
fantastic content! instantly subbed! keep the good work up
For curiosity i clicked
For simplicity i rolled my eyes
But surprised by learning
I subscribe
lol. I did the same. Thought the same. Said the same. (an dnow i hear him saying in my head, "thats the beauty of pigeonhole priciple".) XD
this is not what pigeon holing means or where it comes from. To pigeon hole some one is to 'typecast' them, and it come from the message tubes that replaced carrier pigeons not pigeon sleeping holes.
@@erikred8217 nobody said pigeon holing. Read the video title?
@@Greenhawk96 Pigeon holing, and pigeonhole mean the same thing. like golfing. and golf. It's called a present participle.
@@Greenhawk96 also Vernacular is another word you seem to lack. maybe context is a good starter for ya.
Oh, I use that so often in my head to solve some problems. I didn't realize some of its other cool applications.
The whole concept is explained very simply in such an interactive manner! Thanks for this content
Id say this is the opposite of simple. He repeats things so many times. This video could and should be 2 minutes max.
This is a lot of effort! Thanks for this wonderful video!
another rising star of youtube
The second example of the planet earth came on Putnam B6 once. The question was not exactly this but simplifies to this case only. Thank you sir lots of love from 🇦🇫😇👍
Learned this for proofing in my math degree. Good Explanation.
Next level animation! Awesome explanation!
thanks brian you are doing a great job
Thank you!
I don't know why, but I was mesmerized by this video.
Thanks a lot. Very nicely explained. Graphics and animation are excellent.
Great explanation!
I really appreciated the lossless compression example, that was smart.
I usually just shop the pigeons up into the right size pieces to fit them equally in all the pigeon holes.. so there goes that theory
I laughed at the thought of 4 horrified pigeons each sharing a box with a bloody quarter-pigeon.
It feels bad that even working in IT industry, wasn't aware of this theory. Thanks to u, that such complex topic I learned so smoothly...
Excellent animations; very helpful, thank you!
Lossless compression: This should be clarified a bit more. In any numbering system (data) there are always rules that must be followed. One rule might be to omit all leading zero's along with a predefined maximum # of digits. This rule will allow for lossless compression. eg. 10 instead of 00000010.
If those leading zeroes are meaningful that's lossy though. You can't tell if your 10 represents a compressed 10, 010, 0010 or any other such string. If those zeroes aren't meaningful... neither is this rule? This is literally an identity operation.
ASCII code that represents the letter A is written on the harddrive as "0100 0001". (actually there is a 2-7 RLL encoding at the physical disk leve, but for argument sake lets say its not) It progresses incrementally where "0101 1010" is Z. As you can see, the first two bits doesnt change and can be eliminated without loss of data. Of course, if the ASCII table was expanded to include lower case and numbers, then this wouldn't work. (ASCII for "0" is "0011 0000")
@@NA-hi7lx Your ASCII example works because you are always emitting the same thing, so it is a valid way to compress data by 25%.
However, the example in your initial comment of dropping leading zeros doesn't work because its extremely ambiguous. If I said to you that I had compressed something into 10011010 by dropping leading zeros, what does it decompress to? You wouldn't even know how many numbers it was, and even if I told you it is 3 numbers, you still couldn't do it.
It could be:
100, 1, 1010
1001, 10, 10
100, 110, 10
And of course if you didn't know it was 3 numbers it could be anything:
10011010
100, 1, 10, 10
100110, 10
1001, 1010
All of these are valid ways of reading numbers from that byte by introducing leading zeros. Maybe I am misunderstanding you but your example of 00000010 being compressed to 10 makes me think this is what you meant. Compressing 00000010 to 10 with no leading zeros means you can literally only encode 1 and 2 unambiguously. In fact, you can never compress a digit with 1s next to each other because as soon as you do that you can split the 1s apart without creating any leading zeros.
If you say that there must be at least 4 binary digits, you still get problems with larger numbers. 10010001 can be decoded in 2 ways. It could be the entire number 10010001, or it could be 2 numbers: 00001001, 00000001. Once again, it's ambiguous.
Deserves way more views wowww
Thank you man your 8 mins video is equivalent to my 2nd semester classes
Wow! That was such a nice explanation. I’m stunned.
I use the Pigeon Hole principle to solve the most difficult Suduko puzzles... where you have 4 cells, but 5 numbers. The goal is to determine which 4 of the 5 numbers MUST be in the 4 cells - even if I dont know which number goes in which cell. The conclusion being, the 5th number must go elsewhere...
You say pigeonhole, I say "cloaca"
this video blows my mind. how can such a simple principle lead to so many proofs?
a top video explaining how theorems can be applied!
I just like pigeons and holes.
Imma send this to my maths and science teachers and tell em to teach this in class instead xD
This is a very good explanation of the concept. Thanks.
Liked this video, been a while since I’ve heard about ye olde pigeon hole principle. Never heard the 5 point hemisphere problem so that was a fun one to pause and solve before resuming 😊
I didn't fully get the last one. But the geographical example was fascinating!
Imagine someone tells you that they can compress any text so it always becomes shorter, but can also always restore it to its original afterwards.
That is impossible and can be proven with this principle.
If you want to hide 10 letters in 9 letters then at least two possible input letters must become the same one in the result.
If two letters map to the same output, when trying to reverse an output back to the original, then you cannot tell what the original was.
Maybe both I and O turn onto O. Was "ROPE" actually "rope", or was it "ripe"?
Compression works by either declaring a pattern or by substituting. "Hello chello mello" with substitutions could see that "ello" is repeated and replace it with a token that means it. "H1 ch1 m1;1=ello".
You can restore this. It's lossless. But what if the input has no repeats? "AUC"? It can't be made shorter. Unless you've pre-defined a most of tokens that the compression algorithm knows about before even looking at a text. Maybe "AUC" has the token 47.
Since it must be shorter you have to use 2 characters or less to represent these 3 letters.
If you had such a list, the only way to guarantee that any input can be made shorter you must have pre-defined tokens for all possible 3-letter combinations. That number is much greater than the number of 2-number combinations, and so it's not possible. Maybe both "AUC" and "BBV" and "AQJ" all end up on 56.
So for the compressed text "56", which input was it? You cannot tell. You have most that information and you now only know that it must've been either "AUC", "BBV", or "AQJ".
I hope that helped.
In reality it's more complicated than this, and tokens doesn't have to be digits, and so on. But a simplified example might help when the generic principle is harder to see. :)
On the note of lossless compression, that is theoretically true. However, real life data is often not that random. We have patterns that repeat itself and we can build a mapping that maps the repeated patterns to a smaller representation.
Excellent math education and outreach.
the pigeonhole principle test was devastatingly hard when i took the discrete maths course. i remember it had to do with proving you could always find a triangle with a certain arrangement of colours. on a scale of 1 to 10, the average score was 2
Maybe i misunderstand what you are saying about lossless compression, but of course, lossless compression is possible. We even use it in everyday speech in the form of pronouns. In a computer program, you build a database of every word used in a document. Then, convert the document into reference numbers, which take up less space than the original document. I'm sorry if that's not what you meant, but it's easy to shrink the file size without losing any information.
Hymm that interesting. I will ask my teammates in team (IT) if they understand that there is no lossless compression becouse i see you didn (no offense) and you are know something about database.
Let me explain
you can compress manyfile becouse in most case file have low entropy.
For example databes of transaction in your shops
80 % of all transactions is selling your top 3 product
SOMELONGNAME1
SOMELONGNAME2
SOMELONGNAME3
So 80 % of your records have one of this 3 values
so now you can make a "dictionary"
{1: SOMELONGNAME1 , 2 :SOMELONGNAME2 , 3 : SOMELONGNAME3 }
And now you use much less space becouse now in your DataBase you storage 1,2,3
OFC now you can ask "how i store 1,2,3" you can for example use some character at start
for example
if start with "0" - don't use dictionary
if start with "1" -use dictionary
(or many dif solutions )
or sotrage
1 as SOMELONGNAME1
2 as SOMELONGNAME2
3 as SOMELONGNAME2
but 1,2,3 is only 0.01% of your rows so you still are ahead (:
Or you get data in JSON but every of this JSON have the same fields
so you can just saved that data by using "," and knowing that
first field is "name" , "surname" .,,,, etc
In video he said that there is no lossless compression algorithm for any input data
and this is true but we know that files are not "random" if you have some strange bits in your file you will just get error XD
You can actually test that by make file of randoms bits and then try to commpress (:
@@piodd4 What you are describing is called "tokenization." You form a "token" that represents a value. 1 is your token for SOMELONGNAME1. You would set it to something unique, and set a flag to scan input for any token, so it wouldn't be repeated accidentally. In this case, it would look for "1" and assign it a different token, so that "1" in your dataset would not get replaced by "SOMELONGNAME1" when it was decompressed.
A good program looks for repeated long words, tokenizes them, and replaces them in the text. Then it repeats the process recursively until there are no repeats, or tokenizing the repeats would result in a file size that is the same or larger than the original.
Decompression just works backward from there; Decompressing the tokens in reverse order until none are left.
I LOVE this video but have a question about the lossless compression part. Wouldn’t a key embedded in the compression/decompression software solve that issue? The more I think about it the more I confuse myself haha
Yea I think we need a video for lossless compression now
I just posted a long comment explaining why lossless compression algorithms exist, feel free to check it out. Or just check how the Huffman algorithm works, for example.
Very great bro....I thought to give this concept to choice but after this video it is my fav topic
I came home one day and told my sister ‘what I learned in discrete mathematics is if there’s more people in New York than possible hairs on a human head, then at least 2 people in New York have the same amount of hairs on their head’ and I think that’s the worst way to explain this to someone
Can't argue with that.
Yeah maybe that's a good example
so basically even though i have lossless but compressed data i cannot reconstruct the original out of principle ?
Not
this is not what they said in video
this feels like a ted talk, nice work!
This video is absolutely amazing!
Just cut one of your dominos in half.
At university this was one of the early concept covered at logic class, and it's funny how in my specific exam, the professor put a question that could be answered by applying the pidgeonhole principle in a relatively simple way, yet so many people failed to answer because it was a new question he never asked in any previous exam.
Its an exam you arent supposed to apply critical or innovative thinking but simply reiterating memorized stuff
@@clementineshamaney5137 That's stupid.
@Dojel Notmyrealname it's actually normal since exams are designed to test your knowledge, not your intellectual abilities. You use your abilities more in the process of learning, and you push your abilities to the limit on olympiads or during your thesis work.
@@arseniix In middle school, perhaps, and it's stupid there too. But in university exams are supposed to test your competence in the field of study.
@@arseniix They aren't. I never had one where it wasn't required to come up with your own answer at some point. Not even in primary school. Exams usually are designed in a way that make you use your knowledge in a way that shows that you didn't only memorize it, but also understand it. Exams that want you to just memorize random questions and answers are pointless. Everybody can memorize the different parts of the heart from a list and memorize the standard answer to questions about what they do. That doesn't mean that you actually understand how the heart works. Which was probably the point of the lesson.
Pigeons are super cute as well. They are very gentle birds and very loving.
But why did people try to put pigeons into pigeonholes?
4:10
Flat Earthers : It is treason then
Fake
it also often comes up when m is fixed and n can be as large as we want, eventualy we have a doubling which tends to be a useful case
That's a really great explanation!
The way my friend introduced me to the pigeonhole principle was in explaining the so-called birthday paradox. Since there are only 366 possible birthdays, as soon as you have 367 people together, you can be completely sure that at least two of them share the same birthday. After that, you do some probability to figure out how many people you have to have together for there to be a 50/50 chance that two of them have the same birthday
not really a paradox is it
@@sophovot5079 Yea, that's why I added that "so-called" in there. People call it a paradox, even though its not one
Its valuable and crystal clear. Still I will see once more so that I can explain to my son.