6.1 Combinatorial Arguments in Set Theory and Geometry 285an angle of^2 nπaround its center. Such a rotation can be written as the composition of
two reflections that map then-gon to itself, namely the reflection with respect to the per-
pendicular bisector ofA 1 A 3 and the reflection with respect to the perpendicular bisector
ofA 2 A 3 (see Figure 37). These reflections define the permutationsσ 1 andσ 2.
Figure 37The following problems are left to the reader.829.For each permutationa 1 ,a 2 ,...,a 10 of the integers 1, 2 , 3 ,...,10, form the sum
|a 1 −a 2 |+|a 3 −a 4 |+|a 5 −a 6 |+|a 7 −a 8 |+|a 9 −a 10 |.Find the average value of all such sums.830.Find the number of permutationsa 1 ,a 2 ,a 3 ,a 4 ,a 5 ,a 6 of the numbers 1, 2, 3, 4, 5, 6
that can be transformed into 1, 2 , 3 , 4 , 5 ,6 through exactly four transpositions (and
not fewer).
831.Letf (n)be the number of permutationsa 1 ,a 2 ,...,anof the integers 1, 2 ,...,n
such that (i)a 1 =1 and (ii)|ai−ai+ 1 |≤2,i= 1 , 2 ,...,n−1. Determine whether
f( 1996 )is divisible by 3.
832.Consider the sequences of real numbersx 1 >x 2 >···>xnandy 1 >y 2 >···>
yn, and letσbe a nontrivial permutation of the set{ 1 , 2 ,...,n}. Prove that
∑ni= 1(xi−yi)^2 <∑ni= 1(xi−yσ(i))^2.833.Leta 1 ,a 2 ,...,anbe a permutation of the numbers 1, 2 ,...,n. We callaialarge
integer ifai>ajfor alli<j<n. Find the average number of large integers over
all permutations of the firstnpositive integers.
834.Given some positive real numbersa 1 <a 2 <···<anfind all permutationsσwith
the property that
a 1 aσ( 1 )<a 2 aσ( 2 )<···<anaσ (n).