Posts Tagged ‘counting’

Reflections of the implications of the Pigeonhole principle in our lives

February 17, 2008

Readability test scores for this post are as follows:

Flesch Reading Ease: 70.52
Flesch-Kincaid Grade Level: 7.00
Automated Readability Index: 7.00

For more info about readability tests, check out my post about those here.

Math is fun in my opinion. It has, for the longest time, including Science, been my favorite subject.

Anyway, this post is about a portion of mathematics which is more popularly known as the pigeon hole principle. The pigeonhole principle states that, given k+1 or more objects (k being any positive integer) which are to be placed on k number of holes, there is at least one hole which will contain two or more of the objects. Or to generalize the definition in a mathematical way:

if M objects are placed into j holes, M greater than or equal to j, then there is at least one hole containing at least k number of objects, where k is equal to the ceiling( M / j ) .

For example, if I have 12 pigeons to be placed into 11 pigeonholes, there will be at least one pigeonhole which will have 2 pigeons inside. This is so because the ceiling value k, the smallest integer value not less than (M / j) , is 2 since 12 divided by 11 is approximately 1.09 whose ceiling value k is equal to 2

“So what?”

you may say. What would possibly be in the pigeonhole principle that could interest me? Well, a lot actually, same as a lot of other seemingly ‘impractical’ mathematical theories for our every day lives.

1 If we take the upper limit on the average number of hair on the human head (nice alliteration) to be about 150,000, and say a given city has a population size of 500,000, there would be at least 4 people with the same number of hair on their heads. This happened because taking the population size (500,000) as the pigeons and the maximum possible number of hair on the human head (150,000) as the pigeonholes, k is found to be equal to 4. Isn’t that amazing to know? (okay sorry, I know not everyone will find that interesting).

2 Take a pizza party for example: If I were to treat four of my friends so that the five of us will eat a pizza pie of 12 slices, at least one among us will be eating 3 pizzas, while the rest only eat 2. This assumes of course that everyone eats a whole slice of pizza. Now isn’t that worth knowing at times like this? (^)__(^)

3 Another example is when you want to get say, candies from those vending machines which shows you their contents but you can’t pick any flavor in particular (i.e. the machine gives the candy to you at random). Say you can see that there are only two candy flavors left: orange and lemon, and there are 12 of each. You will know (using the pigeonhole principle) that you can get at least 2 candies of the same flavor for sure by buying (not 13 candies) at least 3 candies only! This is because in the event that the first 2 candies you get are of different flavors, you know for certain that the third one will be one of the 2 flavors, giving you at least 2 candies of the same flavor!

However, if you want at least 2 of a specific flavor, say, lemon flavor, it becomes a bit different: you need to get at least 14 candies to be sure that you get 2 lemon flavored candies.

4 Say you have a shop/store with (doesn’t have to be the exact number, since using the principle will still give you the correct answer) 50 aisles, 85 horizontal locations on each aisle, and 5 shelves. The products you sell are stored in bins on horizontal locations on the shelves of each aisle. What is the least number of products you would buy to ensure that at least 2 products are stored in the same bin? That is, based on the above definition, what should be M so that for j = 85 x 50 x 5 = 21250, k = 2 ? Surely enough, M would be equal to 21251 since taking the ceiling of 21251 / 21250 would be equal to 2.

5 If you collect/put together 13 people randomly (or even purposefully), by the pigeonhole principle, there are at least 2 people (pigeons) from that group who were born on the same month, since there are only 12 months (pigeonholes). And, much more obvious, is that among a group of 8 people (randomly/non-randomly chosen), at least two among them were born on the same day.

The important thing to remember here is to figure out which among the objects you’re dealing with is the pigeon and which is the pigeonhole.

There you go! There are tons more of examples on the daily applications of the pigeonhole principle, from computer networks, to train stations, to supermarkets, to art classes, etc. Anybody disagrees with me? (^)__(^)

Btw, comments/suggestions/questions/corrections are welcome, as long as they come in a calm and ruly way.