Your research team has found a prehistoric virus preserved in the permafrost and isolated it for study. After a late night working, you're just closing up the lab when a sudden earthquake hits and knocks out the power. As the emergency generators kick in, an alarm confirms your worst fears: all the sample vials have broken. The virus is contained for now, but unless you can destroy it, the vents will soon open and unleash a deadly airborne plague. Without hesitation, you grab your HazMat suit and get ready to save the world. The lab is a four by four compound of 16 rooms with an entrance on the northwest corner and an exit at the southeast. Each room is connected to the adjacent ones by an airlock, and the virus has been released in every room except the entrance. To destroy it, you must enter each contaminated room and pull its emergency self-destruct switch. But there's a catch. Because the security system is on lockdown, once you enter the contaminated room, you can't exit without activating the switch, and once you've done so, you won't be able to go back in to that room. You start to draw out possible routes on a pad of paper, but nothing seems to get you to the exit without missing at least one room. So how can you destroy the virus in every contaminated room and survive to tell the story? Pause here if you want to figure it out for yourself. Answer in: 3 Answer in: 2 Answer in: 1 If your first instinct is to try to graph your possible moves on a grid, you've got the right idea. This puzzle is related to the Hamiltonian path problem named after the 19th century Irish mathematician William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a Hamiltonian path. That's a route that visits every point within it exactly once. This type of problem, classified as NP-complete, is notoriously difficult when the graph is sufficiently large. Although any proposed solution can be easily verified, we have no reliable formula or shortcut for finding one, or determining that one exists. And we're not even sure if it's possible for computers to reliably find such solutions, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at specific points. But before you waste a ton of graph paper, you should know that a true Hamiltonian path isn't possible with these end points. That's because the rooms form a grid with an even number of rooms on each side. In any grid with that configuration, a Hamiltonian path that starts and ends in opposite corners is impossible. Here's one way of understanding why. Consider a checkerboard grid with an even number of squares on each side. Every path through it will alternate black and white. These grids will all also have an even total number of squares because an even number times and even number is even. So a Hamiltonian path on an even-sided grid that starts on black will have to end on white. And one that starts on white will have to end on black. However, in any grid with even numbered sides, opposite corners are the same color, so it's impossible to start and end a Hamiltonian path on opposite corners. It seems like you're out of luck, unless you look at the rules carefully and notice an important exception. It's true that once you activate the switch in a contaminated room, it's destroyed and you can never go back. But there's one room that wasn't contaminated - the entrance. This means that you can leave it once without pulling the switch and return there when you've destroyed either of these two rooms. The corner room may have been contaminated from the airlock opening, but that's okay because you can destroy the entrance after your second visit. That return trip gives you four options for a successful route, and a similar set of options if you destroyed this room first. Congratulations. You've prevented an epidemic of apocalyptic proportions, but after such a stressful episode, you need a break. Maybe you should take up that recent job offer to become a traveling salesman.
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.