[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] RE: [obm-l] Problemão que circulou em outra lista
As ideias do Rogerio estao no caminho certo... Agora eh soh organizar
tudo. Eu conheco esse problema sem a restricao do "menor que 99", mas o
enunciado costuma deixar claro que sao dois numeros inteiros POSITIVOS --
creio ser esta a ideia, nao? Eu costumo fazer assim...
Faca um tabelao mostrando todas as hipoteses para os dois numeros (ou
pense em todos os pontos do plano cujas coordenadas sejam inteiros positivos
(x,y) com x<=y -- como eu disse, vou jogar fora a condicao do 99, pois acho
que nao faz TANTA diferenca na IDEIA). Para cada par (ponto), escreva o
"dialogo" entre Sr. S e Sr. P usando D para "descobri!" e N para "nao
descobri"... Por exemplo, se os numeros iniciais fossem (1,1), teriamos S=2
e P=1. Senhor P ve o produto e diz "D!". Sr. S tambem diz "D!". Em outras
palavras, o par (1,1) leva ao dialogo DD. Assim, na posicao (1,1) eu tenho
"DD".
Bom, agora monte os dialogos letra a letra, assim:
i) O Sr. P ve uma tabela vazia. Se o produto que ele tem for primo (ou 1),
ele sabera quais sao os numeros; senao, ele nao tem como adivinhar. Assim,
ponha "D" (de descobri!) como primeira letra na tabela para todos os pares
da forma (1,p) com p primo (e em (1,1)); nas outras, claramente a primeira
letra do dialogo eh "N" (de Nao descobri!).
ii) O Sr. S olha a tabela, agora separada em dois conjuntos de
possibilidades, aquelas que comecam com D e aquelas que comecam com N. Ele
soh tem a soma, isto eh, ele estah restrito a uma especie de "diagonal" do
tipo x+y=S no tabelao. Ele olha todos os pontos no tabelao com aquela soma,
e percebe que:
-- Em (1,1), Sr. S claramente diz "D" (eh a unica possibilidade) e temos
"DD" -- fim de papo.
-- Em (1,p), idem, pois o Sr. S verah que (1,p) eh o unico par com aquela
soma S particular que comeca por "D", entao ele conclui que os numeor sao 1
e p=S-1. Assim, estas casas levam ao dialogo "DD", e fim de papo (lembre-se
que eu supus x<=y, jah que a ordem nao interessa). Note que nestes casos,
nos aqui de fora nao temos como saber se foi (1,1), ou se foi (1,p), ou que
"p" foi esse.
-- O mesmo ocorre para (2,2); de fato, o Sr. S olha para a diagonal x+y=4 no
tabelao e ve apenas duas possibilidades para o dialogo ateh entao proferido
pelo Sr. P: "D" (em (1,3)) e "N" (em (2,2)). Dependendo do que o Sr. P
falou, o Sr. S saberah a resposta. Assim temos "DD" em (1,3) e "ND" em
(2,2).
-- Qualquer outra casa do meu tabelao pertence a uma diagonal x+y=S com
varias casas marcadas ateh aqui com "N". Assim, nestas casa, acresente mais
um N e fique com "NN" -- o sr. S nao tem como saber que "N" foi o que o Sr.
P proferiu.
iii) Estah acompanhando o tabelao? O Sr. P estah limitado a uma curva do
tipo xy=P (uma especie de hiperbole nos inteiros, limitada pela condicao
x<=y). Veja as possibilidades para esta curva... Muitas delas teem um bando
de "NN" e, portanto, o Sr. P diria mais um N, incapaz de decidir qual
daqueles pontos NN eh o do momento. As excecoes sao:
-- Se o produto eh 4, ha apenas os pontos (1,4) e (2,2), que no momento teem
dialogos distintos (NN e ND repsectivamente!). Assim, o Sr. P eh capaz de
separa-los. Portanto, (1,4) fica com NND e (2,2)=NDD.
-- Todos os outros pontos tipo NN viram NNN -- ha varios NN em cada uma das
"hiperboles", e o Sr. P nao tem como decidir nada.
iv) Agora, o Sr. S ve a sua "diagonal". Quase todas teem um bando de NNN
ateh aqui e o Sr. S eh incapaz de dizer qualquer coisa. A excecao notavel eh
a reta x+y=5, com apenas (1,4)=NND e (2,3)=NNN. Assim, se a soma for 5, o
Sr. S eh capaz de decidir qual dos dois eh o correto pelo dialogo.
Ficamos com (1,4)=NNDD e fim de papo, (2,3)=NNND, e todos os outros que
tinham NNN ficam NNNN.
v) Agora, o Sr. P olha a sua hiperbole. Note que todas elas estao lotadas de
NNNN como no passo (iii); a unica diferenca notavel estah na curva xy=6, que
agora tem (1,6)=NNNN e (2,3)=NNND. Sr. P eh agora capaz de separa-los pelo
dialogo, isto eh, (1,6)=NNNND e (2,3)=NNNDD. O resto que tinha NNNN fica com
NNNNN.
vi) Note que nao ha mudancas significativas desde o passo (iv) para o Sr. S.
A unica esperanca seria a troca de status do ponto (1,6), mas infelizmente
ainda ha DOIS pontos na reta x+y=7 com status NNNNN, e o Sr. S seria incapaz
de ditingui-los. Em suma, (1,6)=NNNNDD e fim de papo, o resto leva NNNNNN.
vii) Daqui para a frente, a tabela nao ganha nenhum D, e portanto nem Sr. S
nem Sr. P serah capaz de distinguir pelo dialogo algo que estava confuso
depois. A tabela fica assim:
y/x 1 2 3 4 5 6 7 8 9 10...
1 DD DD DD NNDD DD NNNNDD DD NNNNNN NNNNNN NNNNNN
2 NDD NNNDD NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN
3 NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN
4 NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN
5 NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN
6 NNNNNN NNNNNN NNNNNN NNNNNN NNNNNN
...
Onde NNNNNN de fato significa NNNNNNNNNNN... :)
Em suma, pra nois coitadinhos inqui de fora que num tem numuro na mao:
- Se o dialogo for DD, era (1,1) ou (1,p) com p primo;
- Se o dialogo for NDD, era (2,2)
- Se o dialogo for NNDD, era (1,4)
- Se o dialogo for NNNDD, era (2,3)
- Se o dialogo for NNNNDD, era (1,6) -- o caso do problema!
- Fora isso, o dialogo TEM DE SER NNNNN..., e o par pode ser qualquer outro!
Fique aa vontade para adaptar este tabelao para o caso da questao, onde a
soma eh limitada por 99. Havera varias diferencas do lado direito da tabela,
perto do 99, com uma onda de D's do lado de lah... :) De uma certa maneira
este metodo eh "infalivel" -- sim, pode dar um trabalho de cao, mas este
metodo dah um "algoritmo" para gerar todos os dialogos possiveis, mesmo que
a situacao envolvesse inteiros negativos ou outras restricoes.
Abraco,
Ralph
P.S.: Hmmmm... Mas serah que 0,NNNNNN...=D,000000... :) ;P :)
>From: "Marcos Melo" <mgmelo@terra.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: "obm-l" <obm-l@mat.puc-rio.br>
>Subject: [obm-l] Problemão que circulou em outra lista
>Date: Thu, 25 Apr 2002 20:46:21 -0200
>
>Para o caso de não ter circulado por esta lista:
>
>******************* Texto do Problema *****************************
>Dois amigos se encontram. Um tem o produto de dois numeros (Sr. P) e
>o outro
>tem a soma dos dois numeros (Sr. S). Nenhum dos dois sabe quais sao
>os
>numeros. Entao eles desenvolvem o seguinte dialogo:
>
>Sr. S: A soma eh menor que 99.
>Sr. P: Deste jeito, eu nao sei quais sao os numeros.
>Sr. S: Entao eu tambem nao sei quais sao os numeros.
>Sr. P: Se voce nao sabe ainda, eu tambem nao sei.
>Sr. S: Como voce nao sabe, eu tambem nao sei.
>
>Sr. P: Agora, eu sei quais sao os numeros.
>Sr. S: Eu tambem sei.
>
>Quais sao os numeros?
=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================