1. O que é Sequência de Thue-Morse? Explique sua construção.

Passo 1

O enunciado pede para definirmos a sequência de Thue–Morse e explicarmos como ela é construída. O conteúdo envolve sequências recursivas em teoria de palavras e a paridade de dígitos em representação binária. Vamos usar tanto uma definição recursiva quanto uma via paridade de bits para mostrar a construção.

Passo 2

Definição recursiva. Começamos com
T_{0} = 0.
Dado o bloco T_{n}, definimos T_{n+1} como
T_{n+1} = T_{n}\,\|\,\overline{T_{n}},
onde “ \|” significa concatenação de cadeias e \overline{T_{n}} é o complemento bit a bit de T_{n} (trocamos 0 por 1 e 1 por 0). Assim, os primeiros blocos são:
T_{0} = 0, \quad T_{1} = 0\,\|\,1 = 01, \quad T_{2} = 01\,\|\,10 = 0110, \quad T_{3} = 0110\,\|\,1001 = 01101001,
e assim por diante.

Passo 3

Sequência infinita. A sequência de Thue–Morse T é o limite
T = \lim_{n\to\infty} T_{n},
isto é, a cadeia infinita
T = 0110100110010110\cdots.
Ela tem propriedades interessantes, como evitar subcadeias do tipo www (“cubos”) e “overlaps”.

Passo 4

Definição via paridade de bits. Outra forma equivalente de definir o n-ésimo termo t_{n} de T é tomar a soma dos dígitos 1 na representação binária de n e computar essa soma módulo 2. Formalmente, se \mathrm{popcount}(n) é o número de 1’s em n, então
t_{n} = \mathrm{popcount}(n)\bmod 2.
Por exemplo, para n=5, escrevemos 5 em binário como 101, a soma dos dígitos 1 é 2, e 2\bmod 2=0, então t_{5}=0. Isso gera exatamente a mesma sequência vista acima.

Resposta

A sequência de Thue–Morse é a sequência infinita binária que se obtém recursivamente por
T_{0}=0, \quad T_{n+1}=T_{n}\,\|\;\overline{T_{n}},
ou, equivalentemente, pelo critério
t_{n} = \bigl(\text{número de dígitos 1 na representação binária de }n\bigr)\bmod 2.úíçãá
Os primeiros termos são
0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,\dots
e a sequência resultante evita “cubos” e sobreposições em teoria de palavras.

Exercícios relacionados