Advanced book on Mathematics Olympiad

730 Combinatorics and Probability

other colors chosen from 1, 2, and 3. Ifx∼x 0 thenfn(x)=fm(x 0 )for some integers
mandn. For that particularx, choosemandnto be minimal with this property. Color
xbyjifm−nis even, and bykifm−nis odd.
Note thatxandf(x)cannot have the same color, for otherwise in the equalities
fn(x) = fm(x 0 )andfn+^1 (x) =fm′(x 0 )the minimality ofmandm′implies that
m=m′, and thenn−mandn+ 1 −mwould have the same parity, which is impossible.
Again, the coloring partitionsAinto four sets with the desired properties.

829.We solve the more general case of the permutations of the first 2npositive integers,

n≥1. The average of the sum

∑n

k= 1

|a 2 k− 1 −a 2 k|

is justntimes the average value of|a 1 −a 2 |, because the average value of|a 2 i− 1 −a 2 i|

is the same for alli= 1 , 2 ,...,n. Whena 1 =k, the average value of|a 1 −a 2 |is

(k− 1 )+(k− 2 )+···+ 1 + 1 + 2 +···+( 2 n−k)

2 n− 1

=

1

2 n− 1

[

k(k− 1 )

2

+

( 2 n−k)( 2 n−k+ 1 )

2

]

=

k^2 −( 2 n+ 1 )k+n( 2 n+ 1 )

2 n− 1

.

It follows that the average value of the sum is

n·

1

2 n

∑^2 n

k= 1

k^2 −( 2 n+ 1 )k+n( 2 n+ 1 )

2 n− 1

=

1

4 n− 2

[

2 n( 2 n+ 1 )( 4 n+ 1 )

6

−( 2 n+ 1 )

2 n( 2 n+ 1 )

2

+ 2 n^2 ( 2 n+ 1 )

]

=

n( 2 n+ 1 )

3

.

For our problemn=5 and the average of the sums is^553.

(American Invitational Mathematics Examination, 1996)

830.The condition from the statement implies that any such permutation has exactly two

disjoint cycles, say(ai 1 ,...,air)and(air+ 1 ,...,ai 6 ). This follows from the fact that in

order to transform a cycle of lengthrinto the identityr−1, transpositions are needed.

Moreover, we can only haver=5, 4, or 3.

Whenr=5, there are

( 6

1

)

choices for the number that stays unpermuted. There are

( 5 − 1 )!possible cycles, so in this case we have 6× 4 !=144 possibilities.