Problem:
A word is a finite sequence of letters from some alphabet. A word is repetitive if it is a concatenation of at least two identical subwords (for example, and are repetitive, but and are not). Prove that if a word has the property that swapping any two adjacent letters makes the word repetitive, then all its letters are identical. (Note that one may swap two adjacent identical letters, leaving a word unchanged.)
Solutions — 3
Solution 1
Solution:
In this and the subsequent solutions we refer to a word with all letters identical as constant.
Let us consider a nonconstant word , of length , and reach a contradiction. Since the word must contain two distinct adjacent letters, be it with , we may assume to be non-empty, and so . By the proper transpositions we get the repetitive words , of a period of length , and , of a period of length . However, if a word is repetitive, then the word is also repetitive, of a same period length; therefore we can work in the sequel with the repetitive words , of a period of length , and , of a period of length . The main idea now is that the common prefix of two repetitive words cannot be too long.
Now, if a word is repetitive, of a period of length , then the word (and any subword of it) is -periodic, i.e. , for all . Therefore the word is both -periodic and -periodic.
We now use the following classical result:
Wilf-Fine Theorem. Let be positive integers, and let be a word of length , which is both -periodic and -periodic. If then the word is -periodic (but this need not be the case if instead ).
By this we need , hence , otherwise and would be identical, absurd. Since and , we have , and so ; similarly we have .
If , then , so , implying . But the three-letter suffix is not periodic (not even for or ), thus must be contained in , forcing , contradiction.
If , then , so , hence , forcing and ; by an above observation, we may even say and , leading to . It follows , forcing . This leads to , contradiction.
Solution 2
Solution:
We will take over from the solution above, just before invoking the Wilf-Fine Theorem, by replacing it with a weaker lemma, also built upon a seminal result of combinatorics on words.
Lemma. Let be positive integers, and let be a word of length , which is both -periodic and -periodic. If then the word is -periodic.
Proof. Let us first prove that two not-null words commute, i.e. , if and only if there exists a word with , such that . The "if" part being trivial, we will prove the "only if" part, by strong induction on . Indeed, for the base step we have , and so clearly we can take . Now, for , if it follows , and so we can again take . If not, assume without loss of generality ; then , so , whence . Since , it follows , so by the induction hypothesis there exists a suitable word such that , so .
Now, assuming without loss of generality , we have , with . If all is clear; otherwise it follows we can write , with , whence , implying , and so by the above result there will exist a word of length such that , , therefore is -periodic.
By this we need , hence , otherwise by the previous lemma and would be identical, absurd. Since and , we have , and so ; similarly we have . That implies . Now, from we will have ; but is impossible, since the three-letter suffix is not periodic (not even for or ), thus must be contained in , forcing . Therefore , and so .
If , then , for a quick contradiction.
If , it follows , hence , forcing and ; by an above observation, we may even say and , leading to . It follows , leading to , contradiction.
If , it follows , hence . From then follows either and , thus , clearly contradictory, or else and , thus , which also leads to contradiction, by just a little deeper analysis.
Solution 3
Solution:
We define the distance between two words of the same length to be the number of positions in which those two words have different letters. Any two words related by a transposition have distance 0 or 2; any two words related by a sequence of two transpositions have distance or .
Say the period of a repetitive word is the least such that the word is the concatenation of two or more identical subwords of length . We use the following lemma on distances between repetitive words.
Lemma. Consider a pair of distinct, nonconstant repetitive words with periods and , where and , the first word is made up of repetitions of the subword of length and the second word is made up of repetitions of the subword of length . These two words have distance at least .
Proof. We may assume , since the distance between the words is times the distance between their initial subwords of length . Without loss of generality suppose .
For each positive integer , look at the subsequence in each word of letters in positions congruent to . Those subsequences (of length ) have periods dividing and respectively. If they are equal, then they are constant (since each letter is equal to those and before and after it, mod , and ). Because , there is some for which the first subsequence is not constant, and so is unequal to the second subsequence. Restrict attention to those subsequences.
We now have two distinct repetitive words, one (nonconstant) made up of repetitions of a subword of length and one made up of repetitions of a subword of length . Looking at the first of those words, for any consider the letters in positions . These letters cover every position (mod ); since the first word is not constant, the letters are not all equal, but the letters in the corresponding positions in the second word are all equal. At least one of these letters in the first word must change to make them all equal to those in the corresponding positions in the second word; repeating for each , at least letters must change, so the words have distance at least .
In the original problem, consider all the words (which we suppose to be repetitive) obtained by a transposition of two adjacent letters from the original nonconstant word; say that word has length . Suppose those words include two distinct words with periods and ; those words have distance at most . If or , we have a contradiction unless or . If is the greatest number of repetitions in any of the words ( is the smallest period), then unless all the numbers of repetitions divide each other there must be words with or repetitions, words with repetitions and all larger numbers of repetitions must divide each other and be divisible by .
We now divide into three cases: all the numbers of repetitions may divide either other; or there may be words with (multiples of) and repetitions; or all words may have at most repetitions, with at least one word having repetitions and at least one having or repetitions.
Case 1. Suppose all the numbers of repetitions divide each other. Let be the least number of repetitions. Consider the word as being divided into blocks, each of letters; any transposition of two adjacent letters leaves those blocks identical. If any two adjacent letters within a block are the same, then this means all the blocks are already identical; since the word is not constant, the letters in the first block are not all identical, so there are two distinct adjacent letters in the first block, and transposing them leaves it distinct from the other blocks, a contradiction. Otherwise, all pairs of adjacent letters within each block are distinct; transposing any adjacent pair within the first block leaves it identical to the second block. If the first block has more than two letters, this is impossible since transposing the first two letters has a different result from transposing the second two. So the blocks all have length ; similarly, there are just two blocks, the arrangement is but transposing the adjacent letters does not leave the word repetitive.
Case 2. Suppose some word resulting from a transposition is made of (a multiple of) repetitions, some of repetitions and some of repetitions (or repetitions, counted as ). Consider it as a sequence of blocks, each of length . If the six blocks are already identical, then as the word is not constant, there are some two distinct adjacent letters within the first block; transposing them leaves a result where the blocks form a pattern , which cannot have two, three or six repetitions. So the six blocks are not already identical. If a transposition within a block results in them being identical, the blocks form a pattern (without loss of generality) or . In any of these cases, apply the same transposition (that converts between and ) to an block adjacent to the block, and the result cannot have two, three or six repetitions. Finally, consider the case where some transposition between two adjacent blocks results in all six blocks being identical. The patterns are and (and considering the letters at the start and end of each block shows ). In all cases, transposing two adjacent distinct letters within an block produces a result that cannot have two, three or six repetitions.
Case 3. In the remaining case, all words have at most repetitions, at least one has repetitions and at least one has or repetitions. For the purposes of this case we will think of -repetition words as being -repetition words. The number of each letter is a multiple of , so ; consider the word as made of six blocks of length .
If the word is already repetitive with repetitions, pattern , any transposition between two distinct letters leaves it no longer repetitive with two repetitions, so it must instead have three repetitions after the transposition. If is not all one letter, transposing two adjacent letters within implies that , so , the word has pattern but transposing within the initial means it no longer has repetitions. This implies that is all one letter, but similarly must also be all one letter and so the word is constant, a contradiction.
If the word is already repetitive with repetitions, it has pattern and any transposition leaves it no longer having repetitions, so having repetitions instead. is not made all of one letter (since the word is not constant) and any transposition between two adjacent distinct letters therein turns it into ; such a transposition affects at most two of the blocks, so , the word has pattern and transposing two adjacent distinct letters within the first half cannot leave it with two repetitions.
So the word is not already repetitive, and so no two adjacent letters are the same; all transpositions give distinct strings. Consider transpositions of adjacent letters within the first four letters; three different words result, of which at most one is periodic with two repetitions (it must be made of two copies of the second half of the word) and at most one is periodic with three repetitions, a contradiction.