Infinite sequence of $3$ numbers with nonrepeated parts. I am thinking about this problem. Can we construct infinite sequence with $3$ numbers so that no repeated parts exist in it? There should not be subsequence with $2k$ numbers so that its left and right parts are the same. This is such a sequence $1 0 1 2 0 2 1 0 2 0 1 0 2 1 0 1 2 0 2 1 $. The question is can we give a algorithm to continue it infinity. It is clear that we can't do it if there are only $2$ numbers.
 A: There is a result by Thue (1906) to explicitly construct such non-repetitive sequences of any length. Starting from any initial nonrepetitive sequence, e.g. just the single $(1),$ one repeatedly (simultaneously) replaces each occurrence of $1,2,3$ in the sequence at a given stage as follows:
$$1 \to 12312, \\ 2 \to 131232, \\ 3 \to 1323132.$$
According to the article here Thue's construction can be shown to produce a nonrepetitive sequence from any given one, that is, at each stage the next one is nonrepetitive provided the one before is.
It seems that (at least starting with initial string $(1),$) the continual replacements make the initial part of the string begins to settle down, but I haven't thought much about "proving" that. [Actually I don't now think I can show it, it may not be true] The linked paper is about a different approach for producing these sequences, and only refers to Thue's result in the first page or two.
A: An inductive proof can be found in http://goo.gl/OSzV1O (problem 124,b).
A: Here is a more symmetric construction, with proof:
Inductively, we will construct the ternary words $W_{13^k}$ according to the following rules:
first, we colour $W_1$ with $0$. Given $W_{13^k}$, we substitute every letter $i\in\{0,1,2\}$ by the word $A_i$, where
$$\begin{array}{cc}
 A_0&=0121021201210\\
 A_1&=1202102012021\\
 A_2&=2010210120102
 \end{array}$$
By inflating in this way we obtain the ternary word $W_{13^{k+1}}$. The claim is that at each stage, this $W_{13^k}$ has no repeated parts.
To prove the claim, suppose we have the counterexample $WW\subset W_{13^k}$, where $W$ is a word. We can choose $k$ to be minimal. This implies that $13$ does not divide $|W|$: otherwise the sequence of $A_i$ which cover $WW$ is repetitive. This implies we have found a counterexample in $W_{13^{k-1}}$, contradicting the minimality of $k$.
We now consider two cases.
Case 1. Suppose there is some $A_i$ such that $A_i\subset W$. Note that if $U=abcbacbcabcba$ for $\{a,b,c\}=\{0,1,2\}$ such that $U\subset A_jA_k$ (where $j,k$ are distinct numbers in $\{0,1,2\}$), then $U=A_j$ or $U=A_k$ (see example below for an illustration). Therefore if we consider the subword in the second appearance of $W$ that corresponds to the $A_i$, it must agree with another word $A_j$. But this implies $13$ divides $|W|$, which we already discussed.
example: finding subwords $abcbacbcabcba$ in $A_0A_1$:
\begin{array}{ccccccccccccccccccccccccccc}
 &0&1&2&1&0&2&1&2&0&1&2&1&0&1&2&0&2&1&0&2&0&1&2&0&2&1\\
 & & & & &a&b&c&b&a&c&b&c&a&b&c&b&a& & & & & & & & &
 %\\
 %& & & & & & & &a&b&c&b&a&c&b&c&a&b&c&b&a& & & & &
 \end{array}
Case 2. Suppose $A_i\not\subset W$ for all $i$, or equivalently $|W|\le 24$. To complete the proof for the claim, it is sufficient to show that all even subwords of length up to 48 of some $A_{i_1}A_{i_2}A_{i_3}A_{i_4}A_{i_5}$ are non-repetitive. This is a finite problem and we can check these remaining (less than 30000) possibilities.$\square$
Used definitions: 


*

*A word is a non-empty sequence of symbols.

*If we have two words $W,U$, we denote $WU$ as the concatenation of the two words.

*$W\subset U$ or $W$ is a subword of $U$ if we can find a sequence of consecutive symbols in $U$ that is $W$.

*A word $U$ is repetitive if it contains a subword $WW$ where $W$ is a word.

