2012/12/15 Pedro Angelo <pedro.fon...@gmail.com> > 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? : ) >
O que se pode perceber dessa sequência é que a quantidade dos bits 1 da representação binária dos números é sempre ímpar. Assim se tivermos uma PA infinita, {a+ir} contida na sequência, essa invariante se mantem. E aí está o problema! Seja 2^m > a, e 2^m > r. Temos que a+2^m r, pertence à sequência. Como 'a' pertence à sequência também, o número de bits 1 de 'a' é ímpar e de 'r' é par para que a+2^m r tenha uma quantidade ímpar de 1s. Mas aí a+2^m r + 2^(2m) r (também da sequência) teria uma quantidade par de 1s, uma contradição. -- []'s Lucas