Maths Olympiad Prep

Library / /7 of 14

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it European Girls' Mathematical Olympiad (EGMO)

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, abababa b a b a b and abcabca b c a b c are repetitive, but ababaa b a b a and aabba a b b 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 WW, of length W=w|W|=w, and reach a contradiction. Since the word WW must contain two distinct adjacent letters, be it W=AabBW=A a b B with aba \neq b, we may assume B=cCB=c C to be non-empty, and so W=AabcCW=A a b c C. By the proper transpositions we get the repetitive words W=AbacC=Pw/pW' = A b a c C = P^{w / p}, of a period PP of length pw,1<p<wp \mid w, 1 < p < w, and W=AacbC=Qw/qW'' = A a c b C = Q^{w / q}, of a period QQ of length qw,1<q<wq \mid w, 1 < q < w. However, if a word UVUV is repetitive, then the word VUVU is also repetitive, of a same period length; therefore we can work in the sequel with the repetitive words W0=CAbacW_0' = C A b a c, of a period PP' of length pp, and W0=CAacbW_0'' = C A a c b, of a period QQ' of length qq. The main idea now is that the common prefix of two repetitive words cannot be too long.
Now, if a word a1a2aw=Tw/ta_1 a_2 \ldots a_w = T^{w / t} is repetitive, of a period TT of length tw,1t<wt \mid w, 1 \leq t < w, then the word (and any subword of it) is tt-periodic, i.e. ak=ak+ta_k = a_{k+t}, for all 1kwt1 \leq k \leq w-t. Therefore the word CAC A is both pp-periodic and qq-periodic.
We now use the following classical result:
Wilf-Fine Theorem. Let p,qp, q be positive integers, and let NN be a word of length nn, which is both pp-periodic and qq-periodic. If np+qgcd(p,q)n \geq p+q-\operatorname{gcd}(p, q) then the word NN is gcd(p,q)\operatorname{gcd}(p, q)-periodic (but this need not be the case if instead np+qgcd(p,q)1n \leq p+q-\operatorname{gcd}(p, q)-1).
By this we need CAp+qgcd(p,q)1p+q2|C A| \leq p+q-\operatorname{gcd}(p, q)-1 \leq p+q-2, hence wp+q+1w \leq p+q+1, otherwise W0W_0' and W0W_0'' would be identical, absurd. Since pwp \mid w and 1<p<w1 < p < w, we have 2pwp+q+12p \leq w \leq p+q+1, and so pq+1p \leq q+1; similarly we have qp+1q \leq p+1.
If p=qp=q, then CAp+pgcd(p,p)1=p1|C A| \leq p+p-\operatorname{gcd}(p, p)-1 = p-1, so 2pwp+22p \leq w \leq p+2, implying p2p \leq 2. But the three-letter suffix acba c b is not periodic (not even for c=ac=a or c=bc=b), thus must be contained in QQ', forcing q3q \geq 3, contradiction.
If pqp \neq q, then max(p,q)=min(p,q)+1\max(p, q) = \min(p, q) + 1, so 3min(p,q)w2min(p,q)+23 \min(p, q) \leq w \leq 2 \min(p, q) + 2, hence min(p,q)2\min(p, q) \leq 2, forcing min(p,q)=2\min(p, q) = 2 and max(p,q)=3\max(p, q) = 3; by an above observation, we may even say q=3q = 3 and p=2p = 2, leading to c=bc = b. It follows 6=3min(p,q)w2min(p,q)+2=66 = 3 \min(p, q) \leq w \leq 2 \min(p, q) + 2 = 6, forcing w=6w = 6. This leads to CA=aba=abbC A = a b a = a b b, 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 p,qp, q be positive integers, and let NN be a word of length nn, which is both pp-periodic and qq-periodic. If np+qn \geq p+q then the word NN is gcd(p,q)\operatorname{gcd}(p, q)-periodic.
Proof. Let us first prove that two not-null words U,VU, V commute, i.e. UV=VUUV = VU, if and only if there exists a word WW with W=gcd(U,V)|W| = \operatorname{gcd}(|U|, |V|), such that U=WU/W,V=WV/WU = W^{|U| / |W|}, V = W^{|V| / |W|}. The "if" part being trivial, we will prove the "only if" part, by strong induction on U+V|U| + |V|. Indeed, for the base step U+V=2|U| + |V| = 2 we have U=V=1|U| = |V| = 1, and so clearly we can take W=U=VW = U = V. Now, for U+V>2|U| + |V| > 2, if U=V|U| = |V| it follows U=VU = V, and so we can again take W=U=VW = U = V. If not, assume without loss of generality U<V|U| < |V|; then V=UVV = U V', so UUV=UVUU U V' = U V' U, whence UV=VUU V' = V' U. Since V<V|V'| < |V|, it follows 2U+V<U+V2 \leq |U| + |V'| < |U| + |V|, so by the induction hypothesis there exists a suitable word WW such that U=WU/W,V=WV/WU = W^{|U| / |W|}, V' = W^{|V'| / |W|}, so V=UV=WU/WWV/W=W(U+V)/W=WV/WV = U V' = W^{|U| / |W|} W^{|V'| / |W|} = W^{(|U| + |V'|) / |W|} = W^{|V| / |W|}.
Now, assuming without loss of generality pq,q=kp+rp \leq q, q = k p + r, we have N=QPSN = Q P S, with Q=q,P=p|Q| = q, |P| = p. If r=0r = 0 all is clear; otherwise it follows we can write P=UV,Q=V(UV)kP = U V, Q = V (U V)^k, with V=r|V| = r, whence UV=VUU V = V U, implying PQ=QPP Q = Q P, and so by the above result there will exist a word WW of length gcd(p,q)\operatorname{gcd}(p, q) such that P=Wp/gcd(p,q)P = W^{p / \operatorname{gcd}(p, q)}, Q=Wq/gcd(p,q)Q = W^{q / \operatorname{gcd}(p, q)}, therefore NN is gcd(p,q)\operatorname{gcd}(p, q)-periodic.
By this we need CAp+q1|C A| \leq p+q-1, hence wp+q+2w \leq p+q+2, otherwise by the previous lemma W0W_0' and W0W_0'' would be identical, absurd. Since pwp \mid w and 1<p<w1 < p < w, we have 2pwp+q+22p \leq w \leq p+q+2, and so pq+2p \leq q+2; similarly we have qp+2q \leq p+2. That implies max(p,q)min(p,q)+2\max(p, q) \leq \min(p, q) + 2. Now, from kmax(p,q)=wp+q+22max(p,q)+2k \max(p, q) = w \leq p+q+2 \leq 2 \max(p, q) + 2 we will have (k2)max(p,q)2(k-2) \max(p, q) \leq 2; but max(p,q)2\max(p, q) \leq 2 is impossible, since the three-letter suffix acba c b is not periodic (not even for c=ac=a or c=bc=b), thus must be contained in QQ', forcing q3q \geq 3. Therefore k=2k = 2, and so w=2max(p,q)w = 2 \max(p, q).
If max(p,q)=min(p,q)\max(p, q) = \min(p, q), then w=2p=2qw = 2p = 2q, for a quick contradiction.
If max(p,q)=min(p,q)+1\max(p, q) = \min(p, q) + 1, it follows 3min(p,q)w=2max(p,q)=2min(p,q)+23 \min(p, q) \leq w = 2 \max(p, q) = 2 \min(p, q) + 2, hence min(p,q)2\min(p, q) \leq 2, forcing min(p,q)=2\min(p, q) = 2 and max(p,q)=3\max(p, q) = 3; by an above observation, we may even say q=3q = 3 and p=2p = 2, leading to c=bc = b. It follows w=2max(p,q)=6w = 2 \max(p, q) = 6, leading to CA=aba=abbC A = a b a = a b b, contradiction.
If max(p,q)=min(p,q)+2\max(p, q) = \min(p, q) + 2, it follows 3min(p,q)w=2max(p,q)=2min(p,q)+43 \min(p, q) \leq w = 2 \max(p, q) = 2 \min(p, q) + 4, hence min(p,q)4\min(p, q) \leq 4. From min(p,q)w=2max(p,q)\min(p, q) \mid w = 2 \max(p, q) then follows either min(p,q)=2\min(p, q) = 2 and max(p,q)=4\max(p, q) = 4, thus w=8w = 8, clearly contradictory, or else min(p,q)=4\min(p, q) = 4 and max(p,q)=6\max(p, q) = 6, thus w=12w = 12, 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 0,2,30, 2, 3 or 44.
Say the period of a repetitive word is the least kk such that the word is the concatenation of two or more identical subwords of length kk. We use the following lemma on distances between repetitive words.
Lemma. Consider a pair of distinct, nonconstant repetitive words with periods gag a and gbg b, where (a,b)=1(a, b) = 1 and a,b>1a, b > 1, the first word is made up of kbk b repetitions of the subword of length gag a and the second word is made up of kak a repetitions of the subword of length gbg b. These two words have distance at least max(ka,kb)\max(k a, k b).
Proof. We may assume k=1k = 1, since the distance between the words is kk times the distance between their initial subwords of length gabg a b. Without loss of generality suppose b>ab > a.
For each positive integer mm, look at the subsequence in each word of letters in positions congruent to mm (modg)(\bmod g). Those subsequences (of length aba b) have periods dividing aa and bb respectively. If they are equal, then they are constant (since each letter is equal to those aa and bb before and after it, mod aba b, and (a,b)=1(a, b) = 1). Because a>1a > 1, there is some mm 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 bb repetitions of a subword of length aa and one made up of aa repetitions of a subword of length bb. Looking at the first of those words, for any 1tb1 \leq t \leq b consider the letters in positions t,t+b,,t+(a1)bt, t+b, \ldots, t+(a-1) b. These letters cover every position (mod aa); 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 tt, at least bb letters must change, so the words have distance at least bb.
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 nn. Suppose those words include two distinct words with periods n/an / a and n/bn / b; those words have distance at most 44. If a>4a > 4 or b>4b > 4, we have a contradiction unless aba \mid b or bab \mid a. If a>4a > 4 is the greatest number of repetitions in any of the words (n/an / a is the smallest period), then unless all the numbers of repetitions divide each other there must be words with 22 or 44 repetitions, words with 33 repetitions and all larger numbers of repetitions must divide each other and be divisible by 66.
We now divide into three cases: all the numbers of repetitions may divide either other; or there may be words with (multiples of) 2,32, 3 and 66 repetitions; or all words may have at most 44 repetitions, with at least one word having 33 repetitions and at least one having 22 or 44 repetitions.

