According to Google, there are 129,864,880 books in the entire world. And I've on Wikipedia-the longest book ever written is "Men of Goodwill" by the French author "Jules Romains" that has 2,070,000 words. So by a simple calculation, it means that there's must be 63 books with the exact same number of words. I completely love your channel.
Is that correct? Everyone having a birthday that falls on a finite calendar is a driving force for the pigeon principle. But in the case of publication (something artificially created), one could create a work with 2,070,001 words and it could be unique. The other 129,864,880 books can indeed overlap each other multiple times but this one work would still be unique. Great channel.
The point is that assuming both the facts Kfir brought are true, the conclusion must be, as well. If one of the 129,864,880 books Google lists has MORE words than Men of Goodwill, then the second fact is false, and the conclusion becomes suspect.
Forgive me, I misunderstood his statement. It was not that there were 63 books with the highest number of words but 63 books with identical number of words. Yes, he is indeed right - I misread the statement.
Brouwer's fixed point theorem is one of my favorite pidgeonholeings. It states that for a continuous function f mapping a set onto itself there's a point x that satisfies f(x)=x. Easy to illustrate this way: take a world map and spread it out on the floor (map the world onto itself), and there has to be a point that's has the same coordinates on both the map and on the planet itself.
I can't believe I never thought of this before, but the PIN example could be extended to physical locks. If a lock cylinder has, say, five pins (the number shown on the sample photo of a Yale lock I googled), and each pin has only x range of elevations, depending on how finely calibrated the manufacturing is, and the lock company in question makes hundreds of thousands (millions?) of units for sale, then somewhere in the world, there's a person you've never met who's house/car/bicycle key will open yours.
yep, One of my friends has a key that opens both bikes of his kids. Bikes (with lock) were purchased 3 years apart and are of different make and model...
Great explanation! I am really liking this new series. Maybe do something on proofs and techniques: induction, contradiction, etc.? (You could include some nice ones like irrationality of sqrt(2) or the Tibet Mountain Climber problem) :D
This series could/should encourage more than just passive viewing: Support both hands-on work (1-2 problems to help internalize the concepts in the video) and also inspire curiosity to probe deeper/wider (links to other discussions and courses). I've tossed a couple challenges into the comments for some of these videos and have been delighted by the responses. I think there's a real hunger there that could be far better addressed by being an integral part of the videos themselves. The underlying issue concerns "learning modalities" (Google it); the ways in which each of us can take in new knowledge and develop new skills. Depending on who you ask, there are either 5 or 7 fundamental Learning Modalities (domain dependent, it seems). Watching and/or listening to a recording is just one way: Doing is another. The more learning modalities that are brought to bear directly leads to more folks learning more things.
MATH ROCK!! Hi, I stumbled across your appearance in PBS SPACE TIME explaining math’s perspective on singularities. After the video I checked out yours. Loved it, can’t wait to show my son. He’s only 11 and loves math. I bet he would enjoy your insightful examples, they are very creative!! Count me a subscriber and look forward to the rest of the series!! James
There were 39 interesting facts in this video, and it is eight-and-a-half minutes long, so the more complex version of the pigeonhole principle shows there must be at least one minute-long segment of this video that contained at least five of the interesting facts.
I had to spend some time to find how that formal statement at 5:26 is related to Dirichlet's principle in common understanding of it. I'm still unsure if my reasoning is correct so it would be cool to get some clarification on that.
this is an amazing channel, 3 episodes and we're already learning so much about the application and characteristics of the mathematics, keep up the good work!
The infinite pigeonhole principle: given an infinite number of pigeons, and a finite number of holes, one hole contains an infinite number of pigeons. Then we can talk about regular infinite cardinals κ and how given κ pigeons in λ < κ holes, at least one hole as κ pigeons... :-P
What could we say with ordinals? If there are omega pigeons and omega+1 pigeon holes, can we make any inference except that somebody has used super-tasking for a very bizarre purpose?
A F it's not straightforward, since the order structure on the ordinal needs to be taken into account. Otherwise since they are the same cardinality one can easily fit exactly one pigeon per hole. You might want to look up the concept of *cofinality*.
I prefer the alternative, yet equivalent, phrasing of the pigeonhole principle. Given an n number of pigeons. If I drill m > n holes into the pigeons, then there is at least one pigeon with more than 2 holes drilled in it.
"Unless somebody loses or grows a hair. Then they get kicked out." - Or perhaps they kick out everybody else: Even if one of them loses or grows a hair there still have to be at least 19 people to share hair count. So if the group loses a member through this act and assuming that, before this loss, the group was indeed made up of _exactly_ 19 people and furthermore unique, there now needs to be a different group of at least 19 people, so before that there must have been at least one group of 18 people who happened to have exactly 1 hair more or less than the club of 19 people and who thus become the new club.
not at least there must be at least 19 people with the same number of hairs doesn't mean there are 19 people with every number of hairs you know that at least in one category (of numbers of hairs) there will be at least 19 people. But it could be more. Hell, it could be 99% of the world population has exactly the same number of hairs, but we can't know that for certain. at the same time there might be some categories with no people in them. Maybe if you lose a hair, you end up in a club with no one else. Again, we can't know that for certain.
True -- if somebody loses or grows a hair they may cause the whole club to collapse. We know there must still be some number of hairs that has at least 19 people who share it, so a new club could be formed, but it may not be either the previous nor the new hair-count of the mysterious hair-grower/loser.
If the largest number of people with matching hairs is 19, that would mean that all other body hair counts have either 18 or 19 members. If only one club has 19 members, anyone leaving that club automatically forms a new club with 19 members. Further, if everyone joined a club with matching body hair count, and the largest club was 19 people, there are at least 389 million clubs (7.4 billion / 19).
Lysander Dusseljee but does the club necessarily contain all ppl with given number of body hair? Because if it doesnt, the statement is not necessarily true
The moment you started in the direction of counting hairs, I immediately thought 'Pigeon hole principle'. It's one of my strongest memories from university. I blew a question on it on both a midterm and a final. My problem was that I considered the concept too basic to name. It stems naturally and intuitively from the very idea of a mean value. I hated that I had to name such an obvious thing, it felt out of place. But now, having fallen prey the second time to the same error, the name springs readily to mind. I seem to recall having made another error on the midterm, but there's a good chance the final was perfect apart from that omission. And I'm nostalgiaing over university right now...
Yep! It's about using rational numbers to approximate (i.e. get close to) real numbers. Also, fun fact: Dirichlet called it the "schubfachprinzip" which means "drawer principle"
Great stuff! Wonder how you might use this in combination with other factors to narrow down which galaxies might have life? Thinking we need to take into account the conditions for life as we know on earth and correlate to other conditions (proximity to stars, atmosphere type, and etc.)
how does that birthday stat you stated account for the birthday paradox ? ( or rather does the birthday paradox take into consideration the pidgeon hole theory?)
Unfortunately, the pigeonhole principle doesn't guarantee that that "soulmate" would be of your favourite gender though... They may very well all be of the opposite gender. A slight inconvenience, but a soulmate is a soulmate, right? ;)
@@sweethater8558 Not really. First of all, the principle doesn't guarantee everyone gets a "soulmate." 400 million people can have all possible 400 million numbers of hairs between them...and then all other 6.9 billion people could, theoretically, all have the same number of hairs as one another. In that case, 6.9 billion + 1 people have 6.9 billion possible "soulmates", and everyone else has none. Then, even if you do have a soulmate, the only way you're guaranteed to have one of your preferred gender is either: (A) if the number of possible soulmates > the number of people NOT of your preferred gender, or (B) if you're bisexual.
It's weird how I almost stopped trying to figure it out because of an even simpler answer in my opinion. There just has to be at least 2 people with 0 hairs.
Well done! The Pigeonhole Principle can provide an excellent introduction to Discrete Math. It is also fundamental to several important algorithms in Computer Science (applied math), particularly in areas such as hashing and encoding. The Pigeonhole Principle is an especially useful tool to help *disprove* things! For example: Is there such a thing as a lossless compression algorithm that can compress everything fed to it? The answer is "no", but can you use the Pigeonhole Principle to quickly prove it?
BobC here's my go at it. Imagine your data is two bits. The only size less that than is one bit. But, as there are only 2 outputs (0 or 1) that our 4 inputs (00, 01, 10, 11) must go to, there is one output that can be inverted to at least two inputs. QED
BobC sure. You can either use induction, or that there are only 2^(n-1) numbers less than 2^n. Therefore you'll never have enough smaller lengths to hold the big one
i know it! i know it! if you feed it 8 bits of data, then you have 256 possible inputs. all the different inputs need to be stored in the output, so you need 256 distinct outputs, which is also 8 bits :D
Ah, but what if I group input symbols into larger chunks (such as repeated characters or frequently occurring patterns), then encode over larger "strides"? Can't that get me around this limitation? Longer strides is one of the approaches used by the lossless Zip file compression algorithm: Can you prove there MUST be a file that Zip (or related algorithms such as LZRW and friends) can't make smaller? Can you provide an algorithm or code that will generate such a file of arbitrary size? That is, easily create an incompressible file? (Hint: It's a trick! The proof is not as mathematically elegant as a dis-proof based on the Pigeonhole Principle, but it is conceptually simpler, equally effective, and far easier to demonstrate.)
There are 7.5 billion people on earth. Suppose two events happen simultaneously if they are no more than 1 millisecond apart. A day has 86.400.000 seconds. So if every person on earth farts at least once per day, we have at least 86 people who farted or will fart simultanously today :)
@@HarryNicNicholas thats why the statement assumes that "simultaneous" events are only 1 millisecond apart; of course nothing is *perfectly* simultaneous but 1 millisecond apart is pretty damn close
I was about to ask what if one team scored all 5 goals but then realised that at least one team scored at least three goals, at least I answered my own question but feel really dumb in even typing this comment
Vussianspy hey, being inquisitive and skeptical is how you learn! Even if you consider a question "dumb," it's important to ask it because otherwise how would you learn? Even better, you used the tools given to you to answer the question yourself, so bonus points!
We couldn't agree more! Math can be tricky, and it's good to puzzle over new concepts. Fortunately, the mathematics community is awesomely supportive, since we're all exploring this crazy abstract universe together!
Oh wow what a lovely response, I was half joking in calling myself dumb over a silly mistake but such a welcoming response from you both, really is encouraging to hear, thanks!
I think a nice continuation of the pigeonhole principal is the birthday paradox. They aren't linked per se, but the idea of counting collisions in categories is a binding thread between the two.
My intuition may be failing me here, but does this actually work? I'm thinking about 5 points on a torus, specifically. It seems clear to me when the spaces are spheres and euclidean spaces, but not for less trivial topological spaces.
I don't know. I wouldn't assume that it does. I think you're suggesting something different than what I was saying. I was talking about all of free space where the object/shape is only used to partition free space into 2 regions. Just a nod to the beginning of this video and the last. .... You seem to be suggesting using the shape surface to define a space. I don't know the answer to that.
Mike Guitar Right, ok. In the standard Euclidean space with hyperplanes, it definitely works. When I think of an n dimensional space, I typically think of an n dimensional manifold, and these can be much more general than just Euclidean space. For example, a sphere is a 2 dimensional manifold and a similar statement would work for any dimension sphere
a point on a line cuts the line in 2. A line in a plane cuts the plane in 2. A plane in 3D space cuts the 3D space in 2. A 3D snapshot in spacetime cuts 3D-spacetime in 2 (past vs. future). etc.
My favourite application is in proving that, regardless of the number of people that there are in a room, at least two of them have shaken the same number of hands.
Here's an interesting application of the pigeonhole principle that I've gotten as an exercise in a combinatorics class: Suppose a woodcutter cuts down at least one tree per day over a period of 90 days but he never cuts down more than five trees within three days. Show that for any number k between 1 and 29 there exists some period of consecutive days in which the woodcutter cuts down exactly k trees. Here's a more mathematical example from the same class: Let A be an n-element subset of {1, ..., 2n - 2}. Show that there are always two distinct elements of A such that one of them is an integer multiple of the other.
I thought this new channel would be a little bit more in depth, proving that there are more real numbers than integers is much more interesting than just talking about hairs and categories.
I would suspect cardinality will come up eventually, but this made for really fun examples that I could share with family and they'd get it and be entertained. And the principle is important.
Hey so hate to burst your bubble but that's not necessarily true. What it means, is that there exists at least one character who is shared by 869565. That character need not necessarily be your main, you see ? It could be that every single person except you, plays widowmaker, and you play reinhardt. In this case widowmaker is the category that satisfies the 'at least 869565 players' requirement, but you are the only reinhardt player in the world !
I have seen someone use the pigeon hole principle to explain computer memory management. It was a way to check to see if there is more data than hard drive sectors, roughly.
Correction: There are at least 23,272 New Yorkers who share the same birthday on some day of the year given the population number of 8.5 million. The 366th day only occurs once every four years.
Regarding the last example. If one of them loses a hair and is kicked out that person is put into another box. That shrinks the first box the person was in while growing the new one. It is therefore possible that a person leaving one group, makes the new one 'largest' and exclusive. As the remaining original group is no longer part of the largest, one interpretation is that all members were kicked out and replaced except the one whom lost hair, which remained in the 'largest/exclusive' group.
6:00 ish, it doesn't prove all cases, but if 4 of them form a tetrahedron, the fifth will always be placed in a hemisphere containing exactly 3 points already
Yes, it's true. And clever reasoning -- mathematicians are always finding the special cases. But even if you exclude people with no hair, the analysis still works. :)
I heard once the story that Gauss, as a young boy, was going with his father through the forest. He asked his father if two trees in that forest had the same number of leaves.. to which the father answered: "only God could know that!" But the young Gauss said "if the number of trees in this forest is larger than the number of leaves of the thickest tree, there must exist two trees with the same number of leaves"... It looks like the pigeon hole principle has bee discovered spontaneously by many thinkers throughout history
Ramsey theory is a sort of generalization of the pigeonhole principle, in the sense that if you take an "object" large enough (e.g. enough pigeons) and you divide it to finitely many parts (e.g. holes), then one of these parts will contain an object of the same "type". In the pigeonhole principle if you take a lot of pigeons (n) and you divide them into d holes, then you have at least one hole with "a lot" (n/d) pigeons. The standard Ramsey theory on graphs says that if you color a big enough full graph by finitely many color, then at least one of the induced monochromatic subgraphs (i.e. edges of the same color) will contain a big enough full graph. You also have results like if you color by d colors a long enough arithmetic progression (for example 1,2,...,N with N big compared to d), then at least one of these colors will contain a long arithmetic progression (this theorem is called Van der Waerden's theorem, or its stronger form Szemerédi's theorem).
Is this related to the Kochen-Specker theorem as an application in infinite sets? Basically it demonstrates it's impossible to assign quantum spin values before measurement because the number of points required exceeds the number of points in the surface of a sphere. It implies that either the property did not physically exist before measurement (no hidden variables) or the property value is dependent on the measurement context (no meaning to the counter-factual). Either is mind-blowing.
Maybe like space time do challenge questions and them each week share the results from fans? That that could satisfy the urge for proof and drive some good engagement:)
When I jump on a train or bus, all the seats will be filled by single passengers before I have to sit near an occupied seat (assuming seats are configures in pairs).
It is estimated that 100 billion humans have lived throughout history. Given that there is no instance of a human living past 130 years, that gives 4.1 billion possible lifetimes measured in seconds. That must mean 24 people had to have lived for the same amount of time _to the second_. Out of these 24 people, there is a 54% chance that two people share the same death date. That means it is likely that at some point in the past, two people died on the same date having lived for the exact same amount of time. Neat.
+anticorncob6 The twins wouldn't die at exactly the same second unless they were both squashed into Jello or something. But even then, they weren't born at the same time, at least according to their birth certificates. I think life begins at conception but don't get me started on that.
My favourite of this type of arguments is probably: If you have n objects and you fill all n categories with them, then there is exactly one object in every category (and vice versa, if you fill n objects into n categories so that there is only one object per category, then you filled every category)
It's interesting how this combines with the birthday problem. If a group has 70 people, there is a 99.9% probability that at least 2 of them share a birthday, but you still need 296 more people to reach 100% probability.
Hi! You remeber my last comment, on the infinite infinities? This is my wildest usage of the pidgon hole principle! I know there are at least infinite number of lowest rate of infinities, one the 2D graph. My god, I am bright today!!!
This video has 64,024 views (as of this comment) and it is 515 seconds long, which means that at least 127 people have stopped watching at the exact same second (hopefully the last!)
7:30 .. That said, would be nice to see your explination of the birtday paradox :) [> 50% chance that 2 random ppl out of a group of 25 share the same birthday]
That hairy cylinder disturbed me on an unexpected level.
At least you could comb the hairs in one direction without them clumping up at the ends.
you suffer from tuberculuhirsuitnephobia, it can be cured by paypalling me.
According to Google, there are 129,864,880 books in the entire world.
And I've on Wikipedia-the longest book ever written is "Men of Goodwill" by the French author "Jules Romains" that has 2,070,000 words.
So by a simple calculation, it means that there's must be 63 books with the exact same number of words.
I completely love your channel.
Whoa, that's a fierce application of the general pigeonhole principle! Sweet!
Is that correct? Everyone having a birthday that falls on a finite calendar is a driving force for the pigeon principle. But in the case of publication (something artificially created), one could create a work with 2,070,001 words and it could be unique. The other 129,864,880 books can indeed overlap each other multiple times but this one work would still be unique.
Great channel.
The point is that assuming both the facts Kfir brought are true, the conclusion must be, as well. If one of the 129,864,880 books Google lists has MORE words than Men of Goodwill, then the second fact is false, and the conclusion becomes suspect.
Forgive me, I misunderstood his statement. It was not that there were 63 books with the highest number of words but 63 books with identical number of words. Yes, he is indeed right - I misread the statement.
why?
Ah, yes, the pigeon-hole principle.
If you want to put n holes into k pigeons where n > k, then there must be at least n/k holes in some pigeon.
The way you're saying it it sounds like you're talking about shooting pigeons
premise 1: cheese has holes
premise 2: more cheese more holes
premise 3: more holes less cheese
conclusion: more cheese less cheese.
awesome thought-provoking show. never seen an actual captivating youtube math series before.
and the host is gold.
Benny Z have you never watched vi hart or vsauce (sometimes) or Numberphile or Matt parker?
Can definitely recommend Matt Parker and James Grime.
I feel like the host is mostly carbon and hydrogen though.
oh dear lord, how could I forget numberphile?
numberphile is sometimes nonsensical though. Also check out 3blue1brown
Gotta admit, I'm really liking this series. I look forward to the next video!
Feel bad for me and you because this show is gone FOREVER
rip
I can't believe I'm discovering this awesome show years after its finite end! The heartbreak
Brouwer's fixed point theorem is one of my favorite pidgeonholeings. It states that for a continuous function f mapping a set onto itself there's a point x that satisfies f(x)=x. Easy to illustrate this way: take a world map and spread it out on the floor (map the world onto itself), and there has to be a point that's has the same coordinates on both the map and on the planet itself.
I can't believe I never thought of this before, but the PIN example could be extended to physical locks. If a lock cylinder has, say, five pins (the number shown on the sample photo of a Yale lock I googled), and each pin has only x range of elevations, depending on how finely calibrated the manufacturing is, and the lock company in question makes hundreds of thousands (millions?) of units for sale, then somewhere in the world, there's a person you've never met who's house/car/bicycle key will open yours.
yep, One of my friends has a key that opens both bikes of his kids. Bikes (with lock) were purchased 3 years apart and are of different make and model...
@@janinepost That's almost eerie.
The pigeonhole principal tells us that there can never be a compression algorithm that reduces the size of all data.
Abe Dillon the pigeonhole sounds like a highly conformist school ;)
Jonas Hellberg it is indeed. It has a poor English program though.
Not one that keeps the files distinct, sure.
Abe Dillon i dont get it, can you elaborate a bit more?
ThePedroPimenta I'm not very good at explaining, so I'll point you to a good article on the topic. Google "kolmogorov complexity, a primer"
PBS Space Time sent me here. Just wanted to say, this new series is absolutely fantastic so far. Please keep 'em coming!
I really hope this series is actually infinite. Keep up the good work!
Great explanation! I am really liking this new series. Maybe do something on proofs and techniques: induction, contradiction, etc.? (You could include some nice ones like irrationality of sqrt(2) or the Tibet Mountain Climber problem) :D
I agree. would be cool
Yes, would very much like to see this.
This series could/should encourage more than just passive viewing: Support both hands-on work (1-2 problems to help internalize the concepts in the video) and also inspire curiosity to probe deeper/wider (links to other discussions and courses).
I've tossed a couple challenges into the comments for some of these videos and have been delighted by the responses. I think there's a real hunger there that could be far better addressed by being an integral part of the videos themselves.
The underlying issue concerns "learning modalities" (Google it); the ways in which each of us can take in new knowledge and develop new skills. Depending on who you ask, there are either 5 or 7 fundamental Learning Modalities (domain dependent, it seems). Watching and/or listening to a recording is just one way: Doing is another.
The more learning modalities that are brought to bear directly leads to more folks learning more things.
MATH ROCK!! Hi, I stumbled across your appearance in PBS SPACE TIME explaining math’s perspective on singularities. After the video I checked out yours. Loved it, can’t wait to show my son. He’s only 11 and loves math. I bet he would enjoy your insightful examples, they are very creative!! Count me a subscriber and look forward to the rest of the series!! James
If you only buy two colors of socks, you only need to pull 3 out of the drawer in the dark in the morning to get a matching pair :)
I have one color of socks PROBLEM SOLVED
Considering you have only two pairs of socks in your drawer.
One pair in the drawer: The other is on my feet.
+Tyler Morita The single most useful application of the pigeon hole theory ever.
yeah, but if it's dark, how do you pick the two to actually put on? if you're turning on a light, why not have it on while at the drawer?
I DEMAND THE THUMBNAIL BAVKGROUND TO BE RELEASED AS A WALLPAPER
Here ya go!
imgur.com/a/yLfHU
PBS Infinite Series THANKS YOU SO MUCH
PBS Infinite Series at least half as many viewers would have demanded the thumbnail?
"Mankind's Capilarity viewed from a Mathematician" PBS Infinite. Great piece of work.
Cylindres shapes covered with hair. Sounds like a math joke :)
this is why i love the internet
There were 39 interesting facts in this video, and it is eight-and-a-half minutes long, so the more complex version of the pigeonhole principle shows there must be at least one minute-long segment of this video that contained at least five of the interesting facts.
I wish this show could go on forever.
I had to spend some time to find how that formal statement at 5:26 is related to Dirichlet's principle in common understanding of it. I'm still unsure if my reasoning is correct so it would be cool to get some clarification on that.
this is an amazing channel, 3 episodes and we're already learning so much about the application and characteristics of the mathematics, keep up the good work!
The infinite pigeonhole principle: given an infinite number of pigeons, and a finite number of holes, one hole contains an infinite number of pigeons.
Then we can talk about regular infinite cardinals κ and how given κ pigeons in λ < κ holes, at least one hole as κ pigeons... :-P
What could we say with ordinals? If there are omega pigeons and omega+1 pigeon holes, can we make any inference except that somebody has used super-tasking for a very bizarre purpose?
A F it's not straightforward, since the order structure on the ordinal needs to be taken into account. Otherwise since they are the same cardinality one can easily fit exactly one pigeon per hole.
You might want to look up the concept of *cofinality*.
You cannot use an ordinal to describe a cardinality.
Didn't Georg Cantor raise pigeons?
What if we just use cardinals instead of pigeons.
This channel is great! I hope to see more of these
This girl is awesome.
I like that the principle is both highly intuitive and the spitting image of a non-constructive argument.
I prefer the alternative, yet equivalent, phrasing of the pigeonhole principle.
Given an n number of pigeons. If I drill m > n holes into the pigeons, then there is at least one pigeon with more than 2 holes drilled in it.
"Unless somebody loses or grows a hair. Then they get kicked out." - Or perhaps they kick out everybody else: Even if one of them loses or grows a hair there still have to be at least 19 people to share hair count. So if the group loses a member through this act and assuming that, before this loss, the group was indeed made up of _exactly_ 19 people and furthermore unique, there now needs to be a different group of at least 19 people, so before that there must have been at least one group of 18 people who happened to have exactly 1 hair more or less than the club of 19 people and who thus become the new club.
not at least
there must be at least 19 people with the same number of hairs doesn't mean there are 19 people with every number of hairs
you know that at least in one category (of numbers of hairs) there will be at least 19 people. But it could be more. Hell, it could be 99% of the world population has exactly the same number of hairs, but we can't know that for certain.
at the same time there might be some categories with no people in them. Maybe if you lose a hair, you end up in a club with no one else. Again, we can't know that for certain.
True -- if somebody loses or grows a hair they may cause the whole club to collapse. We know there must still be some number of hairs that has at least 19 people who share it, so a new club could be formed, but it may not be either the previous nor the new hair-count of the mysterious hair-grower/loser.
If the largest number of people with matching hairs is 19, that would mean that all other body hair counts have either 18 or 19 members. If only one club has 19 members, anyone leaving that club automatically forms a new club with 19 members. Further, if everyone joined a club with matching body hair count, and the largest club was 19 people, there are at least 389 million clubs (7.4 billion / 19).
Lysander Dusseljee but does the club necessarily contain all ppl with given number of body hair? Because if it doesnt, the statement is not necessarily true
The moment you started in the direction of counting hairs, I immediately thought 'Pigeon hole principle'. It's one of my strongest memories from university. I blew a question on it on both a midterm and a final. My problem was that I considered the concept too basic to name. It stems naturally and intuitively from the very idea of a mean value. I hated that I had to name such an obvious thing, it felt out of place. But now, having fallen prey the second time to the same error, the name springs readily to mind.
I seem to recall having made another error on the midterm, but there's a good chance the final was perfect apart from that omission. And I'm nostalgiaing over university right now...
Can you please tell us what's the theorem that was mentioned by Dirichlet?
Dirichlet's approximation theorem
Yep! It's about using rational numbers to approximate (i.e. get close to) real numbers.
Also, fun fact: Dirichlet called it the "schubfachprinzip" which means "drawer principle"
I like how the pressed elevator buttons form a Game of Life glider
Damn somoene got to it before me
I like the background music, specially the one that starts at 3:37. Does anyone know its name?
the longest youtube video is 2146000 seconds long. There are 26.1 billion videos on TH-cam. That means 12162 videos are the same length
2:59 Ceave Gaming confirmed
Great stuff! Wonder how you might use this in combination with other factors to narrow down which galaxies might have life? Thinking we need to take into account the conditions for life as we know on earth and correlate to other conditions (proximity to stars, atmosphere type, and etc.)
Glad I found about this series.
how does that birthday stat you stated account for the birthday paradox ? ( or rather does the birthday paradox take into consideration the pidgeon hole theory?)
Lit button pattern at 4:45 is a glider in the Game of Life.
kandrc Lol
If you find a person with the same number of body hairs as you, they're your soulmate and you have to marry them.
hopefully you're already pretty intimate if you're counting each other's body hairs.
Unfortunately, the pigeonhole principle doesn't guarantee that that "soulmate" would be of your favourite gender though... They may very well all be of the opposite gender. A slight inconvenience, but a soulmate is a soulmate, right? ;)
Can't you make it guarantee your preferred gender? Half of 7.3 billion is still more than 400 million, right?
If my soulmate has many hairs as I do, I will pass.
@@sweethater8558 Not really. First of all, the principle doesn't guarantee everyone gets a "soulmate." 400 million people can have all possible 400 million numbers of hairs between them...and then all other 6.9 billion people could, theoretically, all have the same number of hairs as one another. In that case, 6.9 billion + 1 people have 6.9 billion possible "soulmates", and everyone else has none.
Then, even if you do have a soulmate, the only way you're guaranteed to have one of your preferred gender is either: (A) if the number of possible soulmates > the number of people NOT of your preferred gender, or (B) if you're bisexual.
keep up the good work. really pleased with the channel and the host
It's weird how I almost stopped trying to figure it out because of an even simpler answer in my opinion. There just has to be at least 2 people with 0 hairs.
Well done!
The Pigeonhole Principle can provide an excellent introduction to Discrete Math. It is also fundamental to several important algorithms in Computer Science (applied math), particularly in areas such as hashing and encoding.
The Pigeonhole Principle is an especially useful tool to help *disprove* things! For example: Is there such a thing as a lossless compression algorithm that can compress everything fed to it? The answer is "no", but can you use the Pigeonhole Principle to quickly prove it?
BobC here's my go at it. Imagine your data is two bits. The only size less that than is one bit. But, as there are only 2 outputs (0 or 1) that our 4 inputs (00, 01, 10, 11) must go to, there is one output that can be inverted to at least two inputs. QED
Excellent! Does the "dis-proof" generalize to arbitrary lengths?
BobC sure. You can either use induction, or that there are only 2^(n-1) numbers less than 2^n. Therefore you'll never have enough smaller lengths to hold the big one
i know it! i know it!
if you feed it 8 bits of data, then you have 256 possible inputs. all the different inputs need to be stored in the output, so you need 256 distinct outputs, which is also 8 bits :D
Ah, but what if I group input symbols into larger chunks (such as repeated characters or frequently occurring patterns), then encode over larger "strides"? Can't that get me around this limitation?
Longer strides is one of the approaches used by the lossless Zip file compression algorithm: Can you prove there MUST be a file that Zip (or related algorithms such as LZRW and friends) can't make smaller?
Can you provide an algorithm or code that will generate such a file of arbitrary size? That is, easily create an incompressible file?
(Hint: It's a trick! The proof is not as mathematically elegant as a dis-proof based on the Pigeonhole Principle, but it is conceptually simpler, equally effective, and far easier to demonstrate.)
Thank you for making me smile. Cheers.
There are 7.5 billion people on earth. Suppose two events happen simultaneously if they are no more than 1 millisecond apart. A day has 86.400.000 seconds. So if every person on earth farts at least once per day, we have at least 86 people who farted or will fart simultanously today :)
My average is MUCH higher than that. I eat a high-fiber diet for health reasons.
God dam it!!!!!!! If you didn't win Nobel Prize for mathematics for this, this world is ruined
nothing happens "simultaneously" though....
@@HarryNicNicholas thats why the statement assumes that "simultaneous" events are only 1 millisecond apart; of course nothing is *perfectly* simultaneous but 1 millisecond apart is pretty damn close
I was about to ask what if one team scored all 5 goals but then realised that at least one team scored at least three goals, at least I answered my own question but feel really dumb in even typing this comment
Vussianspy hey, being inquisitive and skeptical is how you learn! Even if you consider a question "dumb," it's important to ask it because otherwise how would you learn? Even better, you used the tools given to you to answer the question yourself, so bonus points!
We couldn't agree more! Math can be tricky, and it's good to puzzle over new concepts. Fortunately, the mathematics community is awesomely supportive, since we're all exploring this crazy abstract universe together!
Oh wow what a lovely response, I was half joking in calling myself dumb over a silly mistake but such a welcoming response from you both, really is encouraging to hear, thanks!
so amazing, thank you for the great video!
Well done! But, here is a thought, how do you measure the hairs not knowing both the rate of growth and positions simultaniously?
Nice videos! You need to do the hairy ball theorem now!
I think a nice continuation of the pigeonhole principal is the birthday paradox. They aren't linked per se, but the idea of counting collisions in categories is a binding thread between the two.
If you have an n-dimensional (Euclidean) space with 5 points , you can use an (n-1)-dimensional hyperplane to section off 4 of the points.
My intuition may be failing me here, but does this actually work? I'm thinking about 5 points on a torus, specifically.
It seems clear to me when the spaces are spheres and euclidean spaces, but not for less trivial topological spaces.
I don't know. I wouldn't assume that it does. I think you're suggesting something different than what I was saying. I was talking about all of free space where the object/shape is only used to partition free space into 2 regions. Just a nod to the beginning of this video and the last. .... You seem to be suggesting using the shape surface to define a space. I don't know the answer to that.
problem is you can't section of a region of your n-dimensional space with a (n-1)-dimensional object. Think of 3-d and a circle.
Mike Guitar Right, ok. In the standard Euclidean space with hyperplanes, it definitely works.
When I think of an n dimensional space, I typically think of an n dimensional manifold, and these can be much more general than just Euclidean space. For example, a sphere is a 2 dimensional manifold and a similar statement would work for any dimension sphere
a point on a line cuts the line in 2. A line in a plane cuts the plane in 2. A plane in 3D space cuts the 3D space in 2. A 3D snapshot in spacetime cuts 3D-spacetime in 2 (past vs. future). etc.
This video makes me remember the time in secondary school, and we called it is the Dirichlet principle.
My favourite application is in proving that, regardless of the number of people that there are in a room, at least two of them have shaken the same number of hands.
didn't understand the goals example a 6:57... isn't it possible that one team scored 1 goal and the other scored 4?
oh right! lol so in my example the second team is the one that's scored atleast 3... i didn't make that flip in my head. Thank you +shomolya :)
Here's an interesting application of the pigeonhole principle that I've gotten as an exercise in a combinatorics class:
Suppose a woodcutter cuts down at least one tree per day over a period of 90 days but he never cuts down more than five trees within three days. Show that for any number k between 1 and 29 there exists some period of consecutive days in which the woodcutter cuts down exactly k trees.
Here's a more mathematical example from the same class:
Let A be an n-element subset of {1, ..., 2n - 2}. Show that there are always two distinct elements of A such that one of them is an integer multiple of the other.
Great content! Thanks for sharing!
More interesting then I thought. Thanks!
4:46 the pattern of the lit buttons resembles the glider from Conway's game of life. is that just a coincidence or did you do this deliberately?
I thought this new channel would be a little bit more in depth, proving that there are more real numbers than integers is much more interesting than just talking about hairs and categories.
I would suspect cardinality will come up eventually, but this made for really fun examples that I could share with family and they'd get it and be entertained. And the principle is important.
Overwatch has 20 million players and 23 playable characters. which means that if you play Overwatch, you share your main with 869565 other people.
Hey so hate to burst your bubble but that's not necessarily true. What it means, is that there exists at least one character who is shared by 869565. That character need not necessarily be your main, you see ? It could be that every single person except you, plays widowmaker, and you play reinhardt. In this case widowmaker is the category that satisfies the 'at least 869565 players' requirement, but you are the only reinhardt player in the world !
Started watching, my guess is will involve intermediate value theorem, now to continue watching
Ohhh, even simpler method, plain ol brute force with over estimations, I like it!
I have seen someone use the pigeon hole principle to explain computer memory management.
It was a way to check to see if there is more data than hard drive sectors, roughly.
So is the video title question gonna be answered?
Nice, a glider on the elevator.
Correction: There are at least 23,272 New Yorkers who share the same birthday on some day of the year given the population number of 8.5 million. The 366th day only occurs once every four years.
thank you that was amazing
Easy question even before reasoning : YES, skin-heads :P.
was that theorem Dirichlet proved the density of the rationals in the reals, or a more general case of that? It seems to be a more general case...
I find it hard to have counterintuitive examples of the pigeonhole principle. It is a good tool for estimating
Thank you
Regarding the last example. If one of them loses a hair and is kicked out that person is put into another box.
That shrinks the first box the person was in while growing the new one.
It is therefore possible that a person leaving one group, makes the new one 'largest' and exclusive. As the remaining original group is no longer part of the largest, one interpretation is that all members were kicked out and replaced except the one whom lost hair, which remained in the 'largest/exclusive' group.
@6:02 My favorite dots don't lie both on the same equator.
misium you define the equator for your exact two point. Spheres don't necessarily have fixed axes...
6:00 ish, it doesn't prove all cases, but if 4 of them form a tetrahedron, the fifth will always be placed in a hemisphere containing exactly 3 points already
Her hair is so fancy :D
You can answer "yes" without any math: alopecia universalis. Bonus fact: if you join this club, it's unlikely you'll ever get kicked out.
Yes, it's true. And clever reasoning -- mathematicians are always finding the special cases.
But even if you exclude people with no hair, the analysis still works. :)
I heard once the story that Gauss, as a young boy, was going with his father through the forest. He asked his father if two trees in that forest had the same number of leaves.. to which the father answered: "only God could know that!" But the young Gauss said "if the number of trees in this forest is larger than the number of leaves of the thickest tree, there must exist two trees with the same number of leaves"... It looks like the pigeon hole principle has bee discovered spontaneously by many thinkers throughout history
Gotta love that furry cylinder
What? Why aren't new yorkers finding out what day the most people share a birthday and throwing a city wide bday party?!
Keep it going!
Best channel
If you get five of your friends to club together to buy a peanut from you for 10 000$, there's at least one pigeon among them.
Ramsey theory is a sort of generalization of the pigeonhole principle, in the sense that if you take an "object" large enough (e.g. enough pigeons) and you divide it to finitely many parts (e.g. holes), then one of these parts will contain an object of the same "type". In the pigeonhole principle if you take a lot of pigeons (n) and you divide them into d holes, then you have at least one hole with "a lot" (n/d) pigeons. The standard Ramsey theory on graphs says that if you color a big enough full graph by finitely many color, then at least one of the induced monochromatic subgraphs (i.e. edges of the same color) will contain a big enough full graph. You also have results like if you color by d colors a long enough arithmetic progression (for example 1,2,...,N with N big compared to d), then at least one of these colors will contain a long arithmetic progression (this theorem is called Van der Waerden's theorem, or its stronger form Szemerédi's theorem).
I love this woman.
Such high hopes for this new channel…
And then you measure things in inches.
Sir, you have just won the Internet today.
Typical physicist’s problem. A mathematician does not care.
shomolya
Scientists in general would care. Not just physicists lol.
Well, they wouldn't for this particular case, but you know...
Roman Odaisky it's cause they are entertaining a widely American audience
This show is run by PBS, a US-based national broadcasting service.
Is this related to the Kochen-Specker theorem as an application in infinite sets? Basically it demonstrates it's impossible to assign quantum spin values before measurement because the number of points required exceeds the number of points in the surface of a sphere. It implies that either the property did not physically exist before measurement (no hidden variables) or the property value is dependent on the measurement context (no meaning to the counter-factual). Either is mind-blowing.
Maybe like space time do challenge questions and them each week share the results from fans? That that could satisfy the urge for proof and drive some good engagement:)
When I jump on a train or bus, all the seats will be filled by single passengers before I have to sit near an occupied seat (assuming seats are configures in pairs).
Love the show
I'm just not sure why you remind me so much of Matt (PBS Space Time).. Related somehow?
it's the Elbows-in body posture.
They have a similar rhythm and cadence of speech as well. Perhaps they share at least some of the same writing advisors?
they're both PBS related ...
Mathematicians always be like "that's cute and all, but can you [...]?"
It is estimated that 100 billion humans have lived throughout history. Given that there is no instance of a human living past 130 years, that gives 4.1 billion possible lifetimes measured in seconds. That must mean 24 people had to have lived for the same amount of time _to the second_. Out of these 24 people, there is a 54% chance that two people share the same death date.
That means it is likely that at some point in the past, two people died on the same date having lived for the exact same amount of time. Neat.
Anthony Khodanian Identical twins dying in a car crash.
+anticorncob6 The twins wouldn't die at exactly the same second unless they were both squashed into Jello or something. But even then, they weren't born at the same time, at least according to their birth certificates. I think life begins at conception but don't get me started on that.
I'm sorry, how did you get the 54%?
Pigeon holes and hash collisions
Sphere with 5 points. 1st problem in Putnam 2003
Actually it was Problem 2 of Putnam 2002: kskedlaya.org/putnam-archive/2002.pdf
Close enough = within a very small epsilon ;)
Was I the only one who spotted a Conway's glider on 4:46?
My favourite of this type of arguments is probably: If you have n objects and you fill all n categories with them, then there is exactly one object in every category (and vice versa, if you fill n objects into n categories so that there is only one object per category, then you filled every category)
If a show has 28 roles, but there's only 4 actors, at least one of them plays 7 roles.
His name is probably Billy West.
Speaking of hair! Lovin' yours ;)
It's interesting how this combines with the birthday problem. If a group has 70 people, there is a 99.9% probability that at least 2 of them share a birthday, but you still need 296 more people to reach 100% probability.
Hi! You remeber my last comment, on the infinite infinities? This is my wildest usage of the pidgon hole principle! I know there are at least infinite number of lowest rate of infinities, one the 2D graph.
My god, I am bright today!!!
what about DNA? would we out number the possible DNA combinations?
This video has 64,024 views (as of this comment) and it is 515 seconds long, which means that at least 127 people have stopped watching at the exact same second (hopefully the last!)
7:30 .. That said, would be nice to see your explination of the birtday paradox :)
[> 50% chance that 2 random ppl out of a group of 25 share the same birthday]
Similar to hair problem: are there more than one tree having the same number of leafs in a forest? (yes, if # of tree > Max(# of leafs on each tree).)
would like to rename this the Wookiee question, because now I want to see two equally number of haired Wookiees in a room.