Contest Pigeons!

(This is a talk I gave for the Canadian IMO team at their 2014 winter camp at York University on Jan 3, 2014.)

The pigeonhole principle is a remarkable combinatorial theorem that looks silly and obvious, but turns out to be quite powerful and useful, especially in the context of contest problem solving. I’m going to present a couple of statements of the pigeonhole principle, then I’ll give some broad applications of it. I’ll end off with a list of problems.

The Statements

We start off with the most basic statement of the Pigeonhole Principle:

(BPHP) For $N$ a positive natural number (think number of pigeonholes) if $N+1$ (or more) pigeons are each put in a pigeonhole, THEN there must be at least one of the pigeonholes that has at least 2 pigeons in it.

Example 1. Say you ate 8 pieces of cake last week. Then there must have been a day where you ate 2 pieces of cake. (Assuming you ate whole pieces of cake.) Here the ‘7 days of the week’ are the pigeonholes and the ‘8 pieces of cake’ are the pigeons.

Eating 8 pieces of cake in a week is not good for you.

Example 2. There are two people in Toronto that have the same number of hairs on their (respective) heads. First some quick facts: A person has less than 250 000 hairs on their head (average is about ~100 000), and there are ~ 2.5 million people in Toronto. So to each person in Toronto we associate the number of hairs on their head, and the BPHP tells us that there are at least 2 people with the same number of hairs. (This example was inspired by Presh Talwalkar’s example.)

Notice that the BPHP doesn’t tell us anything about which hole gets two pigeons, it just tells us that there is such a hole. In the second example we don’t know anything about which two people have the same number of hairs. These types of theorems are sometimes called ‘existential theorems’ because they prove that something exists but they don’t provide a method for finding what we’re looking for. This can be a good thing though! We have given up some precision for power.

Expanding on the BPHP we can get better estimates on our final declaration about how many pigeons are in one of the holes. Before I state the more general PHP, here’s an example.

Example 3. If you ate 22 grapes last week, then there was a day where you ate at least 4 grapes.

Bacchus with Attendant Putti by Baldassarre Franceschini c. 1670

Stating this in a general way we have:

(GPHP) If we have $N$ pigeonholes and at least $N \cdot K + 1$ pigeons each in a pigeonhole, THEN there is a pigeonhole with at least $K+1$ pigeons in it.

Example 4. If 27 Canadians show up to a math contest, at least 3 of them will be from the same province or territory (remembering that there are 10 provinces and 3 territories).

The GPHP can be stated in an even more general way which turns out to be quite useful. This Average PHP was stated by Dijkstra (although it must certainly have been stated before):

(APHP) The maximum value of a function is at least its average.

This is really a restatement of the GPHP but the advantage is that it no longer references ‘pigeons’ and ‘pigeonholes’ (or ‘objects’ and ‘boxes’).

Example Problems

I’m going to list 5 example problems that you can look over and think about, then I will post solutions below in the next section.

EP1. For any subset $A \subseteq \{1,2,3,4,5,6,7,8,9,10,11\}$ with 6 elements, there are two different elements $a,b \in A$ such that $a + b = 11$ . (Inspired by Gary MacGillivray’s writeup.)

EP2. Given a set $A \subseteq \{1, 2, ..., 100\}$ of ten integers. Prove that it is possible to select two disjoint non-empty subsets of $A$ , $S$ and $T$ , whose members have the same sum. (Problem 22 from CTK.)

EP3. In a gymnasium with 2014 people, there are at least two people that have the same number of friends in the room. (Note if Mike is a friend of Janet, then Janet is a friend of Mike. Also, no person is a friend of themselves.) (Problem from folklore.)

EP4. Mike solved 45 Project Euler problems in November, and he solved at least one a day. Show that there was a streak of days where he solved exactly 14 problems. (Problem from folklore.)

EP5. Let $P$ be a non-degenerate pentagon whose vertices lie on the integer lattice. Show that there is an integer lattice point in the interior of $P$ . (This appeared on a Putnam Contest, but I don’t know which one.)

Example Problem Solutions

EP1. For any subset $A \subseteq \{1,2,3,4,5,6,7,8,9,10,11\}$ with 6 elements, there are elements (possibly only one element) of $A$ such that sum to 11.

SOL. If $A$ contains the number 11, then we are finished, so suppose it doesn’t. Consider the pigeonholes: $\{1,10\},\{2,9\},\{3,8\},\{4,7\},\{5,6\}$ . Notice the elements of each pigeonhole sum to 11. Since $A$ has 6 elements, by the BPHP one of the pigeonholes contains two elements of $A$ , which must sum to 11.

Followup. Formulate a similar problem (with the appropriate size of $A$ , and length of $\{1,2, \ldots, n\}$ ) such that there is always a subset of $A$ with at least two elements that adds up to an odd number.

