Você sabe resolver o enigma do vírus? - Lisa Winer

Veja a lição completa: http://ed.ted.com/lessons/can-you-solve-the-virus-riddle-lisa-winer

Sua equipe de pesquisa encontrou um vírus pré-histórico preservado no "permafrost" e que foi isolado para estudo. Depois de uma noite trabalhando, você está quase fechando o laboratório quando ocorre um terremoto e quebra todos os frascos das amostras que contêm o vírus. Você será capaz de destruir o vírus antes dos dutos de ventilação abrirem e liberarem uma peste mortal no ar? Lisa Winer mostra como.

Lição de Lisa Winer, animação de Artrake Studio

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.