Saturday, June 10, 2017

The Pigeonhole Principle

The pigeonhole principle states that if a group of pigeons flies into a set of pigeonholes, and there are more pigeons than pigeonholes, then there must be at least one pigeonhole with two pigeons in it. More generally, if k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects. Despite its seeming simplicity (perhaps obviousness), it can be used to solve a surprising range of problems in probability, number theory, and computer science, just to name a few. See if you can use it to solve the following three problems.

  1. (Warm up) A drawer contains a dozen blue socks and a dozen black socks, all unmatched. If the room is dark, how many socks do you have to take out to be sure you have a matching pair?
  2. Prove that there are at least two people in Tokyo with exactly the same number of hairs on their heads.
  3. Prove that if five distinct integers are selected from the numbers 1 through 8, there must be at least one pair with a sum equal to 9.

Click below to see the answers.

No comments: