Изменения

Очевидно что <tex>t_{2n}=t_n</tex> и <tex>t_{2n+1}=\varphi(t_n)</tex> для <tex>n \ge geqslant 0</tex>.Пусть существует две равные как строки подстрок строки <tex>T_n</tex>, имеющих пересекающиеся вхождения в <tex>T_n</tex>, тогда <tex>T_n=ucxcxcv</tex>, где <tex>u,c,x,v</tex> {{---}} подстроки строки <tex>T_n</tex>.

Пусть <tex>m=|cx|</tex> и <tex>k=|u|</tex>, тогда <tex>t_{k+j}=t_{k+j+m}</tex> по предположению при <tex>0 \le leqslant j \le leqslant m</tex>.

Рассмотрим наименьшее <tex>m\ge geqslant 1</tex>. Тогда возможны два случая: <tex>m</tex> четно и нечетно:# <tex>m</tex> четно, тогда . #: Тогда пусть <tex>m=2m'</tex>. Рассмотрю два случая: <tex>k</tex> четно или нечетно:#* <tex>k</tex> четно: #*: Пусть <tex>k=2k'</tex>. Так как <tex>t_{k+j}=t_{k+j+m}</tex> при <tex>0 \le leqslant j \le leqslant m</tex>, тогда очевидно, что <tex>t_{2k'+2j'}=t_{2k'+2j'+2m'}</tex> для <tex> 0 \le leqslant j' \le leqslant m'</tex>. Так как <tex>t_{2k'+2j'}=t_{k'+j'}</tex> и <tex>t_{2k'+2j'+2m'}=t_{k'+j'+m'}</tex> очевидно, что <tex>t_{k'+j'}=t_{k'+j'+m'}</tex> для <tex>0 \le leqslant j' \le leqslant m'</tex>. Это противоречие, так как <tex>m</tex> минимально.#* <tex>k</tex> нечетно: #*: Пусть <tex>k=2k'+1</tex>. Тогда, как и в предыдущем случае <tex>t_{2k'+2j'+1}=t_{2k'+2j'+2m'+1}</tex> для <tex>0 \le leqslant j' \le leqslant m'</tex> и тогда <tex>t_{k'+j'}=t_{k'+j'+m'}</tex> для <tex>0 \le leqslant j' \le leqslant m'</tex>, что является опять противоречием из-за минимальности <tex>m</tex>#<tex>m</tex> нечетно, тогда . #:Тогда рассмотрю три случая: <tex>m \ge geqslant 5</tex>, <tex>m=3</tex> и <tex>m=1</tex>. Пусть <tex>b_n=\left\{ \begin{array}{rl}

\end{array} \right.</tex> для <tex>n \ge geqslant 1</tex>. Заметим, что <tex>b_{4n+2}=a</tex> так как <tex>4n+2</tex> и <tex>4n+1</tex> одинаково записываются в двоичной записи, кроме последних двух битов, которые равны <tex>10</tex> и <tex>01</tex> соответственно и значит <tex>t_{4n+2}=t_{4n+1}</tex>. Так же заметим, что <tex>b_{2n+1}=1</tex>, так как <tex>2n+1</tex> и <tex>2n</tex> одинаково записываются в двоичной системе, кроме последнего бита и значит, что <tex>t_{2n+1}=\varphi(t_{2n})</tex>#* <tex>m</tex> нечетно и <tex>m \ge geqslant 5</tex>. #*:Тогда <tex>b_{k+j}=b_{k+j+m}</tex> для <tex>1 \le leqslant j \le leqslant m</tex>. С <tex>m \ge geqslant 5</tex> существует <tex>j</tex>, такое что <tex>k+j=2</tex> по модулю <tex>4</tex>. Тогда для <tex>k+j</tex> точно известно, что <tex>b_{k+j}=0</tex>, но с другой стороны <tex>k+j+m</tex> - нечетно, значит <tex>b_{k+j+m}=1</tex>. Противоречие.#* <tex>m=3</tex>. #*:Аналогично: <tex>b_{k+j}=b_{k+j+3}</tex> для <tex>1 \le leqslant j \le leqslant 3</tex>. Найдем <tex>j</tex>, чтобы <tex>k+j=2</tex> или <tex>k+j=3</tex> по модулю <tex>4</tex>. Если <tex>k+j=2</tex> по модулю <tex>4</tex>, то противоречие получается так же, как в предыдущем пункте. Рассмотрю <tex>k+j=3</tex> по модулю <tex>4</tex>, тогда <tex>b_{k+j}=1</tex>, но <tex>b_k+j+3=0</tex>. Это опять противоречие.#* <tex>m=1</tex>. #*:Тогда <tex>t_k=t_{k+1}=t_{k+2}</tex> из чего следует, что <tex>t_{2n}=t_{2n+1}</tex> для <tex>n=k/2</tex>, но <tex>t_{2n}=\varphi(t_{2n+1}) \ne t_{2n+1}</tex>. Противоречие.