[obm-l] Re: [obm-l] Re: [obm-l] Questão do cartaz

[Carlos César de Araújo <cca@xxxxxxxxxxxxxxxxxxxxxx>]

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" <euraul@terra.com.br>
To: <obm-l@mat.puc-rio.br>
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 <cca@gregosetroianos.mat.br>
> To: <obm-l@mat.puc-rio.br>
> 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" <euraul@terra.com.br>
> > To: <obm-l@mat.puc-rio.br>
> > 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 <cca@gregosetroianos.mat.br>
> > > To: <obm-l@mat.puc-rio.br>
> > > 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
=========================================================================