SOL. Note that the largest possible sum of elements of $A$ is $92 + 93 + \ldots + 99 + 100 = 864$ , and the smallest is $1$ . Thus there are at most $864$ possible sums for subsets of $A$ . However, there are $2^{10} - 1 = 1023$ ways of partitioning $A$ into two non-empty disjoint subsets. So by the BPHP there are two different, non-empty subsets of $A$ , named $S$ and $T$ , such that they have the same sum.

We are not finished yet though, because $S$ and $T$ need not be disjoint. A little bit of thinking quickly reveals that removing the common intersection of $S$ and $T$ from each set yields the desired pair.

Followup. Prove that this can also be done with $A$ having size 9.

EP3. In a gymnasium with 2014 people, there are at least two people that have the same number of friends in the room.

SOL. There are two cases to consider: (1) everyone has at least 1 friend, and (2) there is someone with no friends.

(1) Here each person has between 1 and 2013 friends. To each person we associate their number of friends. By the BPHP there will be two people with the same number of friends.

(2) Now everyone has between 0 and 2012 friends. So again by the BPHP there are two people with the same number of friends.

Followup. Ten baseball teams are entered in a round-robin touranment (meaning that every team plays every other team exactly once) in which ties are not allowed. Prove that if no team loses all of its games, then some two teams finish the tournament with the same number of wins. (Taken from Gary MacGillivray’s handout.)

EP4. Mike solved 45 project Euler problems in November, and he solved at least one a day. Show that there was a streak of days where he solved exactly 14 problems.

SOL. There is a clever idea hidden in here that is also useful for efficient coding. If you have a list of 30 things (like amount of problems solved in a day) and need to keep track of the sum of consecutive things you only need to keep track of sums starting from the beginning.

e.g. $d_1, d_1 + d_2, d_1 + d_2 + d_3, \ldots, d_1 + d_2 + \ldots + d_{30}$

Now if $d_i$ is the amount of problems solved on day $i$ and $s_i = d_1 + \ldots + d_i$ , then to figure out how many problems solved between day $i$ and day $j$ we only need to look at $s_j - s_i = d_{i+1} + \ldots + d_{j}$ .

Back to our problem, we need to find $i,j$ between 1 and 30 so that $s_j - s_i = 14$ . Or in other words, $s_j = s_i + 14$ .

Notice first that since Mike solves at least one problem a day, we have:
$\displaystyle 1 \leq s_1 < s_2 < \ldots < s_{30} = 45$
and so also,
$\displaystyle 15 \leq s_1 +14 < s_2 + 14 < \ldots < s_{30} + 14 = 59$

Now, we notice that the 60 numbers $s_1, s_2, \ldots, s_{30}, s_1 + 14, s_2 + 14, \ldots, s_{30} + 14$ must all be between 1 and $59$ . By the BPHP there must be two that are equal. Our previous inequalities tell us that it must be one of the $s_i$ and one the $s_j + 14$ . As desired.

EP5. Let $P$ be a non-degenerate, convex pentagon whose vertices lie on the integer lattice. Show that there is an integer lattice point in the interior of $P$ .

SOL. Suppose this isn’t true, and take $P$ to be a counterexample with a minimal number of integer lattice points in $P$ . (We could try taking one of minimal area, but it isn’t immediately clear that such a thing should exist.) We will show that there is a related pentagon $P'$ that has smaller number of integer lattice points inside itself.

We are going to put the five vertices into four holes based on the parity of the coordinates. That is, the holes are {Even,Even}, {Odd, Odd}, {Even, Odd} and {Odd, Even}. By the BPHP there are two vertices $a$ and $b$ with the same “parity pair” (above). This tells us that their midpoint $m$ is again an integer lattice point. By convexity, it is inside $P$ , by our assumption of $P$ being a counterexample, $m$ is on the boundary of $P$ , and by our assumption of $P$ being non-degenerate that means that $a$ and $b$ are adjacent.

Thus if $P$ has vertices $a,b,c,d,e$ the related pentagon $P'$ given by $m,b,c,d,e$ will be a convex, non-degenerate pentagon containing fewer integer lattice points (namely we removed $a$ ).

References and Resources

This is a writeup by Gary Macgillivray. It is very clear and contains very well thought out examples. LINK

16 fun applications of the Pigeonhole Principle by Presh Talwalkar. A list of some pretty cure real world ‘applications’ of the pigeonhole principle. LINK

Cut the Knot’s write-up of the pigeonhole principle is fantastic. The list of problems is also amazing! LINK

A transcription of E. Dijkstra’s thoughts on the Pigeonhole principle. LINK

The Red Book of Mathematical Problems by Kenneth S. Willians and Kenneth Hardy contains some nice Putnam level contest problems. LINK

Contest Pigeons!

The Statements

Example Problems

Example Problem Solutions

Other Problems

References and Resources

One thought on “Contest Pigeons!”

The Statements

Example Problems

Example Problem Solutions

Other Problems

References and Resources

Share this:

Like this:

Related

One thought on “Contest Pigeons!”