Newyork Hair (Pigeonhole Principle) | Amazon Interview

You are visiting NYC when a man approaches you.
“Not counting bald people, I bet a hundred bucks that there are two people living in New York City with the same number of hairs on their heads,” he tells you.
“I’ll take that bet!” you say. You talk to the man for a minute, after which you realize you have lost the bet. What did the man say to prove his case?

 

 

 

 

 

Solution :

This is a classic example of the pigeonhole principle. The argument goes as
follows: assume that every non-bald person in New York City has a different
number of hairs on their head. Since there are about 9 million people living
in NYC, let's say 8 million of them aren't bald.

So 8 million people need to have different numbers of hairs on their head.
But on average, people only have about 100,000 hairs. So even if there was
someone with 1 hair, someone with 2 hairs, someone with 3 hairs, and so on,
all the way up to someone with 100,000 hairs, there are still 7,900,000 other
people who all need different numbers of hairs on their heads, and furthermore,
who all need MORE than 100,000 hairs on their head.

You can see that additionally, at least one person would need to have at least
8,000,000 hairs on their head, because there's no way to have 8,000,000 people
all have different numbers of hairs between 1 and 7,999,999. But someone having
8,000,000 is an essential impossibility (as is even having 1,000,000 hairs),
So there's no way this situation could be the case, where everyone has a different
number of hairs. Which means that at least two people have the same number of
hairs.

Leave a Reply

Your email address will not be published. Required fields are marked *

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |

*