It's the weekend, so we thought of sharing something recreationally interesting, and interestingly recreational! The above headline might sound like something absurdly hard to crack using conventional mathematics, to most of us anyway, but the actual solution is so laughingly easy that even a kindergartner can understand and use it. This is something commonly called the pigeonhole principle.
The actual principle is simple - when m items are put into n containers where m>n (m and n both being natural numbers, of course), at least one container must contain 2 or more items.
The actual name of this simple axiom results from a story revolving around pigeons. Suppose you have 10 pigeons, and 9 holes inside which they can live. So, when you place 1 pigeon inside 1 hole, at last you'll have 2 pigeons left to be put inside a single hole. Likewise, you can place all the 10 pigeons inside the first hole, and then at least one hole (the first hole) has more than 1 pigeons.
That's it! A bit more sophisticated way of stating it is:
"If more than n objects are distributed into a set of n compartments, some compartment must receive [ for "must receive" read "receives", EWD] more than one of the objects."
Why and how does it matter?
The beauty of this laughingly simple axiom is that, we can find its use pretty much everywhere, and yet, despite the original reason being so obvious, the results obtained by applying the principle are really wonderful.
Let us discuss a few examples.
Find me two people with the same hair-count
Ok, so let's say you live in a city with 5 million residents. Now, when you're asked this question, you immediately laugh it away by calling it impossible. And anyway it would be impractical to actually count the hair number on the head of each person, right?
The solution is simple - the average number of hairs on human head ranges between 90,000 and 1,50,000 (source: http://bionumbers.hms.harvard.edu/bionumber.aspx?&id=101509 ). So, let us take the first 1,50,000 people from your city.
Let person <1> have 0 hairs, or total baldness.
Let person <2> have 1 hair,
Let person <3> have 2 hairs
...
Let person <1,50,001> have 1,50,000 hairs.
So, what would be the hair-count on the head of person <1,50,002>? Certainly something between 0 and 1,50,000! So, there must be at least 1 person in the original 1,50,001 people considered, who has the exact same hair-count!
People with the same birthday
Ok, so in a party, say there are 367 people. Now, since the maximum number of days in a year is 366, there must be at least 2 people with the exact same birthday! It's wonderful to see such a simple principle in effect in this case as well.
Sophisticated applications: lossless data compression can't guarantee that all data input files are compressed
Yes! This simple principle finds use in computing as well. As we know, lossless compression, as opposed to lossy compression, doesn't compromise with quality.
Let us see how it works.
Step 1: Assume that each file is represented as a string of bits of some arbitrary length.
Step 2: Suppose that there is a compression algorithm that transforms every file into a distinct shorter file. (If the output files are not all distinct, the compression cannot be reversed without losing some data).
Step 3: Consider the set of all files of length at most N bits. This set has 1 + 2 + 4 + ... + 2N = 2^N+1-1 members, if we include the zero-length file.
Step 4: Now consider the set of all files of length at most N-1 bits. There are 1 + 2 + 4 + ... + 2N-1 = 2^N-1 such files, if we include the zero-length file.
Step 5: But this is smaller than 2^N+1-1. We cannot map all the members of the larger set uniquely into the members of the smaller set.
Step 6: This contradiction implies that our original hypothesis (that the compression function makes all files smaller) must be untrue.
Naturally, however good and advanced the compression algorithm be, if it's lossless then it makes some files shorter must necessarily make some files longer!
Applications in basic number theory
OK, so there's no way you can pick 5 distinct numbers from 1 to 8 and 2 of your numbers don't add up to 9.
Why? Because 1-8 contains 8 whole numbers, and there are 4 pairs of numbers in [ 1 , 8 ] that add to form 9. These are:
1 + 8 = 9
2 + 7 = 9
3 + 6 = 9
4 + 5 = 9
Now, these 4 pairs cover all the possible numbers. So, when you're asked to select any 5 numbers, let us say that your first four choices don't belong to any of these pairs, and don't add to form 9. BUT, the fifth number will HAVE TO belong to any of these four pairs, and as such, with one of the numbers you've previously selected, it will add to form 9!
References and further reading
http://www.fact-index.com/l/lo/lossless_data_compression.html
(lossless data compression)
Image courtesy: Wikimedia
No comments:
Post a Comment