IMO Shortlist 2011 problem C6

  Avg: 3,0
  Avg: 8,0
Dodao/la: arhiva
23. lipnja 2013.
Let n be a positive integer, and let W = \ldots x_{-1}x_0x_1x_2 \ldots be an infinite periodic word, consisting of just letters a and/or b. Suppose that the minimal period N of W is greater than 2^n.

A finite nonempty word U is said to appear in W if there exist indices k \leq \ell such that U=x_k x_{k+1} \ldots x_{\ell}. 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.

Proposed by Grigory Chelnokov, Russia
Izvor: Međunarodna matematička olimpijada, shortlist 2011