In a word of more than $10$ letters, any two consecutive letters are different. Prove that one can change places of two consecutive letters so that the resulting word is not periodic, that is, cannot be divided into equal subwords.
Problem
Source: XVIII Tuymaada Mathematical Olympiad (2011)
Tags: combinatorics unsolved, combinatorics
29.07.2011 20:35
Let us assume the word is $W = w_1w_2\ldots w_n$, of length $|W| = n$, and letters from some alphabet $w_k \in A$ for all $1\leq k \leq n$. From the given condition follows $|A|\geq 2$. Now, in order for a swap of letters to maybe create a periodic word, with (obvious $1 < p < n$) period length $p \mid n$, then each letter in the word must repeat (at least) $n/p \geq 2$ times. Among all letters of the word $W$ select one, say $a$, such that some difference $\delta$ between its consecutive apparitions is minimal in length. According to the given condition, we have $\delta > 1$, so $W = \ldots a w_1w_2\ldots w_{\delta} a \ldots$. Then swapping $aw_1$ (or $w_{\delta} a$) creates a word $W'$ with a strictly lesser difference $\delta'= \delta-1$, which is therefore unique. If $W'$ were periodic of $p\geq 3$ that will be a contradiction, so at most we will have $p=2$, with the two occurences of $a$ at closest distance lying in different periods. For this to occur $n$ must be even. But then, since $n\geq 6$, there will exist a subword $bcd$ in the second-half-word. Two of its possible swaps produce $cbd \neq bdc$ (since $b\neq c$), and so one of the resulting second-half-words will be different from the first-half word (which stays unchanged), thus the resulting word will be non-periodic. However, it is immediately seen that even for $n=4$ the result holds (not to mention smaller values of $n$), so the restriction $n>10$ was bogus.
31.01.2022 09:32
I think your solution is not true we can have different periods length for different swaps so you can't swap cbd and bdc when you do this then P mabe changes and is not still 2 . But this works assum that two a's have the minimum length of two consecutive apparitions in all the word then swapping $a w_1$and$a w_2$ shows that p=2 and checking last letters of the word gives us contradiction.