Ol�, Raul. Hoje � tarde, ap�s assistir ao Matrix Reloaded, li com aten��o a solu��o do problema que lhe causou d�vidas, e cujo enunciado �:
"Qual � o d�gito das unidades de 7^7^7^7^...^7, onde aparecem 2002 setes?" Seguem-se os meus esclarecimentos. (Espero que realmente esclare�am!) Sua d�vida inicial foi: como interpretar uma tal torre de pot�ncias? Em minha resposta nesta lista, eu disse que, pela conven��o mais aceita, a associa��o se faz pela DIREITA (ou, em termos da nota��o tradicional, "de cima" para baixo). Na mensagem seguinte, surgiu uma nova d�vida: voc� afirmou que essa interpreta��o n�o lhe parecia compat�vel com a resolu��o apresentada. Ap�s examinar, hoje, a solu��o, verifiquei que foi utilizada a conven��o mais aceita. Eles realmente trataram a opera��o ^ como associativa � DIREITA. Creio ser interessante lhe mostrar onde ocorreu o seu engano ao ler a solu��o, e para este fim farei uma descri��o do racioc�nio ali apresentado numa linguagem diferente (e com uma pequena modifica��o). <observa��o 1> Torres de pot�ncias levam a n�meros ENORMES, para os quais Donald Knuth imaginou algumas nota��es convenientes. Assim, a torre de pot�ncias m^m^...^m, com m repetido n vezes � denota por m||n, onde aqui escrevo "|" em vez da seta para cima (tal como proposto por Knuth). Como eu disse, a potencia��o � associativa � direita, e com essa conven��o � f�cil ver que n>=2 ==> m||n = m^(m||(n-1)). Com essa nota��o, o nosso problema fica: Qual � o d�gito das unidades de 7||2002? Alternativamente: Qual � o resto de 7||2002 por 10? Observe como esse n�mero � grande: 7||2=7^7^7, por exemplo, possui 1+floor(7^7log_10(7))=695.975 algarismos decimais! <fim da observa��o 1> A solu��o que voc� leu come�a mostrando, a partir de casos particulares, como a seq��ncia dos restos das pot�ncias de 7 por 100 � peri�dica, com per�odo 1,7,43,49 <observa��o 2> Esse fen�meno � bem estudado nos textos cl�ssicos sobre congru�ncias, nos quais se mostra que, mais geralmente, se a � primo com m, ent�o a seq��ncia das pot�ncias a^k (k>0) � peri�dica m�dulo m. O comprimento do per�odo � uma fun��o aritm�tica bem conhecida. No software Mathematica, por exemplo, essa fun��o � indicada por MultiplicativeOrder[a,m] ou, em nota��o tradicional, por ord_m(a). Essa fun��o comparece, por exemplo, no c�lculo do per�odo de d�zimas. <fim da observa��o 2> Indubitavelmente, foi nesse come�o que voc� se enganou e se concentrou na seq��ncia 7^7, (7^7)^7, ..., cujos restos TAMB�M s�o peri�dicos! Mas deixemos este caminho de lado. O passo seguinte (da solu��o) se ap�ia em dois fatos que PODERIAM ter sido destacados assim: (1) 7^7 = 43 mod 100 (2) x=43 mod 100 =>7^x=43 mod 100 Fica ent�o f�cil provar, por indu��o a partir de 7||n = 7^(7||(n-1)) (veja observa��o 1) que n>=2 ==> 7||n = 43 mod 100 ==> 7||n = 3 mod 10 That's all! Considera��es Finais (reflex�es pedag�gicas) Bem, Raul, talvez voc� ache que esta apresenta��o seja elaborada demais. Que chances teria um estudante de matem�tica, ainda que talentoso, de ATINAR com certas id�ias e caminhos, os quais se apresentam com mais naturalidade somente para aqueles que possuem alguma sofistica��o matem�tica? No caso acima, por exemplo, o que dizer de um estudante que nada sabe sobre congru�ncias? Meu ponto de vista � que muitos desses problemas s� deveriam ser realmente atacados com as ferramentas que foram JUSTAMENTE CRIADAS para tornar suas solu��es mais mec�nicas, formaliz�veis e compreens�veis. Claro, voc� n�o precisa dominar congru�ncias para resolver certos problemas de Teoria dos N�meros, da mesma forma que n�o precisa estudar L�gica Matem�tica para entender demonstra��es. Mas considero algo "trapaceiro" utilizar uma teoria avan�ada T para descobrir um problema P e depois reenunciar P numa linguagem "inferior" e apresent�-lo como desafio para algu�m que desconhece T, com o suposto objetivo de atestar o "talento matem�tico". Lembre-se: a matem�tica � volumosa demais para a curta vida de um ser humano. Portanto, estudemos e n�o percamos tempo reinventando a roda. Carlos C�sar de Ara�jo Matem�tica para Gregos & Troianos www.gregosetroianos.mat.br Belo Horizonte, MG ----- Original Message ----- From: "Raul" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Saturday, May 31, 2003 12:57 AM Subject: [obm-l] Re: [obm-l] Quest�o do cartaz > Ol� Carlos, > na quest�o original n�o tem par�teses e nem pede para adotar outra > conven��o. � a quest�o 20 da prova OBM 2002 do n�vel 3. Pode-se verificar o > enunciado e a resolu��o no site www.obm.org.br, no link provas. > Queria saber se na resolu��o devemos adotar outra conven��o ou eu n�o > entendi direito. > Obrigado pela aten��o, > Raul > > ----- Original Message ----- > From: Carlos C�sar de Ara�jo <[EMAIL PROTECTED]> > To: <[EMAIL PROTECTED]> > Sent: Friday, May 30, 2003 1:21 AM > Subject: [obm-l] Re: [obm-l] Re: [obm-l] Quest�o do cartaz > > > > Ol�, Raul. Infelizmente, com o enorme volume de trabalho por aqui, ainda > n�o > > pude examinar o enunciado original do seu problema. Poderia me fornecer > > algum link? No enunciado original, a torre de pot�ncias � escrita sem > > par�nteses? O texto menciona alguma conven��o a ser usada? At� que eu > saiba > > mais, prefiro me omitir. Entretanto, a julgar pela sua descri��o da > > resolu��o, foi mesmo utilizada a associa��o pela esquerda (com base num > fato > > simples sobre congru�ncias). > > > > Eu gostaria de sugerir alguns artigos para consulta (enquanto vasculho > parte > > da minha biblioteca antes de sair). Torres de pot�ncias aparecem em > > discuss�es matem�tica e l�gicas (teoria da recurs�o, fun��o de Ackermann, > > funcionais de Hilbert, etc.) H� alguns anos, coletei v�rios artigos > > interessantes no American Mathematical Monthly. Eis alguns: > > > > [1] J. Riordan - A note on Catalan numbers, AMM, 1973, pp. 904-906; > > [2] R.K.Guy and J. L. Selfridge - The nesting and roosting habits of the > > laddred parenthesis, AMM, 1973, pp.868-876. > > [3] J. Spencer - Large numbers and unprovable theorems, AMM, 1983, pp. > > 669-675. > > > > Veja tamb�m sobre a nota��o de setas de Knuth em > > > > http://mathworld.wolfram.com/ArrowNotation.html > > > > e siga as refer�ncias ali mostradas. Quando tiver tempo, e se houver > > interesse, enviarei mais refer�ncias bibliogr�ficas que j� estudei. > > > > Carlos C�sar de Ara�jo > > Matem�tica para Gregos & Troianos > > www.gregosetroianos.mat.br > > Belo Horizonte, MG > > > > ----- Original Message ----- > > From: "Raul" <[EMAIL PROTECTED]> > > To: <[EMAIL PROTECTED]> > > Sent: Thursday, May 29, 2003 7:29 PM > > Subject: [obm-l] Re: [obm-l] Quest�o do cartaz > > > > > > > Obrigado Carlos pela resposta bem elaborada. Mas agora ent�o me > parece > > > errada a resolu��o da quest�o do cartaz que pergunta o �ltimo d�gito de > > > 7^7^7^7...(onde aparecem 2002 setes). Na resolu��o que acompanha o > > gabarito > > > � feita a an�lise que 7^7 termina em 3, ao elevar a 7 novamente termina > em > > > 7. Assim � feita a conclus�o que ficar� alternando 3 e7 ao continuar > > > elevando. Como tem 2002 n�meros 7, conclui-se que terminar� em 3. N�o > est� > > > indo contra a conven��o mais aceita � que ^ � associativa � direita? > > > Agrade�o aos que quiserem realmente ajudar. > > > Raul > > > > > > ----- Original Message ----- > > > From: Carlos C�sar de Ara�jo <[EMAIL PROTECTED]> > > > To: <[EMAIL PROTECTED]> > > > Sent: Thursday, May 29, 2003 2:05 PM > > > Subject: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Quest�o do cartaz > > > > > > > > > > Raul, > > > > > > > > Voc� pergunta: > > > > > > > > > Uma d�vida ent�o: est� errado ensinar que 2^3^2=2^9 por n�o haver > > > > > par�ntesis? > > > > > > > > Repetindo o que eu disse, a conven��o mais aceita � que ^ � > associativa > > � > > > > direita, de modo que 2^3^2=2^(3^2)=2^9=512. Portanto, ensinar que > > > > "2^3^2=2^9" � simplesmente uma forma de aderir a essa conven��o. A > > maioria > > > > dos softwares com os quais trabalho no meu site seguem essa regra. Uma > > > > exce��o � o Excel: se voc� digitar > > > > > > > > =2^3^2 > > > > > > > > numa c�lula e pressionar <Enter>, ver� 64 como resultado. Isto mostra > > que > > > o > > > > Excel decodifica a express�o associando pela ESQUERDA. > > > > > > > > >Algumas apostilas de cursinho e alguns livros que consultei > > > > > trazem exerc�cios que diferenciam (2^3)^2=2^6 do exemplo anterior. > > > > > > > > Sim, a express�o (2^3)^2 tem que ser diferenciada de 2^3^2=2^(3^2) > > porque, > > > > como eu ressaltei, a opera��o ^ n�o � associativa. Onde est� a d�vida? > > Era > > > > isso mesmo que voc� queria dizer? > > > > > > > > Infelizmente, quest�es SINT�TICAS e METODOL�GICAS como essas n�o s�o > > > > discutidas SISTEMATICAMENTE nos cursos "tradicionais" de matem�tica. > > (Isto > > > > n�o acontece em cursos de L�gica Matem�tica ou de Programa��o de > > > > Computadores.) Conseq�entemente, os alunos aprendem a fazer c�lculos e > > > > resolver problemas padronizados, mas n�o aprendem a pensar e CRITICAR > > > fatos > > > > estabelecidos. T�o importante quanto a arte de resolver problemas � a > > > > capacidade de organizar o conhecimento em um corpo coeso de fatos e > > > > CONVEN��ES baseadas em julgamentos inteligentes. Matem�ticos n�o s�o > > > apenas > > > > resolvedores de problemas; s�o, tamb�m, construtores de teorias. Aqui > > vai > > > um > > > > exerc�cio para voc� treinar a sua observa��o e senso cr�tico: por que > se > > > > convenciona que a multiplica��o tem preced�ncia sobre a adi��o? Isto > �, > > > por > > > > que se convenciona que "a + b*c = a+(b*c)" e n�o que "a + b*c = > > (a+b)*c"? > > > > PENSE sobre isto e poder� chegar � resposta por si mesmo (como eu > > pr�prio > > > > cheguei). > > > > > > > > Carlos C�sar de Ara�jo > > > > Matem�tica para Gregos & Troianos > > > > www.gregosetroianos.mat.br > > > > Belo Horizonte, MG > > > > > > > > > ----- Original Message ----- > > > > > > Raul, > > > > > > > > > > > > A opera��o bin�ria (a,b)--> a^b n�o � associativa, de modo que, em > > > > > > princ�pio, a express�o > > > > > > > > > > > > a^b^c > > > > > > > > > > > > � amb�gua: significaria (a^b)^c OU a^(b^c)? Contudo, repare que > uma > > > > dessas > > > > > > alternativas leva a um resultado bem definido: (a^b)^c=a^(bc). > Como > > > > > > conseq��ncia (e abreviando um pouco o que poderia ser uma longa > > > > discuss�o > > > > > > metodol�gica), convencionou-se que a opera��o (a,b)--> a^b � > > > ASSOCIATIVA > > > > � > > > > > > DIREITA. Ou seja, por defini��o, > > > > > > > > > > > > a^b^c = a^(b^c). > > > > > > > > > > > > Em particular, > > > > > > > > > > > > 7^7^7 = 7^(7^7) = 7^49. > > > > > > > > > > > > PS: Quest�es como essas s�o discutidas detalhadamente num dos > > > cap�tulos > > > > do > > > > > > meu CD-ROM "N�meros" (cujas vendas, no momento, est�o paralisadas > � > > > > espera > > > > > > de acordos vi�veis com distribuidoras em territ�rio nacional.) > > > > > > > > > > > > Carlos C�sar de Ara�jo > > > > > > Matem�tica para Gregos & Troianos > > > > > > www.gregosetroianos.mat.br > > > > > > Belo Horizonte, MG > > > > > > > > > > > > ----- Original Message ----- > > > > > > > > > > > > Ol� a todos. > > > > > > No cartaz da OBM 2003 h� uma quest�o para ensino m�dio que > > > pergunta > > > > > qual > > > > > > o �ltimo algarismo de sete elevado a sete elevado a sete...(com > 2002 > > > > > setes). > > > > > > Acontece que n�o h� par�ntesis entre os expoentes. Na resolu��o da > > > > quest�o > > > > > > eu achei que tudo foi feito como se houvesse par�ntesis. Em resumo > > > sete > > > > > > elevado a sete elevado a sete foi tratado como sete elevado a 49 e > > n�o > > > > > como > > > > > > sete elevado a 823543. Quero saber onde eu estou errado. > > > > > > Agrade�o desde j�. > > > > > > Raul > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > ========================================================================= > > > > > > Instru��es para entrar na lista, sair da lista e usar a lista em > > > > > > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > > > > > > > > > > > > ========================================================================= > > > > > > > > > > > > Esta mensagem foi verificada pelo E-mail Protegido Terra. > > > > > > Scan engine: VirusScan / Atualizado em 28/05/2003 / Vers�o: 1.3.13 > > > > > > Proteja o seu e-mail Terra: > http://www.emailprotegido.terra.com.br/ > > > > > > > > > > > > > > > > > > > > ========================================================================= > > > > > Instru��es para entrar na lista, sair da lista e usar a lista em > > > > > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > > > > > > > > > ========================================================================= > > > > > > > > > > ========================================================================= > > > > Instru��es para entrar na lista, sair da lista e usar a lista em > > > > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > > > > > > ========================================================================= > > > > > > > > Esta mensagem foi verificada pelo E-mail Protegido Terra. > > > > Scan engine: VirusScan / Atualizado em 28/05/2003 / Vers�o: 1.3.13 > > > > Proteja o seu e-mail Terra: http://www.emailprotegido.terra.com.br/ > > > > > > > > > > > ========================================================================= > > > Instru��es para entrar na lista, sair da lista e usar a lista em > > > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > > > > ========================================================================= > > > > ========================================================================= > > Instru��es para entrar na lista, sair da lista e usar a lista em > > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > > ========================================================================= > > > > Esta mensagem foi verificada pelo E-mail Protegido Terra. > > Scan engine: VirusScan / Atualizado em 28/05/2003 / Vers�o: 1.3.13 > > Proteja o seu e-mail Terra: http://www.emailprotegido.terra.com.br/ > > > > ========================================================================= > Instru��es para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > ========================================================================= ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================
