IMO 2011 Shortlist C6
Let n be a positive integer and let W = ...x−1x0x1x2 ... be an infinite periodic word consisting of the letters a and b....
Category: Combinatorics
Problem
Let n be a positive integer and let W = ...x−1x0x1x2 ... be an infinite periodic word consisting of the letters a and b. Suppose that the minimal period N of W is greater than 2n . A finite nonempty word U is said to appear in W if there exist indices k ≤ ℓ such that U = xkxk+1 ...xℓ. A finite word U is called ubiquitous if the four words Ua, Ub, aU, and bU all appear in W. Prove that there are at least n ubiquitous finite nonempty words.