Case 1. Suppose all the numbers of repetitions divide each other. Let kk be the least number of repetitions. Consider the word as being divided into kk blocks, each of \ell 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 22; similarly, there are just two blocks, the arrangement is abbaa b b a but transposing the adjacent letters bbb b does not leave the word repetitive.

Case 2. Suppose some word resulting from a transposition is made of (a multiple of) 66 repetitions, some of 33 repetitions and some of 22 repetitions (or 44 repetitions, counted as 22). Consider it as a sequence of 66 blocks, each of length \ell. 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 BAAAAAB A A A A A, 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) BAAAAA,ABAAAAB A A A A A, A B A A A A or AABAAAA A B A A A. In any of these cases, apply the same transposition (that converts between AA and BB) to an AA block adjacent to the BB 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 BCAAAA,ABCAAAB C A A A A, A B C A A A and AABCAAA A B C A A (and considering the letters at the start and end of each block shows BCB \neq C). In all cases, transposing two adjacent distinct letters within an AA block produces a result that cannot have two, three or six repetitions.

Case 3. In the remaining case, all words have at most 44 repetitions, at least one has 33 repetitions and at least one has 22 or 44 repetitions. For the purposes of this case we will think of 44-repetition words as being 22-repetition words. The number of each letter is a multiple of 66, so n12n \geq 12; consider the word as made of six blocks of length \ell.
If the word is already repetitive with 22 repetitions, pattern ABCABCA B C A B C, 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 ABA B is not all one letter, transposing two adjacent letters within ABA B implies that CA=BCC A = B C, so A=B=CA = B = C, the word has pattern AAAAAAA A A A A A but transposing within the initial AAA A means it no longer has 33 repetitions. This implies that ABA B is all one letter, but similarly BCB C must also be all one letter and so the word is constant, a contradiction.
If the word is already repetitive with 33 repetitions, it has pattern ABABABA B A B A B and any transposition leaves it no longer having 33 repetitions, so having 22 repetitions instead. ABAA B A 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 BABB A B; such a transposition affects at most two of the blocks, so A=BA = B, the word has pattern AAAAAAA A A A A A 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.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.