Return to my Puzzle pages
Go to
my home page
© Copyright 2002, Jim Loy
1. Let's say that you have a drawer full of socks, 20 red socks (all identical) and 12 blue socks, and it is dark in the room. How many socks should you grab, to assure that you have at least one matching pair? The answer is below.
2. You have a draw containing 20 red socks, 12 blue socks, and 8 green socks. How many socks should you grab, to assure that you have at least one matching pair?
3. You have 10 pairs of shoes (20 shoes) in your closet, all identical! Again it is dark. And maybe your hands are numb so you can't tell if the shoes that you grab are right or left handed (footed). How may shoes should you grab to make sure you have at least one shoe for each foot?
4. In a city of 2 million people, no one has more than 1.5 million hairs on his/her head. Can you show that at least two people in the city have exactly the same number of hairs on their heads?
Answers:
1. You have 20 red socks and 12 blue socks. You need grab only three socks, and you will have at least two socks of one of the two colors.
2. With three colors, you should grab four socks.
3. With 10 pairs of shoes, you should grab 11 shoes to make sure that you have at least one shoe for each foot.
Comments: The first three puzzles are so simple that people sometimes get them wrong on the first guess. They are examples of the "pigeon-hole principle" (also called Dirichlet's box principle) in mathematics. It states that given n boxes containing m objects (with m>n) then at least one box must contain more than one object. This may seem obvious, but it leads to some important results in number theory. It can be shown that this principle is equivalent to mathematical induction (see Dividing The Plane). The idea leads directly to the solution of question #4, below.
4. In a city of 2 million people, no one has more than 1.5 million hairs on his/her head. Can you show that at least two people in the city have exactly the same number of hairs on their heads? Let's pretend that we have 1.5 million boxes +1. These are all of the possible numbers of hairs that these people may have. Well, if one person has 1,234,567 hairs on his/her head, then we can put his/her name in box number 1,234,567. There are only 1.5 million boxes into which we are trying to put 2 million people's names. At least one box must contain two or more names.