Advanced book on Mathematics Olympiad

286 6 Combinatorics and Probability

835.Determine the number of permutationsa 1 ,a 2 ,...,a 2004 of the numbers 1, 2,...,

2004 for which

|a 1 − 1 |=|a 2 − 2 |=···=|a 2004 − 2004 |> 0.

836.Letnbe an odd integer greater than 1. Find the number of permutationsσof the

set{ 1 , 2 ,...,n}for which

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

n^2 − 1

2

.

6.1.3 Combinatorial Geometry..................................

We grouped under this title problems that are solved by analyzing configurations of

geometric objects. We start with an easy problem that was proposed in 1999 for the

Junior Balkan Mathematical Olympiad.

Example.In a regular 2n-gon,ndiagonals intersect at a pointS, which is not a vertex.

Prove thatSis the center of the 2n-gon.

Solution.Fix one of thendiagonals. The othern−1 diagonals intersect it, so there are

n−1 vertices on one side andn−1 vertices on the other side of this diagonal. Hence

this was a main diagonal. Repeating the argument we conclude that allndiagonals are

main diagonals, so they meet at the center. 

We continue with an example suggested to us by G. Galperin.

Example.Show that from any finitely many (closed) hemispheres that cover a sphere

one can choose four that cover the sphere.

Solution.In what follows, by a half-line, half-plane, and half-space we will understand

a closed half-line, half-plane, respectively, half-space. The hemispheres are obtained

by intersecting the sphere with half-spaces passing through the origin. This observation

allows us to modify the statement so as to make an inductive argument on the dimension

possible.

Alternative problem. Show that from any finitely many half-spaces that cover the three-
dimensional space one can choose four that cover the space.

Let us analyze first the one- and two-dimensional cases. Among any finite set of

half-lines covering a certain line one can choose two that cover it. Indeed, identifying

the line with the real axis, the first of them can be chosen to be of the form[a,∞), with

asmallest among the half-lines of this type in our set, and the other to be of the form

(−∞,b], withblargest among the half-lines of this type in our set.