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.
A tua equipa de investigação encontrou um vírus pré-histórico preservado no "permafrost" e isolou-o para estudo. Depois de uma longa noite de trabalho, estás a fechar o laboratório quando ocorre um súbito tremor de terra que deita abaixo a eletricidade. Quando os geradores de emergência começam a trabalhar, um alarme confirma os teus piores receios: os frascos de amostras estão todos partidos. O vírus, por enquanto, está contido mas, a não ser que o destruas, os respiradouros que em breve se vão abrir desencadearão uma praga mortal lançada pelo ar. Sem hesitação, agarras no teu fato protetor e preparas-te para salvar o mundo. O laboratório é um complexo de 16 salas, num quadrado de 4 x 4, com uma entrada no canto noroeste e uma saída a sudeste. Cada sala está ligada às adjacentes por uma câmara de vácuo e o vírus espalhou-se por todas as salas, exceto a entrada. Para o destruir tens que entrar em todas as salas contaminadas e acionar o interruptor de emergência de autodestruição. Mas há um problema. Como o sistema de segurança está ativado, depois de entrares na sala contaminada não podes sair sem ativares o interruptor e, depois de fazeres isso, não podes voltar a essa sala. Começas a traçar num bloco todos os caminhos possíveis mas nenhum deles parece levar-te à saída sem falhar, pelo menos, uma sala. Como podes destruir o vírus em todas as salas contaminadas e sobreviver para contar a história? Detém-te aqui, se quiseres resolvê-lo sozinho. Resposta em: 3 Resposta em 2: Resposta em: 1 Se o teu primeiro instinto é tentar um grafo dos possíveis movimentos numa grelha, captaste a ideia certa. Este enigma está relacionado com o problema do caminho hamiltoniano assim chamado segundo William Rowan Hamilton, um matemático irlandês do século XIX. O desafio do problema do caminho é descobrir se um determinado grafo tem um caminho hamiltoniano. É um caminho que visita apenas uma vez todos os pontos que contém. Este tipo de problema, classificado como NP-complete, é extremamente difícil quando o grafo é muito grande. Embora qualquer solução proposta seja facilmente verificável, não temos uma fórmula ou atalho fiáveis para a encontrar, ou para determinar se ela existe. Nem sequer temos a certeza se os computadores podem encontrar essa solução fiável. Este enigma acrescenta uma nova versão ao problema do caminho hamiltoniano na medida em que temos que começar e acabar em pontos específicos. Mas, antes que gastes uma tonelada de papel, tens que saber que não é possível um verdadeiro caminho hamiltoniano com estes dois pontos extremos, porque as salas formam uma grelha com um número par de salas de cada lado. Em qualquer grelha com esta configuração, um caminho hamiltoniano que começa e termina em cantos opostos, é impossível. Eis uma forma de perceber porquê. Considera um tabuleiro de damas com um número par de quadrados de cada lado Todos os caminhos possíveis alternarão entre o preto e o branco. Estas grelhas também vão ter um número par de quadrados porque o produto de um número par por um número par é sempre par. Por isso, um caminho hamiltoniano numa grelha com um lado par que comece num quadrado preto terá que acabar num quadrado branco. E um caminho que comece num branco terá que acabar num quadrado preto. No entanto, em qualquer grelha com lados pares, os cantos opostos têm a mesma cor, por isso, é impossível começar e acabar um caminho hamiltoniano em cantos opostos. Parece que estás com pouca sorte, a não ser que olhes para as regras com atenção e repares numa exceção importante. É verdade que, depois de acionares o interruptor numa sala contaminada, ela é destruída e não podes voltar atrás. Mas há uma sala que não foi contaminada — a entrada — Isso significa que podes sair de lá sem acionar o interruptor e voltar lá depois de teres destruído uma destas duas salas. A sala do canto pode ter sido contaminada com a abertura da câmara de vácuo, mas não faz mal porque podes destruir a entrada depois da segunda visita. Este regresso dá-te quatro opções para um caminho com êxito e um conjunto de opções semelhante se destruíres esta sala primeiro. Parabéns! Impediste uma epidemia de proporções apocalípticas mas, depois de tão angustiante episódio, precisas de uma pausa. Talvez devas aceitar aquela oferta de trabalho