Advanced book on Mathematics Olympiad

732 Combinatorics and Probability

This product is positive, so by exchangingyσ(i)andyσ(j)we decrease the sum. This
means that this permutation does not minimize the sum. Therefore, the sum is minimal
for the identity permutation. The inequality follows.

833.LetN(σ)be the number we are computing. Denote byNi(σ )the average number of
largeintegersai. Taking into account the fact that after choosing the firsti−1 numbers,
theith is completely determined by the condition of being large, for any choice of the
firsti−1 numbers there are(n−i+ 1 )!choices for the lastn−i+1, from which(n−i)!
contain a large integer in theith position. We deduce thatNi(σ )=n−^1 i+ 1. The answer
to the problem is therefore

N(σ)=

∑n

i= 1

Ni(σ )= 1 +

1

2

+···+

1

n

.

(19th W.L. Putnam Mathematical Competition, 1958)

834.We will show thatσ is the identity permutation. Assume the contrary and let
(i 1 ,i 2 ,...,ik)be a cycle, i.e.,σ(i 1 )=i 2 ,σ(i 2 )=i 3 ,...,σ(ik)=i 1. We can assume
thati 1 is the smallest of theij’s,j= 1 , 2 ,...,k. From the hypothesis,

ai 1 ai 2 =ai 1 aσ(i 1 )<aikaσ(ik)=aikai 1 ,

soai 2 <aikand thereforei 2 <ik. Similarly,

ai 2 ai 3 =ai 2 aσ(i 2 )<aikaσ(ik)=aikai 1 ,

and sinceai 2 >ai 1 it follows thatai 3 <aik,soi 3 <ik. Inductively, we obtain that
ij<ik,j= 1 , 2 ,...,k−1. But then

aik− 1 aik=aik− 1 aσ(ik− 1 )<aikaσ(ik)=aikai 1 ,

henceik− 1 <i 1 , a contradiction. This proves thatσis the identity permutation, and we
are done.
(C. Nast ̆ ̆asescu, C. Ni ̧ta, M. Brandiburu, D. Joi ̧ta, ̆ Exerci ̧tii ̧si Probleme de Algebra ̆
(Exercises and Problems in Algebra), Editura Didactica ̧ ̆si Pedagogica, Bucharest, 1983) ̆

835.LetS ={ 1 , 2 ,..., 2004 }. Write the permutation as a functionf : S → S,
f (n)=an,n= 1 , 2 ,...,2004. We start by noting three properties off:

(i)f(i) =ifor anyi,
(ii)f(i) =f(j)ifi =j,
(iii)f(i)=jimpliesf(j)=i.