Lottery Confusion: The Pigeonhole Principle

Example 1. Annemarie is cutting out coupons for her favorite restaurant, Adelinas Ballhaus, from the newspaper. Coupon denominations are 5 thaler, 10 thaler, 20 thaler, 50 thaler and 100 thaler. How many coupons must Annemarie cut out to be sure of getting two coupons of the same denomination?

Solution. What is the worst-case scenario? Annemarie can get each of the 5 denominations after 5 cuts. But the sixth cut guarantees a repetition of one of the denominations. And that's the pigeonhole principle, a deceitfully obvious, yet incredibly useful combinatorial technique that can be employed to solve multitudes of advanced problems.

If there are more pigeons than pigeonholes, then one of the pigeonholes contains at least two pigeons.

Warm-Up

Example 2. How many integers from 1 through 1000 must you pick in order to be certain of getting one that is divisible by 5?

Solution. There are 200 integers between 1 and 1000 that are divisible by 5. So, there are 800 that are not. The worst-case scenario? Your first 800 picks are the numbers that are not divisible by 5. Now it is guaranteed that after 800+1 picks you can be sure of having a multiple of 5.

Example 3. An urn contains 10 red balls, 10 green balls and 10 blue balls. How many fruits should you choose to be certain of obtaining 5 balls of the same color?

Solution. It is possible that we have 4 balls of each color after 12 picks. On the thirteenth pick we can be sure of getting 5 balls of the same color, and this color is the color of the thirteenth ball.

Try this one yourself!

There are n married couples. How many of the 2n people must be selected in order to guarantee that one has selected a married couple?

Generalized Version

If you have n pigeons and I pigeonholes then at least one of the holes contains at least [n/k] pigeons.

The previous statement is simply a corollary of the generalized statement where n>k and [n/k] is therefore at least 2.

Note: [x] denotes the ceiling function, the smallest integer that is greater than or equal to x.

To illustrate,

Example 4. 41 rooks are placed on a 10x10 chessboard. Prove that there exist 5 rooks that do not attack each other.

Solution. The problem asks us to find 5 rooks that are situated on different rows and different columns. We have 10 rows and 41 rooks. From the pigeonhole principle it follows that there must be at least [41/10] = 5 rooks in one row. Now it makes sense to find a rook in another row in a different column. How do we do that?

What do you notice about the other rows? We have identified one row with at least 5 rooks. At most, it can have 10 rooks. Throw this row out of the picture!

We have 31 rooks and 9 rows left. One of these rows must contain at least [31/9] = 4 rooks. Continue pigeonholing!

Problems in many fields of mathematics can be solved, or at least greatly simplified via the pigeonhole principle.

Let's start with the rook on the row that contains at least one rook. Now we can pick a rook from the row that has at least two rooks. At least one of them is not in the same row as the first rook. Repeat for the third, fourth and fifth rows, and we have five rooks that are on different rows and different columns!

"A method is an idea applied twice" - George Polya

Many problems can be solved by repeated application of the generalized pigeonhole principle. Here's a general outline for solving problems of this type:

Identify the use of the pigeonhole principle in the problem.
Identify the pigeons and the pigeonholes.
Does using the pigeonhole principle help?
Does the problem require repeated application of the pigeonhole principle? If not, what other strategies can you think of? Utilizing the pigeonhole principle in proofs and puzzles is often a preliminary step following which there is much work to be done. That said, the pigeonhole principle serves an important purpose: to extract information.

The second step is often the crux of problems utilizing the pigeonhole principle, and sometimes the most deceptive step.

Example 5. Prove that there exist 15 integers between 1 and 100 such that the difference between any two integers is divisible by 7.

Solution. This problem is on the confusing side. Instead of the numbers, we can consider the pigeonholes to be the remainders after division of the differences by 7. It follows that at least one pigeonhole has [100/7]= 15 numbers. The difference between any 2 of these 15 numbers leaves the same remainder when divided by 7. So the difference between any 2 numbers in this particular set is always a multiple of 7.

Problems in many fields of mathematics can be solved, or at least greatly simplified via the pigeonhole principle.

Number Theory

Prove that there exists a power of three which ends with the digits 001 in base 10.

Geometry

Prove that if five points are randomly chosen on a unit square there exist at least two points such that the square of the distance between them is less than 1/2.

Brain Teaser

Now that you have a theoretical background in the pigeonhole principle, here's a lovely problem:

Integers 1 through 12 are are divided into 4 groups. Prove that the products of the numbers in at least one group is greater than 144.

You don't actually need the pigeonhole principle to prove this. The product of all the numbers is 12! = 479001600. If no group had a product greater than 144 then the maximum possible product of all the numbers would be 144 x 144 x 144 x 144= 429981696. Since 429981696 < 479001600, it follows that the product of the elements of at least one group is greater than 144.

That said, I leave you with a final challenge. Can you solve this problem using the pigeonhole principle?

If you liked this article, let me know using the contact forms below! Please feel free to email me at arushee.tj@gmail.com with any questions, problems, solutions or suggestions for future blog posts. Until next time :D