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

@hermangilbertbobbit3970

Жыл бұрын

Pigeons better

@HansLemurson

Жыл бұрын

What were the hamsters even _doing_ in the dovecote in the first place? Must have scared away the pigeons from their holes.

@chessmaster2041

Жыл бұрын

Hamster hole principle

@remy333

Жыл бұрын

@@chessmaster2041 that’s a different game altogether. Just ask the ER staff. 😂

@TheAllMightyGodofCod

Жыл бұрын

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!

@tommasobanfi8133

Жыл бұрын

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

@KinuTheDragon

11 ай бұрын

Honestly, given how simple it is, it seems to usually be taken as implicit, hence the difficulty in trying to come up with uses.

@ily____

11 ай бұрын

i still don’t get it 🥺

@AlmogBokobza-jh8un

11 ай бұрын

@@ily____ you don’t get the idea of the principle?

@ily____

11 ай бұрын

@@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 😐

*Me procrastinating by watching more enjoyable math*

Came for the pigeons, stayed for the math.

@GameDevEFacil

10 ай бұрын

came for the pigeons, stayed for the holes

@kevinfernandez9999

10 ай бұрын

"Came" for the pigeons you say??? 🤨📸

@GameDevEFacil

10 ай бұрын

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

@p0358

2 жыл бұрын

Well now they can't

@shufflecat3334

Жыл бұрын

Probably because it was mediocre no offense. (To those who do not know, this is a meme, I actually really enjoyed the video)

@whannabi

Жыл бұрын

​@@p0358 they can. You just don't see it. But wait until the button itself disappears

@thenamelessking375

Жыл бұрын

@@shufflecat3334 was it? I would like to see you try to make a similar video

@figboot

Жыл бұрын

@@thenamelessking375

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

@SpanningTree

3 жыл бұрын

Thanks!

@AJmara2772

2 жыл бұрын

Ver very Gud

@AJmara2772

2 жыл бұрын

I like your explanation idea Nice man U did it❤️

@KRYPTOS_K5

Жыл бұрын

@@SpanningTree It is debatable if the 2 points on the arbitrary equator line belong to any of the 2 hemispheres.

@angelmendez-rivera351

Жыл бұрын

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

@rickwilliams967

Жыл бұрын

You should check out VSauce if you haven't yet.

@BariumCobaltNitrog3n

Жыл бұрын

The BEST ever? And what are math?

@erikred8217

Жыл бұрын

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.

@BariumCobaltNitrog3n

Жыл бұрын

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

@erikred8217

Жыл бұрын

@@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 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 ^^

@tomatwalden

Жыл бұрын

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.

@SplendidKunoichi

Жыл бұрын

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

@cjlister8508

Жыл бұрын

A pigeon hole is just where you keep a pigeon.

@DavidHRyall

Жыл бұрын

@@SplendidKunoichi most people pigeonhole themselves by believing their are less capable than they really are

@angelmendez-rivera351

Жыл бұрын

@@SplendidKunoichi It is a mathematical theorem, though, but not all mathematical theorems are called by the name "theorem."

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

@erikred8217

Жыл бұрын

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

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

@SpanningTree

3 жыл бұрын

Thanks for the feedback!

@peNdantry

2 жыл бұрын

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

@taniakalsi2454

2 жыл бұрын

Yes I agree, the background music was rather distracting

@kebman

Жыл бұрын

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.

@olduncleamos

Жыл бұрын

@@peNdantry Presidential comment.

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.

@piodd4

Жыл бұрын

" 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

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.

@erikred8217

Жыл бұрын

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.

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

@petensue2708

Жыл бұрын

Ten people start on the first floor and enter the lift, that means there are only eight floors left and ten people

@johanponken

Жыл бұрын

