Estou meio sem tempo agora, entao vou colocar minha versao do problema
e minha versao da solucao, que acho mais clara do que a maioria que eu
vi por ai (apesar de ser trabalhosa de explicar).... Tenho certeza que
esta versao eh facilmente adaptavel a outros problemas do tipo, e vira
um algoritmo para botar no computador no caso finito.
Abraco, Ralph.
---///---
ENUNCIADO: Marcos pensa dois números naturais positivos (possivelmente
iguais); a soma destes dois números ele entrega ao matemático Alcides,
enquanto o produto ele entrega à matemática Beatriz. Alcides e Beatriz
conversam sem mostrar seus números um ao outro:
A: “Só com esta soma, eu não sei quais são eram os dois números originais”.
B: “Com este produto, também não dá para descobrir”.
A: “Mesmo assim, continuo sem saber quem eram os números originais”.
B: “E eu continuo sem saber quem eles eram”.
A: “Ah! Neste caso, eu sei quem eram os números originais!”.
B: “Se você agora sabe, então eu também sei!”.
Quais eram os números originais?
SOLUCAO:
Sejam m e n os números que Marcos pensou (digamos, m>=n). O
objetivo eh montar uma tabela com "todas” as possibilidades para m e
n, e "todas" as possiveis conversas em cada caso. Assim, considere a
conversa que Alcides teria com Beatriz em cada caso (denotaremos por
“s” a frase “Eu sei quem são os números m e n” e por “n” a frase
“Ainda não sei quem são m e n”.).
Alcides vê a soma. Se ela for 2 ou 3, Alcides sabe os números (1
e 1 no primeiro caso e 1 e 2 no segundo). Qualquer outra soma faz com
que Alcides fique em dúvida, pois qualquer soma maior que 4 pode ser
alcançada de várias maneiras. A conversa começa então assim em cada
hipotese:
n\m 1 2 3 4 5 6 7 8
1 s s n n n n n n
2 n n n n n n n
3 n n n n n n
4 n n n n n
5 n n n n
6 n n n
7 n n
8 n
A seguir, Beatriz olha o produto. Se o produto for 1, 2 ou um número
primo p, Beatriz saberá que os números são 1 e 1, 1 e 2 ou 1 e p,
respectivamente. Caso contrário, Beatriz ainda é incapaz de decidir
qualquer coisa, pois haverá várias opções e todas elas vêm com um “n”
do Alcides. A tabela da conversa fica assim:
n\m 1 2 3 4 5 6 7 8
1 ss ss ns nn ns nn ns nn
2 nn nn nn nn nn nn nn
3 nn nn nn nn nn nn
4 nn nn nn nn nn
5 nn nn nn nn
6 nn nn nn
7 nn nn
8 nn
Como continuar a tabela? Nos casos “ss”, a conversa acabou. Nos casos
“ns”, Alcides será capaz de deduzir que os números são 1 e p, e
portanto descobri-los a partir da soma que tem em mãos (assim, os
casos correspondentes a 1 e p com p primo maior do que 2 levam à
conversa “nss”). Enfim, em todos os outros casos do tipo “nn” Alcides
vê a soma que tem em mãos e ainda é incapaz de decidir em que “casa”
ele está na tabela acima – com uma exceção: se a soma fosse 4, Alcides
decidiria que (m,n)=(1,3) ou (m,n)=(2,2), e seria capaz de distinguir
entre as duas opções baseado na conversa até aqui (que, no primeiro
caso, é “ns”, mas, no segundo, é “ss”). Assim, com a resposta de
Alcides, a tabela se torna:
n\m 1 2 3 4 5 6 7 8
1 ss ss nss nnn nss nnn nss nnn
2 nns nnn nnn nnn nnn nnn nnn
3 nnn nnn nnn nnn nnn nnn
4 nnn nnn nnn nnn nnn
5 nnn nnn nnn nnn
6 nnn nnn nnn
7 nnn nnn
8 nnn
Agora é a vez de Beatriz. Se o produto for 1, 2 ou primo, já sabemos o
que acontece. Se Beatriz tem algum outro produto em mãos, ela tem de
considerar várias hipóteses, e, como mostra a tabela acima, em todas
elas a conversa foi “nnn” até aqui – com uma exceção: se o produto for
4, Beatriz tem como decidir entre as únicas possibilidades (m,n)=(2,2)
ou (1,4) observando a tabela acima (que indica a conversa “nns” no
primeiro caso e “nnn” no segundo). Então, temos:
n\m 1 2 3 4 5 6 7 8
1 ss ss nss nnns nss nnnn nss nnnn
2 nnss nnnn nnnn nnnn nnnn nnnn nnnn
3 nnnn nnnn nnnn nnnn nnnn nnnn
4 nnnn nnnn nnnn nnnn nnnn
5 nnnn nnnn nnnn nnnn
6 nnnn nnnn nnnn
7 nnnn nnnn
8 nnnn
Agora, Alcides olha suas várias hipóteses e, provavelmente, todas elas
têm a mesma conversa “nnnn” – Alcides será incapaz de decidir quem são
m e n. As poucas exceções são os casos onde alguém já descobriu algum
número. Em particular, se a soma for 5, as únicas possibilidades
(m,n)=(1,4) e (2,3) têm diálogos distintos até aqui! Neste caso,
Alcides diria que sabe quem são os números!
n\m 1 2 3 4 5 6 7 8
1 ss ss nss nnnss nss nnnnn nss nnnnn
2 nnss nnnns nnnnn nnnnn nnnnn nnnnn nnnnn
3 nnnnn nnnnn nnnnn nnnnn nnnnn nnnnn
4 nnnnn nnnnn nnnnn nnnnn nnnnn
5 nnnnn nnnnn nnnnn nnnnn
6 nnnnn nnnnn nnnnn
7 nnnnn nnnnn
8 nnnnn
Enfim, no próximo passo Beatriz não saberá coisa alguma, a menos que o
produto seja 6 (as possibilidades de (m,n)=(1,6) ou (2,3) são
diferenciadas pelo diálogo). A partir daí, nem Alcides nem Beatriz
seriam capazes de alcançar conclusões novas. A tabela final é:
n\m 1 2 3 4 5 6 7 8
1 ss ss nss nnnss nss nnnnnss nss nnnnn...
2 nnss nnnnss nnnnn... nnnnn... nnnnn...
nnnnn... nnnnn...
3 nnnnn... nnnnn... nnnnn... nnnnn...
nnnnn... nnnnn...
4 nnnnn... nnnnn... nnnnn...
nnnnn... nnnnn...
5 nnnnn... nnnnn... nnnnn...
nnnnn...
6 nnnnn... nnnnn... nnnnn...
7 nnnnn... nnnnn...
8 nnnnn...
Como a conversa foi “nnnnss”, os números são 2 e 3.
2009/8/3 Albert Bouskela <bousk...@msn.com>:
> Olá!
>
>
>
> Há alguns dias, foi proposto, nesta Lista, o seguinte problema:
>
>
>
> (SIC)
>
> "Dois homens conhecedores de lógica e extremamente rápidos em fazer cálculos
> mentais, encontram-se na fazenda de um terceiro matemático, também com as
> mesmas características dos outros dois. Este diz que sua fazenda tem formato
> retangular, com lados medindo um número inteiro de quilômetros de 2 a 62.
> Ele dá um papel para o primeiro visitante onde está escrita a área da
> fazenda em quilômetros quadrados e outro para o segundo, com o perímetro da
> fazenda em quilômetros. Segue-se então o diálogo abaixo: Primeiro visitante
> diz: Eu não sei as medidas dos lados da fazenda. Segundo visitante diz: Eu
> sabia que você não saberia as medidas dos lados da fazenda. Primeiro
> visitante diz: Agora eu sei as medidas dos lados da fazenda. Segundo
> visitante diz: Agora eu também sei as medidas dos lados da fazenda. Como
> ambos falaram a verdade, quais as medidas dos lados da fazenda?"
>
> Trata-se de uma variante do chamado “O Problema Impossível”, cujo enunciado
> e solução (em diversas versões) podem ser encontrados nos links que coloco
> no final desta mensagem.
>
>
>
> Sudações,
>
> Albert Bouskela
>
> bousk...@msn.com
>
>
>
> Referências:
>
> http://en.wikipedia.org/wiki/Impossible_Puzzle
>
> http://people.sc.fsu.edu/~burkardt/fun/puzzles/impossible_puzzle.html
>
> ________________________________
> Novo Internet Explorer 8: mais rápido e muito mais seguro. Baixe agora, é
> grátis!
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
