Page 425 - Discrete Mathematics and Its Applications

404 6 / Counting

We give an example before presenting the proof of Theorem 3.
2
EXAMPLE 12 The sequence 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 contains 10 terms. Note that 10 = 3 + 1. There
are four strictly increasing subsequences of length four, namely, 1, 4, 6, 12; 1, 4, 6, 7;
1, 4, 6, 10; and 1, 4, 5, 7. There is also a strictly decreasing subsequence of length four,
namely, 11, 9, 6, 5. ▲

The proof of the theorem will now be given.

2
Proof: Let a 1 ,a 2 ,...,a 2 be a sequence of n + 1 distinct real numbers.Associate an ordered
n +1
pair with each term of the sequence, namely, associate (i 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
2
and d k are both positive integers less than or equal to n, for k = 1, 2,...,n + 1. Hence, by the
2
product rule there are n possible ordered pairs for (i k ,d k ). By the pigeonhole principle, two of
2
these n + 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.

The final example shows how the generalized pigeonhole principle can be applied to an im-
portant part of combinatorics called Ramsey theory, after the English mathematician F. P. Ram-
sey. In general, Ramsey theory deals with the distribution of subsets of elements of sets.

EXAMPLE 13 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.

Solution: Let A be one of the six people. Of the five other people in the group, there are either
three or more who are friends of A, or three or more who are enemies of A. This follows from
the generalized pigeonhole principle, because when five objects are divided into two sets, one
of the sets has at least 5/2 = 3 elements. In the former case, suppose that B, C, and D are
friends of A. If any two of these three individuals are friends, then these two and A form a group
of three mutual friends. Otherwise, B, C, and D form a set of three mutual enemies. The proof
in the latter case, when there are three or more enemies of A, proceeds in a similar manner. ▲

The Ramsey number R(m, n), where m and n are positive integers greater than or equal
to 2, denotes the minimum number of people at a party such that there are either m mutual friends
or n mutual enemies, assuming that every pair of people at the party are friends or enemies.
Example 13 shows that R(3, 3) ≤ 6. We conclude that R(3, 3) = 6 because in a group of five

FRANK PLUMPTON RAMSEY (1903–1930) Frank Plumpton Ramsey, son of the president of Magdalene
College, Cambridge, was educated at Winchester and Trinity Colleges. After graduating in 1923, he was elected
a fellow of King’s College, Cambridge, where he spent the remainder of his life. Ramsey made important
contributions to mathematical logic. What we now call Ramsey theory began with his clever combinatorial
arguments, published in the paper “On a Problem of Formal Logic.” Ramsey also made contributions to the
mathematical theory of economics. He was noted as an excellent lecturer on the foundations of mathematics.
According to one of his brothers, he was interested in almost everything, including English literature and politics.
Ramsey was married and had two daughters. His death at the age of 26 resulting from chronic liver problems
deprived the mathematical community and Cambridge University of a brilliant young scholar.