@@petensue2708 The definition of "first floor" varies (e.g. with language; as you can see CM isn't a native English speaker).

@hermesthegreek5247

Жыл бұрын

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

@blueberrymuffin4921

Жыл бұрын

@@hermesthegreek5247 my thought exactly, that's how I interpreted it

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

@addy1154

2 жыл бұрын

How did you find out?

@anuragsuresh5867

2 жыл бұрын

@@addy1154 Look at the about page on his channel.

@proodnam9440

2 жыл бұрын

Anurag suresh see the description

@proodnam9440

2 жыл бұрын

Theres his name

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.

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!

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

@erikred8217

Жыл бұрын

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.

@gbasar1032

10 ай бұрын

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

@owenkanaal3457

Жыл бұрын

I mean, everything is just math

@theodoregossett9230

Жыл бұрын

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.

@angelmendez-rivera351

Жыл бұрын

@@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 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 exists, but that no surjective function h : X -> Y exists. Your "formulation" of the pigeonhole principle, that if |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| Y which is not injective, then |X| Another formulation is to say that if |X| 1. This one is the more straightforward formulation from the English wording.

@odar9729

Жыл бұрын

Like an octopus wiggling it’s multiple arms but the right one is cut off and by this you can tell the direction lol

Yeah in computer science you run across this all the time. And remembering it lets you solve some complex problems almost instantly.

@cryp0g00n4

Жыл бұрын

I must be an idiot cause I dont see the groundbreaking application.

@deathstar4794

5 ай бұрын

@@cryp0g00n4 Lol...Perfectly said.

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.

The compression example was beautiful, really made me understand how this can be useful

I never heard of this principle, but it is interesting to hear. Thank you 😊

@erikred8217

Жыл бұрын

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.

Really great explanation, thanks. I'm a programmer, but never thought of this concept directly.

That is a brilliant explanation! Thank you very much. Please keep making the videos

I wish this video existed when I was still learning discrete math back in university. It would have been so useful!

@urbanimmortalculitvator6652

11 ай бұрын

is your mind pigeon holed?

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!

@erikred8217

Жыл бұрын

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.

@citizenearth71

Жыл бұрын

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

The animations are very nice and the buildup in the way it teaches things is also very well thought out.

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

Insane Explaination and Insane graphics you deserves a million subcribers dude .. Keep growing

fantastic content! instantly subbed! keep the good work up

More of this please!!! The applications were beautifully explained I watched it once, twice, ... and lost the count :)

one pigeon had a good buddy willing to share his space

way better explanation than my college professor. Thanks so much

For curiosity i clicked For simplicity i rolled my eyes But surprised by learning I subscribe

@ChannelTrapesium

Жыл бұрын

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

@erikred8217

Жыл бұрын

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.

@Greenhawk96

Жыл бұрын

@@erikred8217 nobody said pigeon holing. Read the video title?

@erikred8217

Жыл бұрын

@@Greenhawk96 Pigeon holing, and pigeonhole mean the same thing. like golfing. and golf. It's called a present participle.

@erikred8217

Жыл бұрын

@@Greenhawk96 also Vernacular is another word you seem to lack. maybe context is a good starter for ya.

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 channel is massively underrated. Giving this to me was the single best thing that KZread algorithms had ever done.

This is a lot of effort! Thanks for this wonderful video!

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 the type of content I just love. Stimulates my brain so good

well explained ✨

Awesome explanation brother, Love the pigeons. You just got a subscriber.

Thank you for explaining the pigeon hole principle. I am a programmer and I really need to learn this.

@pkmabcd8270

Жыл бұрын

Shut up madrasi

Excellent animations; very helpful, thank you!

Thank you man your 8 mins video is equivalent to my 2nd semester classes

Next level animation! Awesome explanation!

thanks brian you are doing a great job

@SpanningTree

3 жыл бұрын

Thank you!

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

WOW! Thank you!!!! This video made the concept really easy to understand.

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.

@NotASpyReally

Жыл бұрын

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?

@Albtraum_TDDC

Жыл бұрын

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

@NotASpyReally

Жыл бұрын

