Advanced book on Mathematics Olympiad

Combinatorics and Probability 733

The first two properties are obvious, while the third requires a proof. Arguing by
contradiction, let us assume thatf(i)=jbutf(j) =i. We discuss first the case
j>i. Ifweletk=j−i, thenf(i)=i+k. Sincek=|f(i)−i|=|f(j)−j|
andf(j) =i, it follows thatf(j)=i+ 2 k, i.e.,f(i+k)=i+ 2 k. The same
reasoning yieldsf(i+ 2 k)=i+kori+ 3 k. Since we already havef(i)=i+k, the
only possibility isf(i+ 2 k)=i+ 3 k. And the argument can be repeated to show that
f(i+nk)=i+(n+ 1 )kfor alln. However, this then forcesftoattain ever increasing
values, which is impossible since its range is finite. A similar argument takes care of the
casej<i. This proves (iii).
The three properties show thatfis an involution onSwith no fixed points. Thusf
partitionsSinto 1002 distinct pairs(i, j )withi=f(j)andj=f(i). Moreover, the
absolute value of the difference of the elements in any pair is the same. Iff( 1 )− 1 =k
thenf( 2 ) =k+ 1 ,...,f(k)= 2 k, and sincef is an involution, the values off
onk+ 1 ,k+ 2 ,..., 2 kare already determined, namelyf(k+ 1 )= 1 ,f(k+ 2 )=
2 ,...,f( 2 k)=k. So the first block of 2kintegers is invariant underf. Using similar
reasoning, we obtainf( 2 k+ 1 )= 3 k+ 1 ,f( 2 k+ 2 )= 3 k+ 2 ,...,f( 3 k)= 4 k,f ( 3 k+
1 )= 2 k+ 1 ,...,f( 4 k)= 3 k. So the next block of 2kintegers is invariant underf.
Continuing this process, we see thatfpartitionsSinto blocks of 2kconsecutive integers
that are invariant underf. This can happen only if 2kdivides 2004, hence ifkdivides

1002. Furthermore, for each suchkwe can constructffollowing the recipe given above.
      Hence the number of such permutations equals the number of divisors of 1002, which
      is 8.
      (Australian Mathematical Olympiad, 2004, solution by L. Field)

836.Expanding|σ(k)−k|as±σ(k)±kand reordering, we see that

|σ( 1 )− 1 |+|σ( 2 )− 2 |+···+|σ (n)−n|=± 1 ± 1 ± 2 ± 2 ±···±n±n,

for some choices of signs. The maximum of|σ( 1 )− 1 |+|σ( 2 )− 2 |+···+|σ (n)−n|
is reached by choosing the smaller of the numbers to be negative and the larger to be
positive, and is therefore equal to

2

(

− 1 − 2 −···−

n− 1

2

)

−

n+ 1

2

+

n+ 1

2

+ 2

(

n+ 3

2

+···+n

)

=−

(

1 +

n− 1

2

)

n− 1

2

+

(

n+ 3

2

+n

)

n− 1

2

=

n^2 − 1

2

.

Therefore, in order to have|σ( 1 )− 1 |+···+|σ (n)−n|=n

(^2) − 1
2 , we must have
{
σ( 1 ),...,σ

(

n− 1

2

)}

⊂

{

n+ 1

2

,

n+ 3

2

,...,n

}

and