Oi! Soa fácil, mas procurei na internet, tentei fazer, e não consegui de jeito nenhum. Alguém sabe demonstrar que a sequência de Thue-Morse não possui progressões aritméticas de comprimento infinito?
Funciona assim: a sequência é gerada a partir do número 0, e aí fazemos negação binária (para obter 1) e concatenamos com a sequência acumulada (para obter 0 1). Então fazemos tudo de novo: negação (10) e concatena (01 10). Negação da acumulada (1001) e concatenação (0110 1001). Negação da acumulada (10010110) e concatenação (01101001 10010110), etc. A figurinha da wikipedia mostra direitinho como que faz https://en.wikipedia.org/wiki/File:Morse-Thue_sequence.gif Aí a gente pega a sequência: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (espero que fique alinhado) E pega a sequência dos números com 1 em cima: [1, 2, 4, 7, 8, 11, 13, 14, ...]. Tem que provar que essa sequência não tem nenhuma progressão aritmética de comprimento infinito, isto é, nenhuma subsequência infinita da forma [a, a+n, a+2n, ...] alguma idéia? : ) abraços ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================