## Problem 4.

An encyclopedia consists of 2000 numbered volumes. The volumes are stacked in order with number 1 on top and 2000 in the bottom. One may perform two operations with the stack:

(i) For $n$ even, one may take the top $n$ volumes and put them in the bottom of the stack without changing the order.

(ii) For $n$ odd, one may take the top $n$ volumes, turn the order around and put them on top of the stack again.

How many different permutations of the volumes can be obtained by using these two operations repeatedly?


Solution 1. (By the proposer.) Let the positions of the books in the stack be $1,2,3, \ldots, 2000$ from the top (and consider them modulo 2000). Notice that both operations fix the parity of the number of the book at a any given position. Operation (i) subtracts an even integer from the number of the book at each position. If $A$ is an operation of type (i), and $B$ is an operation of type (ii), then the operation $A^{-1} B A$ changes the order of the books in the positions $n+1$ to $n+m$ where $n$ is even and $m$ is odd. This is called turning the interval.

Now we prove that all the volumes in odd positions can be placed in the odd positions in every way we like: If the volume we want in position 1 is in position $m_{1}$, we turn the interval 1 to $m_{1}$. Now if the volume we want in position 3 is in position $m_{3}$, we turn the interval 3 to $m_{3}$, and so on. In this way we can permute the volumes in odd positions exactly as we want to.

Now we prove that we can permute the volumes in even positions exactly as we want without changing the positions of the volumes in the odd positions: We can make a transposition of the two volumes in position $2 n$ and $2 n+2 m$ by turning the interval $2 n+1$ to $2 n+2 m-1$, then turning the interval $2 n+2 m+1$ to $2 n-1$, then turning the interval $2 n+1$ to $2 n-1$, and finally adding $2 m$ to the number of the volume in each position.

Since there are 1000! permutations of the volumes in the odd positions, and 1000! permutations of the volumes in the even positions, altogether we have (1000!) ${ }^{2}$ different permutations.
