  A sequence is nonrepetitive if it does not contain two adjacent identical
blocks. The remarkable construction of Thue asserts that 3 symbols are enough
to build an arbitrarily long nonrepetitive sequence. It is still not settled
whether the following extension holds: for every sequence of 3-element sets
$L_1,..., L_n$ there exists a nonrepetitive sequence $s_1, ..., s_n$ with
$s_i\in L_i$. Applying the probabilistic method one can prove that this is true
for sufficiently large sets $L_i$. We present an elementary proof that sets of
size 4 suffice (confirming the best known bound). The argument is a simple
counting with Catalan numbers involved. Our approach is inspired by a new
algorithmic proof of the Lov\'{a}sz Local Lemma due to Moser and Tardos and its
interpretations by Fortnow and Tao. The presented method has further
applications to nonrepetitive games and nonrepetitive colorings of graphs.

Combinatorics;Discrete Mathematics