I got a fun problem. 


Define the alphabet $\mathcal{A}=\{0,1,2\}$ and the set $\mathcal{A}^{\leq n}=\{ x\_1x\_2\ldots x\_n: x\_i\in \mathcal{A}\}$ of words of length $n,$ for each $n\in\mathbb{N}.$


Suppose that for each $n\in \mathbb{N}$ somebody selects a set $X\_n$ of $2^n$ points of $\mathcal{A}^{\leq n}.$ 


Is it true that there exist a function of linear growth $f:\mathbb{N}\to \mathbb{N},$ a set $\{y^{n}\}\_{n\in K} \subset \mathcal{A}^{\mathbb{N}}$ of infinite cardinality with $K\subset \mathbb{N}$ and for each $n\in K$ a set $Y\_n\subset X\_n$ with cardinality $|Y\_n|\leq f(n)$ such that any sub word of $y^n$ with length $n$ belongs to $Y\_n?$


(My unique intuition is that it is false. And that it should be possible to create by hand the bad sets $X\_n,$ however the proof does not seem clear to me yet. I also think that it could be true a.s., my only guess is to try to use a kind of Borel-Cantelli lemma.)



A problem in symbolic dynamics
An easy procedure to obtain a somewhat stronger result is the following: Consider those words of length $n$ that have exactly one $2$, and this $2$ is not in position $1$. There are $(n-1)2^{n-1}$ such words, which is already more than we need to form $X\_n$. Make an arbitrary selection of $2^n$ such words to define $X\_n$.


Then any $y^n$ that could be considered as a candidate to have subwords from $Y\_n=X\_n$ only (we don't have to make $X\_n$ smaller) has $2$'s in it and thus has subwords with a $2$ in position $1$, which are not in $X\_n$.


