Consegues resolver o enigma do vírus? — Lisa Winer

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

A tua equipa de investigação encontrou um vírus pré-histórico preservado no pergelissolo ("permafrost") e isolou-o para estudo. Depois de uma noite de trabalho, estás a fechar o laboratório quando ocorre um súbito tremor de terra que parte todos os frascos de amostras. Serás capaz de destruir o vírus antes que se abram os respiradouros e desencadeiem uma praga mortal espalhada pelo ar? Lisa Winer mostra como é.

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

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

para seres caixeiro-viajante.