WEBVTT

00:00:08.113 --> 00:00:10.718
Sua equipe de pesquisa encontrou
um vírus pré-histórico

00:00:10.778 --> 00:00:12.619
preservado no "permafrost"

00:00:12.689 --> 00:00:14.730
e que foi isolado para estudo.

00:00:15.020 --> 00:00:16.709
Depois de uma noite de trabalho,

00:00:16.859 --> 00:00:20.389
você está quase fechando o laboratório
quando ocorre um terremoto

00:00:20.529 --> 00:00:22.339
e a energia elétrica acaba.

00:00:22.449 --> 00:00:27.169
Os geradores de emergência funcionam
e um alarme confirma seus piores medos:

00:00:27.449 --> 00:00:30.624
todos os frascos com amostras quebraram.

00:00:30.734 --> 00:00:32.873
O vírus está controlado por enquanto,

00:00:32.973 --> 00:00:34.846
mas, a menos que você possa destruí-lo

00:00:34.846 --> 00:00:39.392
os dutos de ar em breve se abrirão
e irão libertar uma peste mortal no ar.

00:00:40.072 --> 00:00:42.530
Sem hesitação, você agarra
seu traje de proteção

00:00:42.640 --> 00:00:45.560
e corre para salvar o mundo.

00:00:46.070 --> 00:00:49.851
O laboratório é composto
por 16 salas quadradas

00:00:50.041 --> 00:00:54.591
com uma entrada no canto noroeste
e uma saída no canto sudeste.

00:00:55.041 --> 00:00:58.402
Cada sala está conectada
às outras por uma porta com trava

00:00:58.412 --> 00:01:02.760
e o vírus foi liberado em todas
as salas, exceto na entrada.

00:01:03.030 --> 00:01:06.030
Para destruí-lo, você deve entrar
em cada sala contaminada

00:01:06.040 --> 00:01:10.670
e acionar a chave de autodestruição
de emergência, mas há um problema.

00:01:11.230 --> 00:01:13.842
Como o sistema de segurança
está em confinamento,

00:01:13.842 --> 00:01:16.051
uma vez que você entra
na sala contaminada,

00:01:16.111 --> 00:01:18.980
você não pode sair sem ativar a chave,

00:01:19.310 --> 00:01:21.030
e, depois que você fizer isso,

00:01:21.130 --> 00:01:24.271
você não poderá voltar a esta sala.

00:01:25.221 --> 00:01:29.000
Você começa a pensar em todas
as rotas possíveis num papel,

00:01:29.060 --> 00:01:31.234
mas nada parece levar você à saída,

00:01:31.324 --> 00:01:34.010
sem perder pelo menos uma sala.

00:01:34.280 --> 00:01:38.131
Então, como você pode destruir o vírus
em cada sala contaminada

00:01:38.231 --> 00:01:40.622
e sobreviver para contar a história?

00:01:40.732 --> 00:01:44.782
[Faça uma pausa aqui se você
quiser descobrir por si mesmo.]

00:01:45.432 --> 00:01:47.036
[Resposta em: 3]

00:01:47.036 --> 00:01:48.760
[Resposta em: 2]

00:01:48.830 --> 00:01:50.543
[Resposta em: 1]

00:01:50.723 --> 00:01:54.430
Se o seu primeiro impulso for tentar
desenhar os caminhos possíveis,

00:01:54.800 --> 00:01:56.500
você está certo.

00:01:56.750 --> 00:02:00.100
Este enigma está relacionado
ao problema do caminho Hamiltoniano,

00:02:00.310 --> 00:02:05.241
em homenagem ao matemático irlandês
do século 19, William Rowan Hamilton.

00:02:05.371 --> 00:02:06.930
O desafio do problema do caminho

00:02:07.050 --> 00:02:10.901
é descobrir se um dado grafo
tem um caminho Hamiltoniano.

00:02:11.401 --> 00:02:15.501
Este é um caminho que passa
somente uma vez em cada ponto.

00:02:15.791 --> 00:02:19.451
Este tipo de problema,
classificado como NP-completo,

00:02:19.451 --> 00:02:23.561
é notoriamente difícil 
quando o grafo é muito grande.

00:02:23.891 --> 00:02:27.472
Embora qualquer solução proposta
possa ser facilmente verificada,

