[obm-l] Re: [obm-l] Sequência de Thue-Morse
2012/12/15 Lucas Prado Melo luca...@dcc.ufba.br
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.
Desculpe, me enganei. :(
--
[]'s
Lucas
[obm-l] Re: [obm-l] Sequência de Thue-Morse
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
[obm-l] Re: [obm-l] Sequência de Thue-Morse
2012/12/15 Lucas Prado Melo luca...@dcc.ufba.br
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.
Pronto!
Ou 2^(2m) r - 2^m r tem quantidade ímpar de 1s, ou 2^(2m+1) r - 2^m r tem
quantidade ímpar (este último número teria 1 bit 1 a mais).
Veja:
r = 101
101
- 101
1001011
e
1010
-101
--
10011011
--
[]'s
Lucas
[obm-l] Re: [obm-l] Re: [obm-l] Sequência de Thue-Morse
Demorou uma página inteira de rabiscos aqui pra eu entender, mas foi, hehehe
valeu!
2012/12/15 Lucas Prado Melo luca...@dcc.ufba.br:
2012/12/15 Lucas Prado Melo luca...@dcc.ufba.br
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.
Pronto!
Ou 2^(2m) r - 2^m r tem quantidade ímpar de 1s, ou 2^(2m+1) r - 2^m r tem
quantidade ímpar (este último número teria 1 bit 1 a mais).
Veja:
r = 101
101
- 101
1001011
e
1010
-101
--
10011011
--
[]'s
Lucas
=
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=
