Some elegant applications of the Pigeonhole Principle

Reference: Discrete Mathematics and its Applications by Kenneth H. Rosen, Seventh Edition.

In many interesting applications of the pigeonhole principle, the objects to be placed in boxes must be chosen in a clever way. A few such applications will be described here.

Example 1:

During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.

Solution 1:

Let a_{j} be the number of games played on or before the jth day of the month. Then, a_{1}, a_{2}, \ldots, a_{30} is an increasing sequence of distinct positive integers, with 1 \leq a_{j} \leq 45. Moreover, a_{1}+14, a_{2}+14, \ldots, a_{30}+14 is also an increasing sequence of distinct positive integers, with 15 \leq a_{j} + 14 \leq 59.

The 60 positive integers a_{1}, a_{2}, \ldots, a_{30}, a_{1}+14, \ldots, a_{30}+14 are all less than or equal to 59. Hence, by the pigeonhole principle two of these integers are equal. Because the integers a_{j}, j=1, 2, \ldots, 30 are all distinct, there must be indices i and j with a_{i}=a_{j}+14. This means that exactly 14 games were played from day j+1 to i.

Example 2:

Show that among any n+1 positive integers not exceeding 2n there must be an integer that divides one of the other integers.

Solution 2:

Write each of the n+1 integers a_{1}, a_{2}, \ldots, a_{n+1} as a power of 2 times an odd integer. In other words, let a_{j} = 2^{k_{j}}q_{j} for j=1, 2, 3 \ldots n+1, where k_{j} is a nonnegative integer and q_{j} is odd. The integers q_{1}, q_{2}, \ldots, q_{n+1} are all odd positive integers less than 2n. Because there are only n odd positive integers less than 2n, it follows from the pigeonhole principle that two of the integers q_{1}, q_{2}, \ldots, q_{n+1} must be equal. Therefore, there are integers i and j such that q_{i} = q_{j}. Let q be the common value of q_{i} and q_{j}. Then, a_{i}=2^{k_{i}}q and a_{j}=2^{k_{j}}q. It follows that if k_{i}<k_{j} then a_{i} divides a_{j}. QED.

A clever application of the pigeonhole principle shows the existence of an increasing or a decreasing subsequence of a certain length in a sequence of distinct integers. Some definitions will be reviewed before this application is presented. Suppose that a_{1}, a_{2}, a_{3}, \ldots, a_{n} is a sequence of real numbers. A subsequence of this sequence is a sequence of the form a_{1_{1}}, a_{i_{2}}, \ldots, a_{i_{n}}, where 1 \leq i_{1} < i_{2} < ldots < i_{n} \leq N. Hence, a subsequence is a sequence obtained from the original sequence by including some of the original sequence in their original order, and perhaps, not including other terms. A sequence is called strictly increasing if each term is larger than the one that precedes it, and it is called strictly decreasing if each term is smaller than the one that precedes it.

Theorem:

Every sequence of n^{2}+1 distinct real numbers contains a subsequence of length n+1 that is either strictly increasing or strictly decreasing.

An example is presented below (before the proof) of the above:

Example:

The sequence 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 contains 10 terms. Note that 10=3^{2}+1. There are four increasing subsequence of length four, namely, 1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; 1, 4, 5, 7. There is also a decreasing subsequence of length four, namely, 11, 9, 6, 5.

The proof of the theorem is presented below:

Let a_{1}, a_{2}, \ldots, a_{n^{2}}+1 be a sequence of n^{2}+1 distinct real numbers. Associate an ordered pair with each term of the sequence, namely, associate (a_{k},d_{k}) to the term a_{k}, where i_{k} is the length of the longest increasing subsequence starting at a_{k}, and d_{k} is the length of the longest decreasing subsequence starting at a_{k}.

Suppose that there are no increasing or decreasing subsequences of length n+1. Then, i_{k} and d_{k} are both positive integers less than or equal to n, for k=1, 2, \ldots, n^{2}+1. Hence, by the product rule there are n^{2} possible ordered pairs for (i_{k},d_{k}). By the pigeonhole principle, two of these n^{2}+1 ordered pairs are equal. In other words, there exist terms a_{s} and a_{t}, with s<t such that i_{s}=i_{t} and d_{s}=d_{t}. We will show that this  is impossible. Because the terms of the sequence are distinct, either a_{s}>a_{t} or a_{s}<a_{t}. If a_{s}<a_{t}, then, because i_{s}=i_{t}, an increasing subsequence of length i_{t}+1, can be built starting at a_{s}, by taking a_{s} followed by an increasing subsequence of length i_{t} beginning at a_{t}. This is a contradiction. Similarly, if a_{s}>a_{t}, the same reasoning shows that d_{s} must be greater than d_{t}, which is a contradiction. QED.

Quiz based on generalized pigeonhole principle:

Assume that in a group of six people, each pair of individuals consists of two friends or two enemies. Show that there are either three mutual friends or three mutual enemies in the group.

Note: This little quiz is a motivation for Ramsey theory. This theory deals with the distribution of of subsets of elements of sets.

More later,

Nalin Pithwa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s