Q13 Matemática  (IMO Shortlist 2011)

Seja $n$ um inteiro positivo e seja $W=\dots x_{-1}{x}_0{x}_1{x}_2\dots$ uma palavra periódica infinita, consistindo apenas de letras $a$ e/ou $b$. Suponha que o período mínimo $N$ de $W$ seja maior que $2^n$. Diz-se que uma palavra finita não vazia $U$ aparece em $W$ se existirem índices $k\le \ell$ tais que $U=x_k{x}_{k+1}\dots x_{\ell }$. Uma palavra finita $U$ é chamada de onipresente se as quatro palavras $Ua$, $Ub$, $aU$ e $bU$ aparecerem em $W$. Prove que existem pelo menos $n$ palavras finitas não vazias onipresentes. Proposto por Grigory Chelnokov, Rússia