@@Albtraum_TDDC Ooh so sometimes you can compress files and sometimes you can't, right?

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.

@adamw.8579

11 ай бұрын

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

@benwlee

10 ай бұрын

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.

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.

That's a really great explanation!

another rising star of youtube

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

@charleswalters5284

Жыл бұрын

Our schoolbooks were badly written on purpose.

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 🇦🇫😇👍

Excellent math education and outreach.

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?

@bladdnun3016

Жыл бұрын

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.

@dhruvilpatel4218

Жыл бұрын

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

@sudqi

Жыл бұрын

@@bladdnun3016 you are right but picking this example gives the impression that lossless compression is impossible

@bladdnun3016

Жыл бұрын

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

@sudqi

Жыл бұрын

@@bladdnun3016 Anyway, great effort. Thanks for the video.

Great explanation! I really appreciated the lossless compression example, that was smart.

Thanks a lot. Very nicely explained. Graphics and animation are excellent.

Very great bro....I thought to give this concept to choice but after this video it is my fav topic

Deserves way more views wowww

Imma send this to my maths and science teachers and tell em to teach this in class instead xD

The whole concept is explained very simply in such an interactive manner! Thanks for this content

@DrummerJacob

11 ай бұрын

Id say this is the opposite of simple. He repeats things so many times. This video could and should be 2 minutes max.

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 😊

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.

@abdulmasaiev9024

Жыл бұрын

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.

@NA-hi7lx

Жыл бұрын

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

@thekilla1234

11 ай бұрын

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

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

@MorreskiBear

Жыл бұрын

I laughed at the thought of 4 horrified pigeons each sharing a box with a bloody quarter-pigeon.

Please make more such videos they are so easy to understand with your explanation.

So interesting! I've learned a new thing today!

You say pigeonhole, I say "cloaca"

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

This is a very good explanation of the concept. Thanks.

Learned this for proofing in my math degree. Good Explanation.

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

@kzkaa.

Жыл бұрын

Can't argue with that.

@galaxy1234

Жыл бұрын

Yeah maybe that's a good example

I didn't fully get the last one. But the geographical example was fascinating!

@Mankepanke

Жыл бұрын

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

Amazing work

Wow! That was such a nice explanation. I’m stunned.

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

@live688

Жыл бұрын

Yea I think we need a video for lossless compression now

@CorentinLeman

Жыл бұрын

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.

I just like pigeons and holes.

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.

Its valuable and crystal clear. Still I will see once more so that I can explain to my son.

But why did people try to put pigeons into pigeonholes?

so basically even though i have lossless but compressed data i cannot reconstruct the original out of principle ?

@piodd4

Жыл бұрын

Not this is not what they said in video

Well made video. Thank you.

Excellent explanation. Thanks

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.

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.

@piodd4

Жыл бұрын

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

@eclectichoosier5474

Жыл бұрын

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

Amazingly good presentation!

I don't know why, but I was mesmerized by this video.

4:10 Flat Earthers : It is treason then

@user-mc6tq7xb2q

2 жыл бұрын

Fake

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.

@clementineshamaney5137

Жыл бұрын

Its an exam you arent supposed to apply critical or innovative thinking but simply reiterating memorized stuff

@dojelnotmyrealname4018

Жыл бұрын

@@clementineshamaney5137 That's stupid.

@arseniix

Жыл бұрын

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

@dojelnotmyrealname4018

Жыл бұрын

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

@schrodingerskatze4308

Жыл бұрын

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

Thanx a lot man wonderful and simple animations make it my much easier when your explanation makes it much more easier

this video blows my mind. how can such a simple principle lead to so many proofs?

Just cut one of your dominos in half.

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

@sophovot5079

Жыл бұрын

not really a paradox is it

@justinjozokos1699

Жыл бұрын

@@sophovot5079 Yea, that's why I added that "so-called" in there. People call it a paradox, even though its not one

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

thanks for sharing this knowledge in this nice and educative way! right on, bro