Re: será q ninguém me ajuda?

["Jorge Peixoto Morais" <jorge_peixotom@xxxxxxxxxxx>]

>From: "Igor Castro" <cnaval@ieg.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: "obm lista" <obm-l@mat.puc-rio.br>
>Subject: será q ninguém me ajuda?
>Date: Wed, 20 Dec 2000 00:26:09 -0200
>
>deixei duas duvidas aki na lista so obtive uma resposta, se puderem me 
>ajudar ae eu agradeço... mesmo q seja mto facil pra vcs.. bem em todo caso 
>vo copiar as duvidas
>Primeira:
>No seguinte problema:"Mostre que, pelo menos 30% dos naturais n entre 1 e 
>1.000.000, o primeiro digito de 2^n é 1." Estou com duvida em minha 
>resolução, até porque não encontrei erros em meu raciocinio, mas sei que há 
>porque a "prova" naum está dando certa, gostaria q alguém desse uma olhada 
>e me indicasse o erro, lah vai....
>sendo 2^0=1(n=0 não serve), 2^7=128, 2^10=1024 temos 2 ocorrencias do 
>primeiro algarismo sendo 1 para os 10 primeiro valores de n, jah na 
>sequencia dos 10 proximos temos 3 ocorrencias: 2^14=1..., 2^17=1... e 
>2^20=1.... e na sequencia seguinte também temos 3 ocorrencias(2^24=1... 
>2^27=1.. e 2^30) ou seja, é uma especie de periodo que a cada 10 numeros( 
>começando por 1) temos 3 ocorrencias, então o numero de ocorrencias até 
>1.000.000 é (1.000.000/10)*3 ou seja, o numero de periodos vezes 3, pois em 
>cada periodo temos 3 ocorrencias, o resultado é 300.000 mas devemos 
>diminuir 2 pois a primeira ocorrencia(n=0) não serve e a ultima também 
>não(n = 1.000.000) pois ele diz valores de n ENTRE 1 e 1.000.000, então o 
>numero de ocorrencias seria 300.000 - 2 = 299.998, mas o problema é q este 
>valor é menor que 30% do numero de naturais entre 1 e 1.000.000 q é 
>299.999,4.
>Alguém pode me ajudar? desculpem-me se errei mto feio...
>
>Segunda:
>"Sja n>=1 um inteiro. Temos n lâmpadas alinhadas e numeradas, da esquerda 
>para direita, de 1 a n. Cada lâmpada pode estar acesa ou apagada. a cada 
>segundo, determina-se a lampada apagada de maior numero e inverte-se o 
>estado desta(de acesa para apagada ou de apagada para acesa) e das lampadas 
>posteriores(as lampadas de maior numero).
>a) mostre que em algum momento todas as lampadas estarão acesas(e o 
>processo se encerrará)"
>chamei de 0 uma lampada apagada e 1 uma lampada acesa, portanto teriamos 
>uma sequencia da seguinte forma: ...1010110111... ou ...11011101110. No 
>segundo caso no primeiro segundo a ultima lampada sera invertida(somente 
>ela, pois não há nenhuma posterior) entào no proximo segundo a lampada 
>apagada logo anterior inverterá e todas as posteriores(todas acesas) 
>inverterão tb, então teremos ...11011110000 então no segundo seguinte a 
>ultima inverterá(somente ela) e teremos ...11011110001 e no proximo segundo 
>a penultima lampada(ultima apagada) inverterá e a ultima tb entào teremos 
>...11011110010 e no proximo segundo teremos denovo ...11011110000 o q jah 
>aconteceu e este processo se repetirá infinitamente tanto para o primeiro 
>caso tanto para o segundo...
>Estaria certo isso? anda não localizei o erro, gostaria de uma 
>ajuda..obrigado


NO primeiro caso, voceh errou quando supôs intuitivamente que havia 
períodos. Lembre-se de que a intuição humana, quando se estah trabalhando 
com Matemahtica, soh serve para dar uma ideia do que acontece, e tudo deve 
ser provado formal e rigorosamente. Acontece que 2^4=16, e 2^14=16384, 
(multiplicando por 1024) e 2^24=16777216. Ateh aqui foi verdadeiro, mas 
2^104 comeca com 2. O negocio eh que multiplicar por 1024 (2^10) eh como 
multiplicar por 1000, com um erro pequeno; portanto, o "periodo" existe se 
vc multiplica poucas vezes. Mas ao multiplicar muitas vezes, os erros se 
acumulam, e o "periodo" some.
Para provar o segundo problema, represente uma lampada acesa por "1" e uma 
apagada por "0". Quando voceh troca o estado da ultima lampada marcada com 
"0", o numero que estah representado pelos zeros e uns (na base 2) sempre 
aumenta, pois todass as outras lampadas posteriores estando acesas (e 
portanto sendo apagadas), temos que 2^n-2^(n-1)-2^(n-2)-...-2-1=1.   O 
numero sempre aumenta, e, portanto, chegamos a um ponto em que o numero eh o 
maior numero possivel de se representar na  base 2 com n algarismos. Como 
esse numero eh 11111...11111, as lampadas ficam acesas no final.
O erro no segundo caso estah aqui: imagine que as lampadas "terminem" em 
0111110. Depois teremos 0111111. Entao teremos 1000000. Entao teremos 
1000001. Entao teremos 1000010. Depois, 1000011. Entao, 1000100, com o numeo 
sempre aumentando de uma unidade. Nao hah ciclo nenhum!Perceba que nunca se 
volta aa situacao original; tome alguns exemplos com n pequeno e entenderah 
o seu erro.
_________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.