Assume that for some $\alpha<1$ and for all nutural~$n$ a set $F_n$ of at
most $2^{\alpha n}$ "forbidden" binary strings of length~$n$ is fixed.
Then there exists an infinite binary sequence $\omega$ that does not
have (long) forbidden substrings.

We prove this combinatorial statement by translating it into a
statement about Kolmogorov complexity and compare this proof
with a combinatorial one based on Laslo Lovasz local lemma.

Then we construct an almost periodic sequence with the same
property (thus combines the results from Bruno Durand, Leonid Levin,
Alexander Shen, Complex tilings and Andrei Muchnik, Alexei Semenov
and Maxim Ushakov, Almost periodic sequences).

Both the combinatorial proof and Kolmogorov complexity argument
can be generalized to the multidimensional case.