PIGEON HOLE PRINCIPLE

The Pigeonhole Principle, also known as Dirichlet's principle or box principle, states that if you have n-1 holes and n pigeons, then there will be a scenario when one hole contains at least 2 pigeons. This principle is commonly used to prove a certain property will be met whenever we have greater than a certain number of instances of some event. We approach the problem by identifying what object is the pigeon and what object is the pigeonhole. 

 

Example: Suppose there were 4 ice-cream cones and 3 girls, Is it possible to guarantee that one of these three girls will recieve two ice-cream cones?

​

​

​

​

​

​

​

​

​

​

​

​

Explanation: Since there are n ice cream cones (4) and n-1 girls (3), then there is such a scenario where one of the girls will receive 2 ice-cream cones

Question: Suppose a box contains 28 red balls, 20 green balls, 19 yellow balls, 13 blue balls, 11 whites balls, and 9 black balls. What is the minimum number of balls that must be drawn from the box without replacement to guarantee that at least 15 balls of a single color will be drawn? (2019 AMC12 A #3)

​

Answer: 76

​

Explanation: In the worst case scenario, we could have chosen 14 red balls 14 green balls, 14 yellow balls, 13 blue balls, 11 white balls, and 9 black balls. 14+14+14+13+11+9 = 75, meaning we must pick 76 balls to guarantee there are at least 15 balls of a single color. In this situation, the pigeonholes are the three remaining colors we can choose from (red, green, and yellow) and the pigeons are the balls.