The Pigeon-Hole Principle
261
To appreciate these two results, it is helpful to experiment with some subsets of a set,
say (1, 2, 3 ... , 17}, and see how large a subset you can find so that no elements of the
subset divides any other element of the subset. For a second experiment, write down these
17 elements in an arbitrary order (not in increasing or decreasing order), and see how long
a subsequence you can find that is either increasing or decreasing. For example, try
12,6,3,7,8, 1, 17, 16, 14, 15, 13,2,9, 10,4, 11
You should be able to find an increasing subsequence of length six but no increasing subsequence of longer length. The theorems will tell us what we can always expect as answers
for these two problems.
Theorem 8. (Erdos) Let
X C {1,2,3,4,..., 2n - 1}
and I X I > n + 1. There are two numbers a, b E X with a < b such that a divides b.
Proof. For x E X, let F(x) be the largest odd divisor of x. So
F(1) = 1, F(2) = 1, F(3) = 3, F(4) = 1, F(5) = 5, F(6) = 3....
and so forth. For x E X, there are n possible values for F(x), namely 1, 3, 5,..., 2n - 1.
There are at least n + 1 elements of X. So, F is not 1-1 on X. Pick two elements of X
whose images under F are the same, and call the smaller one a and the larger one b. Now,
let
k = F(a) = F(b)
So a = 2i • k, and b = 2i. k where i < j. Then, b = a. 2j-', so a divides b.
U
Theorem 8 is the "best possible" result. That is, if the hypothesis instead required only
that I X I = n, then the result would be false. To prove this for any n, choose
X = {n,n+ 1,n+2,..., 2n- 1}
Then, I X I = n. Now, show that no element of X is a factor of any other. Because if a were
a factor of b, then a . c = b for some c. Since a < b, we must have c > 1. However, a > n
and b < 2n - 1, so
n * c Hence,
1
Theorem 9 tells that in a sequence of n
2 + 1 elements, for any n E N there is always
a subsequence of at least n + 1 elements that is either increasing or decreasing. Even in
choosing a sequence of random numbers, this behavior occurs.
Theorem 9. (Erdos and Szeker6s) Let n E N and k = n
2 + 1. Let
al, a2, a3, . .. , ak
be any sequence of k distinct numbers. Then, the sequence has either an n + 1 element
increasing subsequence or an n + 1 element decreasing subsequence.
Example to Motivate Proof. Let n = 3, and consider the 10-element sequence
5064982173
261
To appreciate these two results, it is helpful to experiment with some subsets of a set,
say (1, 2, 3 ... , 17}, and see how large a subset you can find so that no elements of the
subset divides any other element of the subset. For a second experiment, write down these
17 elements in an arbitrary order (not in increasing or decreasing order), and see how long
a subsequence you can find that is either increasing or decreasing. For example, try
12,6,3,7,8, 1, 17, 16, 14, 15, 13,2,9, 10,4, 11
You should be able to find an increasing subsequence of length six but no increasing subsequence of longer length. The theorems will tell us what we can always expect as answers
for these two problems.
Theorem 8. (Erdos) Let
X C {1,2,3,4,..., 2n - 1}
and I X I > n + 1. There are two numbers a, b E X with a < b such that a divides b.
Proof. For x E X, let F(x) be the largest odd divisor of x. So
F(1) = 1, F(2) = 1, F(3) = 3, F(4) = 1, F(5) = 5, F(6) = 3....
and so forth. For x E X, there are n possible values for F(x), namely 1, 3, 5,..., 2n - 1.
There are at least n + 1 elements of X. So, F is not 1-1 on X. Pick two elements of X
whose images under F are the same, and call the smaller one a and the larger one b. Now,
let
k = F(a) = F(b)
So a = 2i • k, and b = 2i. k where i < j. Then, b = a. 2j-', so a divides b.
U
Theorem 8 is the "best possible" result. That is, if the hypothesis instead required only
that I X I = n, then the result would be false. To prove this for any n, choose
X = {n,n+ 1,n+2,..., 2n- 1}
Then, I X I = n. Now, show that no element of X is a factor of any other. Because if a were
a factor of b, then a . c = b for some c. Since a < b, we must have c > 1. However, a > n
and b < 2n - 1, so
n * c Hence,
1
Theorem 9 tells that in a sequence of n
2 + 1 elements, for any n E N there is always
a subsequence of at least n + 1 elements that is either increasing or decreasing. Even in
choosing a sequence of random numbers, this behavior occurs.
Theorem 9. (Erdos and Szeker6s) Let n E N and k = n
2 + 1. Let
al, a2, a3, . .. , ak
be any sequence of k distinct numbers. Then, the sequence has either an n + 1 element
increasing subsequence or an n + 1 element decreasing subsequence.
Example to Motivate Proof. Let n = 3, and consider the 10-element sequence
5064982173