Discrete Mathematics for Computer Science

262 CHAPTER 4 Functions

The goal is to find either a four-element increasing subsequence or a four-element de-

creasing subsequence.

For each element of the sequence, find the longest increasing subsequence starting

with that element. For example, starting with 5, there are three increasing subsequences of

length three (5 6 9, 5 6 8, and 5 6 7), but none of length four. Starting with 0, there are sev-

eral increasing subsequences of length three but none of length four. Under each number,

write the length of the longest increasing subsequence starting with that number:

(^5 0 6 4 9 8 2 1 7 3)
LongestlncSeq(*) 4, 4, I , 4, 4, 4, 4, 4, 4,
3 3 2 2 1 1 2 2 1 1
If any of these subsequences had length four or greater, then that subsequence would be the
example needed. In this case, there is no such subsequence, since each of the 10 elements of
the sequence mapped to 1, 2, or 3. By the Generalized Pigeon-Hole Principle, we know that
at least four elements of the sequence must map to the same value. In this example, each
element of the subsequence (6, 4, 2, 1) maps to 2, and each element of the subsequence (9,
8, 7, 3) maps to 1. Both of these subsequences are decreasing subsequences of length four.
Proof. Let k = n2 + 1 and the sequence aI, a2 ..... ak be given as in the statement of
Theorem 9. For each ai, define a function F such that F(a,) is the length of the longest
increasing subsequence starting with ai.

We first show that if i < j and ai < aj, then F(ai) > F(aj). This follows because,

if, say, F(aj) = 1, then there is a length-I increasing subsequence beginning with aj :

aj = bj < b 2 < ... < bl. Then, ai < bj < b2 < ... < bl is a subsequence of length l +

1, which implies that F(ai) > 1 + 1 > F(aj). In particular,

if i < j and F(ai) = F(aj), then ai > aj

Case 1: For some i such that 1 <i <k, we have F(ai) > n. Then, there is an increasing

subsequence of length n + 1 starting with ai.

Case 2: There is no i such that 1 < i < k with F(ai) > n. Consequently, the range of F

is a subset of the n-element set { 1, 2, 3. n }. By the Generalized Pigeon-Hole Principle,

at least

[ý(k -1)j L (n^2 + 1)] +1I =n±1

elements of the sequence will be mapped to the same element of {1, 2,..., n). By the

remark before Case 1, these n + 1 elements form a decreasing sequence. 0

rn Exercises

1. Prove that in any set of 27 words, at least two must begin with the same letter assuming
   at most a 26-letter alphabet.


2. Prove that in any group of five integers, at least two have the same value under the
   (mod 4) operation.