Let be a positive integer, and let there be given an infinite periodic string , where can be the letter or for all integers , and the minimal period of is greater than (that is, for all , and no such can be smaller). We call a nonempty substring of length mutually beneficial (abbreviated as FU for "mutually beneficial") if all four of the strings occur in . Prove that: contains at least FU substrings.
Solution
For a string , let denote the length of that string. All substrings mentioned here are nonempty and of length , and the given can be regarded as a circular string of length , namely ; since such is finite, we can define the multiplicity of any substring occurring in as
where all subscripts are taken (mod ). In other words, the string occurs in if and only if . Moreover we have the equalities
for any string of length . So when , we only need to show: . For we treat it specially: if some has , then there exist such that
however this would force for all , giving rise to a new period , a contradiction! So any string of length must have , so only one of and occurs in (going around the circle once more and adding one more letter, that letter being the last letter of ), hence cannot be FU.
PS. Here and have length , so and are meaningless.
Another simple but important observation is
(*): since , at least one of and is greater than .
For each , define
Then take such that its length is the longest among those in . By (*), is nonempty, so must exist.
Now fix a . Since is longer than , by the definition we must have ; however we also need to be satisfied, so . By the same reasoning we also get . Applying the same reasoning again we get . We conclude that is FU.
Next we must show that these values of are all distinct from each other: if , that is , then at least one of and would be greater than . Since and are longer than , this again contradicts the definition of ! So we obtain , which means these values of are all distinct. This completes the proof!