Let
be a positive integer, and let
be an infinite periodic word, consisting of just letters
and/or
. Suppose that the minimal period
of
is greater than
.
A finite nonempty word
is said to appear in
if there exist indices
such that
. A finite word
is called ubiquitous if the four words
,
,
, and
all appear in
. Prove that there are at least
ubiquitous finite nonempty words.
Proposed by Grigory Chelnokov, Russia
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![W = \ldots x_{-1}x_0x_1x_2 \ldots](/media/m/9/8/3/983ff56ce18a909af6df3a3235b7426d.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
![N](/media/m/f/1/9/f19700f291b1f2255b011c11d686a4cd.png)
![W](/media/m/2/c/4/2c4aa0f61279d74f16a59bcde17578ef.png)
![2^n](/media/m/8/e/a/8ea40429bb1e68f68f9e7a97fd5351f7.png)
A finite nonempty word
![U](/media/m/d/f/a/dfa3ccb1bb2d14869d77a98d0d2baf97.png)
![W](/media/m/2/c/4/2c4aa0f61279d74f16a59bcde17578ef.png)
![k \leq \ell](/media/m/3/7/e/37e07a693888e580d8d255174b672c5b.png)
![U=x_k x_{k+1} \ldots x_{\ell}](/media/m/8/3/a/83ace0284c807ba88e6896f2ad2651cb.png)
![U](/media/m/d/f/a/dfa3ccb1bb2d14869d77a98d0d2baf97.png)
![Ua](/media/m/b/8/c/b8c6751d67381221f5b5b21525ebbbaf.png)
![Ub](/media/m/6/5/0/65025681e4818a86709ff2a375363af3.png)
![aU](/media/m/a/c/5/ac500f8bb1fe4830f425bb629a620963.png)
![bU](/media/m/3/8/3/383c8f8000acd4a77e87d2e3bff2e489.png)
![W](/media/m/2/c/4/2c4aa0f61279d74f16a59bcde17578ef.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
Proposed by Grigory Chelnokov, Russia