Here is the full text and summary of Madhav Anand Menon’s talk titled “The Profound Applications of The Pigeonhole Principle” at TEDxHECMontréal conference.
Listen to the audio version here:
TRANSCRIPT:
Mathematics, rightly viewed, possesses not only truth but supreme beauty. This is the quote that has resonated with me ever since I started my love for mathematics in the 8th grade. But maths is known for being intimidating, and it makes sense that it is. After all, who wants to bother unpacking these seemingly random and arbitrary symbols that somehow have a deeper meaning embedded within them?
Yet, amidst the chaos of the alphas, betas, and gammas, lie profound and mystical ideas that have larger implications for the world around us.
Hello, my name is Madhav Menon, and today I’ll be taking you on a tour of the Pigeonhole Principle, an idea in mathematics that is so simple and intuitive, you might end up questioning its validity as a mathematical principle. I don’t like to beat around the bush, so here’s the Pigeonhole Principle in mathematical notation.
But this might bring up traumatic memories for some of you, and some of you might decide to zone out for the rest of this talk. So let’s break down this convoluted mess of m’s and n’s, and get down to what the Pigeonhole Principle really talks about. Sorting pigeons into pigeonholes.
Let’s say I have five pigeons here, and I want to place them into four pigeonholes, or nests. I could take one pigeon and place them into one nest at a time. There goes my first pigeon, my second, my third, and my fourth. But once I get to four pigeons, notice that all of my nests are completely filled, yet I still have one more pigeon left.
Therefore, I have no other choice but to force this pigeon to share a pigeonhole. This is exactly what the Pigeonhole Principle talks about. If I have a certain number of items to be placed in a certain number of containers, but if I have more items than containers, it turns out that at least one container is going to have multiple items. I don’t explicitly have to be talking about pigeons in pigeonholes. I could be talking about anything from pencils to pencil pouches, socks to drawers, and even the weird example of strands of hair in people’s head, something I’ll be getting into in a bit.
What’s also neat about the Pigeonhole Principle is that I can extrapolate it to as many items in containers as we want. As long as I have more items in containers, I can use the Pigeonhole Principle.
Here we have nine pigeons and four nests. And so if I place one pigeon into one nest at a time, and if I group together the surplus pigeons, I might get something that looks like this. Since we had more items than containers, the Pigeonhole Principle said that at least one container must have multiple pigeons. And over here, all of our containers have more than one pigeon.
I want to digress a bit and introduce a mathematical concept. But trust me, it’s very simple, and it’s called the ceiling function. Without it, it would be hard to get into the nitty-gritties of the Pigeonhole Principle. The ceiling function is very simple and is noted by these weird-looking brackets that point towards the ceiling. Effectively, all it does is take in a number and give you an output.
The output is another number that is the nearest whole number greater than or equal to the number you gave it. A hundred is already a whole number, and therefore the ceiling function of 100 is just 100. Pi is approximately 3.14, and therefore the nearest whole number greater than or equal to 3.14 is 4. And so the ceiling function of pi is 4.
Now why did I bother introducing this to you? The reason is that we can actually formalize the Pigeonhole Principle a bit. If I know exactly how many items in containers I have, I will get an idea of approximately how many items there will be in a given container.
Let’s rephrase the Pigeonhole Principle a bit. It looks pretty complicated, but effectively if I have a certain number of items to be placed in a certain number of containers, and if I have more items in containers, at least one container is going to hold the ceiling function of the number of items divided by the number of containers. Sounds confusing? Don’t worry. We’ll illustrate it with an example.
This formalization came about by the French mathematician Jean Leurechon in a book he wrote in 1622. However, it’s now more widely attributed to the famous German mathematician Peter Gustav Lejeune Dirichlet. The beauty of mathematics comes from how you derive principles and theorems from the basic axioms that govern mathematics.
But this talk is not about deriving the Pigeonhole Principle, so I want you to take this for granted. Instead, we’re going to look at how such a simple idea of placing items into containers can be used to understand some pretty important ideas around us.
Let’s go ahead and illustrate the Pigeonhole Principle with our previous example. Here, we had nine pigeons, or nine items, and four containers. And therefore, one container is going to hold at least the ceiling function of 9 divided by 4. 9 divided by 4 is 2.25. And therefore, the Pigeonhole Principle states that at least one container is going to hold the ceiling function of 2.25, which is 3.
Over here, you can see that one container holds exactly three pigeons. Holding exactly three pigeons and holding at least three pigeons are kind of different concepts. So how do we reconcile the two? The thing about the Pigeonhole Principle is that it does not actually take into account different configurations. These are all completely valid as well.
Regardless of which configuration you choose, at least one container or at least one nest has at least three pigeons. And this is the idea of the Pigeonhole Principle, sorting items into containers.
But now that we have a rudimentary understanding of what the Pigeonhole Principle is, why do we need such an intuitive and common sense idea?
The interesting thing about the Pigeonhole Principle is that it can be used to answer some pretty trivial questions that no one’s going to bother asking at all. But at the same time, it can help us understand some stuff in mathematics and computer science that we deal with on a daily basis. Let’s start off with the trivial first.
We have this question. How many people in Chennai city have the same number of strands of hair on their head? This seems pretty difficult, but let’s try and get some numbers. If I go ahead and look at the population of Chennai, according to the 2011 census, the population was 6,407,000. And according to the Healthline website, the upper bound for the average number of hair follicles on a person’s head is approximately 100,000. Now this idea of strands of hair and people’s head was how Leurechon introduced the idea of the Pigeonhole Principle as well, although he did not use Chennai city.
So how do we use the seemingly innocuous idea of sorting items into containers and apply them to strands of hair and people’s head? We can, if we think outside of the box a bit, imagine that our containers are simply the number of strands of hair. For example, one container could hold all the people with just one strand of hair on the head. The second container, all the people with two strands of hair, so on and so forth.
And if we think about our items as the number of people, and if we place them according to the number of strands of hair on our head, we can effectively use the Pigeonhole Principle. Here, we have 100,000 containers, but we have 6,407,000 items. If we go ahead and apply the Pigeonhole Principle, we would get that there are approximately 65 people in Chennai, or there are at least 65 people in Chennai, with the same number of strands of hair on their head. But this is pretty useless, right?
Why do we care about the number of strands of hair on people’s head? And this number doesn’t really tell us anything about the actual number of strands of hair these 65 people have. So let’s look at something a bit more relevant in our day and age.
Let’s look at something in computer science, the idea of data compression. We’ve all dealt with data compression on a day-to-day basis. We have a really large file that we want to send to someone, but we just can’t because it’s too big. So we go ahead and compress that file and make it smaller so that we can send it to our friends and family.
It turns out that there are two types of compression. We have lossy compression and lossless compression. Lossy compression is where certain pieces of redundant information are completely taken away from the file. If we have a video, perhaps certain audio frequencies we can’t hear are removed. If we have an image, certain colors our eyes can’t perceive are removed as well. Effectively, lossy compression involves removing information.
Lossless compression, on the other hand, does not remove any information at all. Instead, lossless compression identifies underlying patterns within the data that we have, something called statistical redundancies, and it exploits these to make our files smaller. In fact, you can see that the frog that underwent lossless compression is not as blurry as the frog that underwent lossy compression. That’s because no information was really removed from it at all.
And so, if no information was removed, I should ideally be able to get back my original file since it’s still faithful to what the original file was. If I apply my compression algorithm to a file, I should be able to get a compressed file. But since no information was removed, if I decompress that file, I should be able to get my original file back again. This seems extremely ideal, right?
Imagine if I was sending some pretty important financial information to someone all the way at the other end of the world. I wouldn’t want any data lost, and therefore, I would want to use lossless compression. But unfortunately, our world is not ideal, and there are certain constraints. And the pigeonhole principle can be used to identify the certain constraints that we have with lossless compression.
But before that, another interlude. All the data we have in the world is stored as tiny ones and zeros, bits. Together, they can collectively be known as binary, a term you might be familiar with. The size of the file is simply dependent on the number of ones and zeros we have or the number of bits. For example, a two-bit file might look like this. The reason it’s a two-bit file is because we have two bits, two combinations of ones and zeros. And these are all the possible combinations we could have for a two-bit file.
But let’s say I want to compress this two-bit file into a one-bit file. There are only two possible one-bit files. I either have a zero and a one. And therefore, I’m effectively mapping four possible files to two files. How do we apply the pigeonhole principle?
If we once again think outside of the box and think of our one-bit files as the number of containers, while our two-bit files as the number of items, we’re effectively trying to sort four items to just two specific containers. And so if I apply the pigeonhole principle again, I get that there must be at least two files, two of these two-bit files that correspond to a single one-bit file.
Now, this violates lossless compression, because ideally, I should have a one-to-one mapping. I should have one specific two-bit file mapping to one specific one-bit file, so that I can get my original file. But if I have two of these files mapping to just one file, how can I get my original file? Therefore, the pigeonhole principle tells us that there are certain collisions when it comes to lossless compression. Effectively, lossless compression does not work for certain types of inputs.
And with the pigeonhole principle, we’ve been able to identify certain constraints in the tools that we as a human race have created. The pigeonhole principle is very simple. I’m simply trying to sort items into containers. It’s so intuitive, and it just makes so much sense, that perhaps it doesn’t need to be formalized as a mathematical principle.
Yet, it has its applications elsewhere, from it being used extensively in mathematical proofs to other fields of computer science, like data encryption and hashing. But how exactly do I go from such a small idea of sorting items into containers to having such a big impact on the way we deal with technology, the way we interact with it?
How do I bridge this divide? How do I bridge this gap? Sometimes, it’s all about identifying the pigeons and the pigeonholes. Thank you very much.
Want a summary of this talk? Here it is.
SUMMARY:
Madhav Anand Menon’s talk, “The Profound Applications of The Pigeonhole Principle,” simplifies complex mathematical concepts to make them accessible and relatable.
Menon begins by highlighting the beauty of mathematics, acknowledging that it can be intimidating due to its symbols and equations. He introduces the Pigeonhole Principle, a fundamental mathematical concept that’s both simple and profound. The Pigeonhole Principle is explained as a common-sense idea: if you have more items than containers to put them in, at least one container must hold multiple items. This concept is illustrated with the example of pigeons and pigeonholes, making it easy to grasp.
Menon introduces the ceiling function, a mathematical tool that helps formalize the Pigeonhole Principle in specific situations. It approximates how many items will be in a container when you know the number of items and containers.
He then dives into real-world applications. First, he playfully asks how many people in Chennai might have the same number of strands of hair on their heads. By treating strands of hair as containers and people as items, he demonstrates how the Pigeonhole Principle can estimate the answer.
Next, Menon explores data compression in computer science. He distinguishes between lossy and lossless compression, highlighting that lossless compression identifies patterns in data to make files smaller. However, he notes that there are constraints due to the Pigeonhole Principle, where certain inputs lead to collisions, making lossless compression impossible.
In conclusion, Menon emphasizes the power of the Pigeonhole Principle—a simple idea that has profound implications in mathematics, computer science, and everyday life. He encourages the audience to appreciate how basic mathematical principles can solve complex problems and influence technology. Ultimately, the talk makes complex math concepts accessible and relatable by connecting them to familiar scenarios.