CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 119
6.6 Prove Theorem 6.5:Dn=n![ 1 − 11 !+ 21 !− 31 !+···+(− 1 )nn^1 !]
Recall (Section 3.3) thatSndenotes the set of permutations onX={ 1 , 2 ,...,n}and|Sn|=n!. Fori= 1 ,...,n,
letFidenote all permutations inSnwhich “fixi,” that is,Fi={σ∈Sn|σ(i)=i}. Then, for distinct subscripts,
|Fr|=(n− 1 )!, |Fi∩Fi|=(n− 2 )!,...|Fi 1 ∩Fi 2 ∩...∩Fir|=(n−r)!
LetYdenote the set of all derangements inSn. Then
Dn=|Y|=|F 1 C∩F 2 C∩···∩FnC|
By the Inclusion–Exclusion principle,
Dn=|Sn|−s 1 +s 2 −s 3 +···+(− 1 )nsn
where
sr=∑i 1 <i 2 <...<in|Fi 1 ∩Fi 2 ∩...∩Fir|=C(n, r) (n−r)!=
n!
r!
Setting|Sn|=n!andsr=n!/r!in the formula forDngives us our theorem.PIGEONHOLE PRINCIPLE
6.7. Suppose five points are chosen from the interior of a squareSwhere each side has length two inches. Show
that the distance between two of the points must be less than√
2 inches.
Draw two lines between the opposite sides ofSwhich partitionsSinto four subsquares each whose sides have
length one inch. By the Pigeonhole Principle, two of the points lie in one of the subsquares. The diagonal of each
subsquare is√
2 inches, so the distance between the two points is less than√
2 inches.6.8. Letpandqbe positive integers.Anumberris said to satisfy the(p, q)-Ramsey property if a set ofrpeople
must have a subset ofpmutual friends or a subset ofqmutual strangers. The Ramsey numberR(p, q)is
the smallest such integerr. Show that R(3, 3)=6.
By Example 6.5,R( 3 , 3 )≥6. We show thatR( 3 , 3 )>5. Consider five people who are sitting around a circular
table, and suppose each person is only friends with the people sitting next to him/her. No three people can be strangers
since two of the three people must be sitting next to each other. Also no three people can be mutual friends since they
cannot be sitting next to each other. ThusR( 3 , 3 )>5. AccordinglyR( 3 , 3 )=6.
6.9. Suppose a teamXplays 18 games in a two-week 14-day period, and plays at least one game a day. Show
that there is a period of days in which exactly 9 games were played.
LetS={s 1 ,s 2 ,...,s 14 }where siis the number of gamesXplayed from the first day to theith day. Thens 14 =18,
and all the siare distinct. LetT={t 1 ,t 2 ,...,t 14 }whereti=si+9. Thent 14 = 18 + 9 =27, and thetiare distinct.
TogetherSandThave 14+ 14 =28 numbers, which lie between 1 and 27. By the Pigeonhole Principle, two of the
numbers must be equal. However the entries inSand the entries inTare distinct. Thus there issj∈Sandtn∈Tsuch
thatsj=tk=sk+9. Therefore,
9 =sj−sn=number of games played in daysk+ 1 ,k+ 2 ,...,j− 1 ,j6.10. Prove Theorem 6.7: Every sequence of distinctn^2 +1 real numbers contains a subsequence of lengthn+ 1
which is strictly increasing or strictly decreasing.Leta 1 ,a 2 ,...,an (^2) +ibe a sequence ofn^2 +1 distinct real numbers. To eachatwe associate the pair(it,dt)where:
(1)itis the longest increasing subsequence beginning atatand (2)dtis the longest decreasing subsequence beginning
atatThus there aren^2 +1 such ordered pairs, one for each number in the sequence.
Now suppose that no subsequence is longer thann. Thenitanddtcannot exceedn. Thus there are at mostn^2
distinct pairs(it,dt). By the Pigeonhole Principle, two of then^2 +1 pairs are equal, that is, there are two distinct
pointsarandassuch that(ir,dr)=(is,ds). WLOG, we can assumer<s. Thenaroccurs beforeasin the sequence
(See Fig. 6-2(a)). Thenarfollowed by the increasing subsequence ofisnumbers beginning atasgives a subsequence
of lengthis+ 1 =ir+1 beginningar(See Fig. 6-2(b)). This contradicts the definition ofir. Similarly, suppose
ar >as. Thenanfollowed by the decreasing subsequence ofdsnumbers beginning atasgives a subsequence of
lengthdr+ 1 =ds+1 beginning atarwhich contradicts the definition ofdr(See Fig. 6-2(c)). In each case we get a
contradiction. Thus the assumption that no subsequence exceedsnis not true, and the theorem is proved.