[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RES: [obm-l] Problema
Eu chutei o balde: fiz um diagrama com todas as possibilidades de vizinhos, ficou assim (use texto de largura fixa para ver isto):
-- -- -- -- -- -- -- 01 08 15 22 29 36 43
-- -- -- -- -- -- 03 10 17 24 31 38 45
-- -- -- -- -- 05 12 19 26 33 40 47
-- -- -- -- 07 14 21 28 35 42 49
-- -- 02 09 16 23 30 37 44
-- 04 11 18 25 32 39 46
06 13 20 27 34 41 48
15 22 29 36 43
(Note que a última linha repete um pedaço da lá de cima).
Agora é fazer um caminho com segmentos horizontais ou verticais andando pelas células numeradas acima, passando por cada célula apenas uma vez.
Se eu me lembro bem, este é o clássico problema de encontrar um caminho Hamiltoniano para um grafo. E "clássico" não é "fácil" -- apesar de muito pesquisado, encontrar este caminho num grafo geral é um problema NP ou NP-completo ou algo assim (eu não sei quase nada de Teoria dos Grafos; quem souber mais, como o Nicolau, por exemplo, pode me corrigir). :)
Mas nosso problema não é o caso geral, então há esperança: comece olhando os cantos, onde só há uma opção (por exemplo, só passo pelo 05 se for fazendo 12 05 14)... faça o desenho com as conexões, marque as absolutamente necessárias por causa dos cantos, corte conexões com números que já foram gastos, aparecem novos cantos que só tem uma opção, etc. Fica melhor no papel do que no computador.
Quem quiser tentar agora por conta própria, pare de ler aqui.......
Até este diagrama abaixo, não há opções (hmmm.... mentira, um dos tais "cantos" poderia ser uma "ponta"... vou ignorar isto e torcer para achar UMA resposta):
|| || ||
01=08 15 22=29 36=43
|| || ||
03=10 17 24=31 38=45
|| ||
05=12 19=26 33 40=47
|| || ||
07=14 21=28 35 42=49
|| || ||
02=09 16 23=30 37=44
|| ||
04=11 18 25 32 39=46
|| ||
06=13 20=27 34 41=48
|| || ||
15 22=29 36=43
Agora há opções.... eu tentei juntar 09 com 16 e me dei mal... então tentei juntar 09 com 18 e 41 com 32... Fiz umas outras escolhas arbitrárias, mantendo a simetria por razões puramente estéticas, e cheguei numa possibilidade bonitinha:
|| || ||
01=08=15 22=29 36=43
|| || ||
03=10 17=24=31 38=45
|| ||
05=12 19=26=33 40=47
|| || ||
07=14 21=28 35=42=49
|| || ||
02=09 16 23=30 37=44
|| || || || ||
04=11 18 25 32 39=46
|| || || || ||
06=13 20=27 34 41=48
|| || ||
Então uma solução possível é:
17-24-31-22-29-20-27-18-09-02-11-04-13-06-15-08-01-10-03-12-05-14-07-16-25)
25)-34-43-36-45-38-47-40-49-42-35-44-37-46-39-48-41-32-23-30-21-28-19-26-33.
Uff!
Perguntas adicionais:
i) Há outras respostas? (Sim: troque 17-24 e 26-33 por 17-26 e 24-33...)
ii) 17 e 33 têm de ser as pontas? (Não: troque 49-40 por 40-33 e você tem um outro caminho; aliás, trocando também 1-10 por 10-17, dá uma solução COMEÇANDO no 1 e TERMINANDO no 49!! Vou escrever esta só de farra:
01-08-15-06-13-04-11-02-09-18-27-20-29-22-31-24-17-10-03-12-05-14-07-16-25)
(25-34-43-36-45-38-47-40-33-26-19-28-21-30-23-32-41-48-39-46-37-44-35-42-49
Legal!
Abraço,
Ralph
-----Mensagem original-----
De: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br]Em nome de Carlos Gomes
Enviada em: segunda-feira, 29 de janeiro de 2007 14:44
Para: obm-l@mat.puc-rio.br
Assunto: [obm-l] Problema
Vê se alguém tem alguma sugestão para essa questao;
Disponha em linha reta, numa ordem, os números inteiros de 1 até 49, de modo que o valor absoluto da diferença de quaisquer dois vizinhos, nessa ordem, seja ou 7 ou 9.
Obg
C.Gomes
=========================================================================
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
=========================================================================