Discrete Mathematics for Computer Science

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 sub-

sequence 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 <a -c = b <2n - 1

Hence,

1 <c < (2n - 1)/n <2

However, there is no integer c between 1 and 2.
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