Sua equipe de pesquisa encontrou um vírus pré-histórico
preservado no "permafrost"
e que foi isolado para estudo.
Depois de uma noite de trabalho,
você está quase fechando o laboratório quando ocorre um terremoto
e a energia elétrica acaba.
Os geradores de emergência funcionam e um alarme confirma seus piores medos:
todos os frascos com amostras quebraram.
O vírus está controlado por enquanto,
mas, a menos que você possa destruí-lo
os dutos de ar em breve se abrirão e irão libertar uma peste mortal no ar.
Sem hesitação, você agarra seu traje de proteção
e corre para salvar o mundo.
O laboratório é composto por 16 salas quadradas
com uma entrada no canto noroeste e uma saída no canto sudeste.
Cada sala está conectada às outras por uma porta com trava
e o vírus foi liberado em todas as salas, exceto na entrada.
Para destruí-lo, você deve entrar em cada sala contaminada
e acionar a chave de autodestruição de emergência, mas há um problema.
Como o sistema de segurança está em confinamento,
uma vez que você entra na sala contaminada,
você não pode sair sem ativar a chave,
e, depois que você fizer isso,
você não poderá voltar a esta sala.
Você começa a pensar em todas as rotas possíveis num papel,
mas nada parece levar você à saída,
sem perder pelo menos uma sala.
Então, como você pode destruir o vírus em cada sala contaminada
e sobreviver para contar a história?
[Faça uma pausa aqui se você quiser descobrir por si mesmo.]
[Resposta em: 3]
[Resposta em: 2]
[Resposta em: 1]
Se o seu primeiro impulso for tentar desenhar os caminhos possíveis,
você está certo.
Este enigma está relacionado ao problema do caminho Hamiltoniano,
em homenagem ao matemático irlandês do século 19, William Rowan Hamilton.
O desafio do problema do caminho
é descobrir se um dado grafo tem um caminho Hamiltoniano.
Este é um caminho que passa somente uma vez em cada ponto.
Este tipo de problema, classificado como NP-completo,
é notoriamente difícil quando o grafo é muito grande.
Embora qualquer solução proposta possa ser facilmente verificada,
não existe nenhuma fórmula ou atalho confiável, para se achar uma solução,
ou determinar que existe uma.
Nem mesmo temos certeza se os computadores conseguiriam
encontrar uma solução confiável, também.
Este enigma acrescenta uma dificuldade ao problema do caminho Hamiltoniano,
no qual você tem que começar e terminar em pontos específicos.
Mas, antes de desperdiçar uma tonelada de papel quadriculado,
deveria saber que um verdadeiro caminho Hamiltoniano
não é possível com estes pontos finais.
Isso porque as salas formam uma grade com um número par de salas de cada lado.
E qualquer grade com esta configuração,
um caminho Hamiltoniano que começa e termina em cantos opostos é impossível.
Aqui está uma forma de entender o porquê.
Considere um tabuleiro de xadrez
com um número par de quadrados em cada lado.
Todos os caminhos através dele será alternado em branco e preto.
Essas grades também terão um número total par de quadrados
porque um número par vezes um número par também é par.
Assim, um caminho Hamiltoniano numa grade de lados iguais, que começa no preto,
terminará num quadrado branco.
E um que começar no branco, terminará num preto.
No entanto, em qualquer grade com lados par,
cantos opostos terão a mesma cor,
por isso é impossível iniciar e terminar um caminho Hamiltoniano em cantos opostos.
Parece que você está sem sorte,
a menos que você veja as regras e observe uma exceção importante.
Depois de ativada, a chave na sala contaminada,
é destruída e você não poderá voltar.
Mas, uma sala que não foi contaminada: a entrada.
Isso significa que você pode deixá-la uma vez, sem acionar a chave,
e voltar lá quando você tiver destruído qualquer uma dessas salas.
A sala do canto pode ter sido contaminada
pela abertura da porta com bloqueio mas está tudo bem
porque você pode destruir a entrada após a sua segunda visita.
Este retorno oferece quatro opções para um caminho bem-sucedido,
e um conjunto semelhante de opções, se você destruiu esta sala primeiro.
Parabéns!
Você impediu uma epidemia de proporções apocalípticas,
mas depois de um episódio estressante, você precisa de uma pausa.
Talvez você aceite uma oferta de trabalhar como caixeiro-viajante.