10.5. Pigeon-Hole Principle

Try these first

1. 1.

   If you place 10 apples into 9 boxes, how many boxes will contain at least 2 apples?

   Hint

   Consider how many more apples there are than boxes.

2. 2.

   What happens if there are 7 pairs of gloves and only 5 pairs of gloves can be stored?

   Hint

   How many gloves do you have vs. storage space?

3. 3.

   If you have 20 items and only 15 containers, will at least one container have more than one item?

   • True
   • False

   Hint

   Think about the basic logic behind resource allocation.

4. 4.

   What is the minimum number of people needed to guarantee either 3 mutual friends or 3 mutual enemies?

   • 4
   • 5
   • 6

   Hint

   Review the principle's application in social dynamics.

5. 5.

   Prove that if you have 100 socks and you’re putting them into 80 drawers, at least one drawer must contain at least 2 socks.

   Hint

   Think about how drawers can be filled.

6. 6.

   If you collect rebounds from 15 basketball games and there are only 10 hoops to shoot at, show using a pigeon-hole approach that at least one hoop must have 2 rebounds.

   Hint

   Relate rebounds to the principle’s logic.