Turkey — Team Selection Test

Let the first written word be $(1,2,\dots,n)$. By induction on $n$ we prove that the number of written words is $n!$.

If $n = 2$ then R.L. starts with $(1, 2)$ and then reverses it and writes $(2, 1)$.

Suppose that for $n = k-1$ the words
$$W_1^{k-1}, W_2^{k-1}, \dots, W_{(k-1)!}^{k-1}$$
are written to the notebook.

Consider the sequence of words
$$W_1^k, W_2^k, \dots,$$
in the case $n = k$. We will use the notation $(a, b, \dots, p) * q$. Let us divide the sequence above into blocks each consisting of $2k$ consecutive words. We show that the $m$-th block is
$$W_{2m-1}^{k-1} * k, \dots, W_{2m}^{k-1} * k$$
Indeed, the first block starts with $W_1^{k-1} * k$ and ends with $W_2^{k-1} * k$, the second block starts with $W_3^{k-1} * k$ and ends with $W_4^{k-1} * k$, ..., the last block starts with $W_{(k-1)!-1}^{k-1} * k$ and ends with $W_{(k-1)!}^{k-1} * k$.

Inside each block each $2l+1$ numbered word of the block is obtained from $2l-1$ numbered word of the same block by shortest counter-clockwise rotation and each $2l+2$ numbered word of the block is obtained from $2l$ numbered word of the same block by shortest clockwise rotation. Therefore, all words inside each block are different and each block is closed under the operation of rotation. Since all words in the sequence above are different all words in the new sequence also will be different.

By induction hypothesis there are $(k-1)!$ terms in the previous sequence. Therefore, there are $(k-1)!/2$ blocks in the new sequence and the sequence consists of $(k-1)!/2 \cdot 2k = k!$ distinct words. We are done.