00:02:27.532 --> 00:02:31.161
não existe nenhuma fórmula ou atalho
confiável, para se achar uma solução,

00:02:31.161 --> 00:02:33.402
ou determinar que existe uma.

00:02:33.402 --> 00:02:36.131
Nem mesmo temos certeza
se os computadores conseguiriam

00:02:36.231 --> 00:02:39.801
encontrar uma solução confiável, também.

00:02:39.881 --> 00:02:43.501
Este enigma acrescenta uma dificuldade
ao problema do caminho Hamiltoniano,

00:02:43.591 --> 00:02:46.892
no qual você tem que começar
e terminar em pontos específicos.

00:02:47.382 --> 00:02:50.342
Mas, antes de desperdiçar
uma tonelada de papel quadriculado,

00:02:50.342 --> 00:02:52.882
deveria saber que um verdadeiro
caminho Hamiltoniano

00:02:52.882 --> 00:02:55.331
não é possível com estes pontos finais.

00:02:55.331 --> 00:03:00.153
Isso porque as salas formam uma grade
com um número par de salas de cada lado.

00:03:00.963 --> 00:03:03.172
E qualquer grade com esta configuração,

00:03:03.172 --> 00:03:09.172
um caminho Hamiltoniano que começa
e termina em cantos opostos é impossível.

00:03:10.022 --> 00:03:12.611
Aqui está uma forma de entender o porquê.

00:03:12.831 --> 00:03:14.432
Considere um tabuleiro de xadrez

00:03:14.432 --> 00:03:17.252
com um número par
de quadrados em cada lado.

00:03:17.252 --> 00:03:20.392
Todos os caminhos através dele
será alternado em branco e preto.

00:03:20.802 --> 00:03:25.262
Essas grades também terão
um número total par de quadrados

00:03:25.482 --> 00:03:29.023
porque um número par vezes
um número par também é par.

00:03:29.383 --> 00:03:33.813
Assim, um caminho Hamiltoniano numa grade
de lados iguais, que começa no preto,

00:03:34.043 --> 00:03:36.283
terminará num quadrado branco.

00:03:36.483 --> 00:03:39.544
E um que começar no branco,
terminará num preto.

00:03:39.984 --> 00:03:42.842
No entanto, em qualquer
grade com lados par,

00:03:43.122 --> 00:03:45.672
cantos opostos terão a mesma cor,

00:03:46.112 --> 00:03:51.433
por isso é impossível iniciar e terminar
um caminho Hamiltoniano em cantos opostos.

00:03:52.503 --> 00:03:54.614
Parece que você está sem sorte,

00:03:54.614 --> 00:03:59.244
a menos que você veja as regras
e observe uma exceção importante.

00:04:00.384 --> 00:04:04.104
Depois de ativada, a chave
na sala contaminada,

00:04:04.244 --> 00:04:06.994
é destruída e você não poderá voltar.

00:04:07.094 --> 00:04:10.673
Mas, uma sala que não
foi contaminada: a entrada.

00:04:11.043 --> 00:04:14.873
Isso significa que você pode deixá-la
uma vez, sem acionar a chave,

00:04:14.983 --> 00:04:18.904
e voltar lá quando você tiver destruído
qualquer uma dessas salas.

00:04:19.514 --> 00:04:21.968
A sala do canto pode ter sido contaminada

00:04:21.998 --> 00:04:24.534
pela abertura da porta
com bloqueio mas está tudo bem

00:04:24.574 --> 00:04:27.843
porque você pode destruir
a entrada após a sua segunda visita.

00:04:28.133 --> 00:04:32.268
Este retorno oferece quatro opções
para um caminho bem-sucedido,

00:04:32.328 --> 00:04:36.448
e um conjunto semelhante de opções,
se você destruiu esta sala primeiro.

00:04:37.128 --> 00:04:37.994
Parabéns!

00:04:37.994 --> 00:04:42.654
Você impediu uma epidemia
de proporções apocalípticas,

00:04:42.654 --> 00:04:45.745
mas depois de um episódio estressante,
você precisa de uma pausa.

00:04:46.015 --> 00:04:50.129
Talvez você aceite uma oferta
de trabalhar como caixeiro-viajante.