Advanced book on Mathematics Olympiad

Combinatorics and Probability 731

Whenr=4, there are

( 6

4

)

ways to split the numbers into the two cycles (two cycles

are needed and not just one). One cycle is a transposition. There are( 4 − 1 )!= 6

choices for the other. Hence in this case the number is 90. Note that here exactly four

transpositions are needed.

Finally, whenr=3, then there are

( 6

3

)

×( 3 − 1 )!×( 3 − 1 )!=40 cases. Therefore,

the answer to the problem is 144+ 90 + 40 =274.

(Korean Mathematical Olympiad, 1999)

831.We would like to find a recursive scheme forf (n). Let us attempt the less ambitious

goal of finding a recurrence relation for the numberg(n)of permutations of the desired

form satisfyingan=n. In that situation eitheran− 1 =n−1oran− 1 =n−2, and in the

latter case we necessarily havean− 2 =n−1 andan− 3 =n−3. We obtain the recurrence

relation

g(n)=g(n− 1 )+g(n− 3 ), forn≥ 4.

In particular, the values ofg(n)modulo 3 are 1, 1 , 1 , 2 , 0 , 1 , 0 , 0 ,...repeating with

period 8.

Now leth(n)=f (n)−g(n). We see thath(n)counts permutations of the desired

form withnoccurring in the middle, sandwiched betweenn−1 andn−2. Removing

nleaves an acceptable permutation, and any acceptable permutation onn−1 symbols

can be so produced, except those ending inn−4,n−2,n−3,n−1. So forh(n),we

have the recurrence

h(n)=h(n− 1 )+g(n− 1 )−g(n− 4 )=h(n− 1 )+ g(n− 2 ), forn≥ 5.

A routine check shows thath(n)modulo 3 repeats with period 24.
We find thatf (n)repeats with period equal to the least common multiple of 8 and
24, which is 24. Because 1996≡ 4 (mod 24), we havef( 1996 )≡f( 4 )= 4 (mod 3).
Sof( 1996 )is not divisible by 3.
(Canadian Mathematical Olympiad, 1996)
832.To solve this problem we will apply Sturm’s principle, a method discussed in Sec-
tion 2.1.6. The fact is that asσranges over all permutations, there aren!sums of the form

∑n

i= 1

(xi−yσ(i))^2 ,

and one of them must be the smallest. Ifσis not the identity permutation, then it must

contain an inversion, i.e., a pair(i, j )withi<jandσ(i)>σ(j). We have

(xi−yσ(i))^2 +(xj−yσ(j))^2 −(xi−yσ(j))^2 −(xj−yσ(i))^2 =(xj−xi)(yσ(i)−yσ(j)).