Maths Olympiad Prep

Library / /185 of 397

Combinatorics Difficulty 5.8 AIME, harder Prove it Taiwan

Let nn be a positive integer, and let there be given an infinite periodic string W=x1x0x1x2W = \dots x_{-1}x_0x_1x_2\dots, where xix_i can be the letter aa or bb for all integers ii, and the minimal period pp of WW is greater than 2n2^n (that is, xi=xi+px_i = x_{i+p} for all ii, and no such pp can be smaller). We call a nonempty substring UU of length p\le p mutually beneficial (abbreviated as FU for "mutually beneficial") if all four of the strings aU,bU,Ua,UbaU, bU, Ua, Ub occur in WW. Prove that: WW contains at least nn FU substrings.

Solution

For a string UU, let U|U| denote the length of that string. All substrings mentioned here are nonempty and of length p\le p, and the given WW can be regarded as a circular string of length pp, namely x0x1x2xp1x_0x_1x_2\dots x_{p-1}; since such WW is finite, we can define the multiplicity of any substring U=a0a1ak1U = a_0a_1\dots a_{k-1} occurring in WW as
m(U)={i0ip1 and a0a1ak1=xixi+1xi+k1} m(U) = |\{i|0 \le i \le p-1 \text{ and } a_0a_1\cdots a_{k-1} = x_i x_{i+1} \cdots x_{i+k-1}\}|
where all subscripts are taken (mod pp). In other words, the string UU occurs in WW if and only if m(U)1m(U) \ge 1. Moreover we have the equalities
m(U)=m(aU)+m(bU)=m(Ua)+m(Ub), m(U) = m(aU) + m(bU) = m(Ua) + m(Ub),
for any string UU of length p1\le p-1. So when Up1|U| \le p-1, we only need to show: m(aU),m(bU),m(Ua),m(Ub)1m(aU), m(bU), m(Ua), m(Ub) \ge 1. For U=p|U|=p we treat it specially: if some U=a0a1ap1U = a_0a_1\cdots a_{p-1} has m(U)2m(U) \ge 2, then there exist 0i<jp10 \le i < j \le p-1 such that
a0a1ap1=xixi+1xi+k1=xjxj+1xj+k1; a_0a_1\cdots a_{p-1} = x_i x_{i+1} \cdots x_{i+k-1} = x_j x_{j+1} \cdots x_{j+k-1};
however this would force xk=xji+kx_k = x_{j-i+k} for all k=0,1,,p1k = 0, 1, \dots, p-1, giving rise to a new period ji<pj-i < p, a contradiction! So any string of length pp must have m(U)1m(U) \le 1, so only one of aUaU and bUbU occurs in WW (going around the circle once more and adding one more letter, that letter being the last letter of UU), hence UU cannot be FU.
PS. Here aUaU and bUbU have length p+1p+1, so m(aU)m(aU) and m(bU)m(bU) are meaningless.
Another simple but important observation is
(*): since p>2kp > 2^k, at least one of m(a)m(a) and m(b)m(b) is greater than 2n12^{n-1}.
For each k=0,1,,n1k = 0, 1, \dots, n-1, define
Ωk={VV is a substring of W of length p1, and m(V)>2k}. \Omega_k = \{V | V \text{ is a substring of } W \text{ of length } \le p-1, \text{ and } m(V) > 2^k \}.
Then take UkΩkU_k \in \Omega_k such that its length is the longest among those in Ωk\Omega_k. By (*), Ωk\Omega_k is nonempty, so UkU_k must exist.
Now fix a k{0,1,,n1}k \in \{0, 1, \dots, n-1\}. Since aUkaU_k is longer than UkU_k, by the definition we must have m(aUk)2km(aU_k) \le 2^k; however we also need 2k<m(Uk)=m(aUk)+m(bUk)2^k < m(U_k) = m(aU_k) + m(bU_k) to be satisfied, so m(bUk)0m(bU_k) \ne 0. By the same reasoning we also get m(bUk)0m(bU_k) \ne 0. Applying the same reasoning again we get m(Uka),m(Ukb)0m(U_ka), m(U_kb) \ne 0. We conclude that UkU_k is FU.
Next we must show that these nn values of UkU_k are all distinct from each other: if UkΩk+1U_k \in \Omega_{k+1}, that is m(Uk)>2k+1m(U_k) > 2^{k+1}, then at least one of m(aUk)m(aU_k) and m(bUk)m(bU_k) would be greater than 2k2^k. Since aUkaU_k and bUkbU_k are longer than UkU_k, this again contradicts the definition of UkU_k! So we obtain 20<m(U0)21<m(U1)22<<2n1<m(Un1)2^0 < m(U_0) \le 2^1 < m(U_1) \le 2^2 < \dots < 2^{n-1} < m(U_{n-1}), which means these nn values of UkU_k are all distinct. This completes the proof!

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 translated into English from zh; metadata (topic, difficulty) added by this project.