Maths Olympiad Prep

Library / /15 of 33

Combinatorics Difficulty 8.0 National olympiad, round 2 Prove it Turkey

The Retired Linguist (R.L.) in his first move writes a word consisting of nn distinct letters to his notebook. Thereafter in each move he writes a new word to the notebook which is obtained by reversing the longest sub-word (starting from the first letter) of the last added word provided the word is not written to the notebook beforehand. Show that R.L. will write n!n! words to his notebook.

Solution

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

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

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

Consider the sequence of words
W1k,W2k,, W_1^k, W_2^k, \dots,
in the case n=kn = k. We will use the notation (a,b,,p)q(a, b, \dots, p) * q. Let us divide the sequence above into blocks each consisting of 2k2k consecutive words. We show that the mm-th block is
W2m1k1k,,W2mk1k W_{2m-1}^{k-1} * k, \dots, W_{2m}^{k-1} * k
Indeed, the first block starts with W1k1kW_1^{k-1} * k and ends with W2k1kW_2^{k-1} * k, the second block starts with W3k1kW_3^{k-1} * k and ends with W4k1kW_4^{k-1} * k, ..., the last block starts with W(k1)!1k1kW_{(k-1)!-1}^{k-1} * k and ends with W(k1)!k1kW_{(k-1)!}^{k-1} * k.

Inside each block each 2l+12l+1 numbered word of the block is obtained from 2l12l-1 numbered word of the same block by shortest counter-clockwise rotation and each 2l+22l+2 numbered word of the block is obtained from 2l2l 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 (k1)!(k-1)! terms in the previous sequence. Therefore, there are (k1)!/2(k-1)!/2 blocks in the new sequence and the sequence consists of (k1)!/22k=k!(k-1)!/2 \cdot 2k = k! distinct words. We are done.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.