¿Puedes resolver el acertijo del virus? - Lisa Winer

Para ver la lección completa: http://ed.ted.com/lessons/can-you-solve-the-virus-riddle-lisa-winer

Tu equipo de investigación ha encontrado un virus prehistórico preservado en el gelisuelo y lo ha aislado para su estudio. Después de una noche trabajando, estás cerrando el laboratorio cuando de repente se produce un terremoto y se rompen todos los frascos con muestras. ¿Serás capaz de destruir el virus antes de que se abra el sistema de ventilación y se desencadene una plaga mortífera? Lisa Winer explica cómo conseguirlo.

Lección de Lisa Winer, animación de Artrake Studio.

Tu equipo de investigación
ha encontrado un virus prehistórico

conservado en el permafrost
y lo ha aislado para su estudio.

Tras una noche de trabajo,
estás cerrando el laboratorio

cuando de repente

se produce un terremoto
y hay un corte de electricidad.

Cuando se encienden
los generadores de emergencia

una alarma confirma tu peor pesadilla:

todos los viales
con las muestras se han roto.

El virus está contenido por ahora,

pero a menos que puedas destruirlo,

los respiraderos pronto se abrirán

y desencadenarán
una mortífera plaga aérea.

Sin dudarlo, agarras
tu traje de protección

y te preparas para salvar el mundo.

El laboratorio es un complejo de
cuatro por cuatro de 16 habitaciones

con una entrada en la esquina noroeste
y una salida en el sureste.

Las habitaciones están conectadas
entre sí por una esclusa,

y el virus ha sido liberado
en cada habitación excepto la entrada.

Para destruirlo, debes entrar
en cada habitación contaminada

y tirar del interruptor de emergencia
para su auto-destrucción.

Pero hay una trampa.

Debido a que el sistema
de seguridad está bloqueado,

una vez que entras en la
habitación contaminada,

no se puede salir sin
activar el interruptor,

y una vez que lo hayas hecho,

ya no podrás volver a esa habitación.

Empiezas a dibujar posibles
rutas en una libreta de papel,

pero ninguna parece llevarte a la salida

sin que falte al menos una habitación.

Entonces, ¿cómo puedes destruir el virus
en cada habitación contaminada

y sobrevivir para contar la historia?

Pausa aquí si quieres
averiguarlo por tí mismo.

Respuesta en: 3

Respuesta en: 2

Respuesta en: 1

Si tu primer instinto es dibujar
tus posibles rutas en una cuadrícula,

vas bien encaminado.

Este rompecabezas está relacionado
con el problema del camino hamiltoniano

nombrado en honor del matemático irlandés
del siglo XIX William Rowan Hamilton.

El desafío del problema del camino

es descubrir si una gráfica dada
tiene una ruta hamiltoniana.

Es una ruta que visita cada punto
dentro de ella exactamente una vez.

Este tipo de problema,
clasificado como NP-completo,

es muy difícil cuando el gráfico
es lo bastante grande.

Aunque cualquier solución propuesta
puede ser verificada fácilmente,

no tenemos ninguna fórmula fiable
o atajo para encontrar uno,

o determinar que existe.

Y ni siquiera estamos seguros
de si es posible para los ordenadores

encontrar de manera
fiable tales soluciones.

Este rompecabezas agrega un giro
al problema de la trayectoria hamiltoniana

ya que tienes que empezar
y terminar en puntos específicos.

Pero antes de gastar una
tonelada de papel cuadriculado,

debes saber que una verdadera
ruta hamiltoniana

no es posible con estos puntos finales.

Eso es porque las habitaciones
forman una cuadrícula

con un número par de
habitaciones en cada lado.

En cualquier cuadrícula
con esa configuración,

un camino hamiltoniano que comienza y
termina en esquinas opuestas es imposible.

He aquí una manera de entender por qué.

Imagina un tablero cuadriculado
con un número par de cuadros en cada lado.

Cada ruta a través de él
alternará blanco y negro.

La cuadrícula también tendrá
un número total de cuadrados par,

porque un número par
por otro número par da par.

Así que un camino hamiltoniano en una
cuadrícula par que empieza en negro

tendrá que terminar en blanco.

Y si empieza en blanco
tendrá que terminar en negro.

Sin embargo, en cualquier
cuadrícula con lados pares,

las esquinas opuestas son del mismo color,

por lo que es imposible iniciar
y terminar un camino hamiltoniano

en las esquinas opuestas.

Parece que se te ha acabado la suerte.

A no ser que mires las reglas con atención
y notes una importante excepción.

Es cierto

que una vez que activas el interruptor
en una habitación contaminada,

es destruida y no puedes volver atrás.

Pero hay una habitación
que no estaba contaminada - la entrada.

Esto significa que puedes dejarla
una vez sin tirar del interruptor

y regresar a ella cuando hayas destruido
cualquiera de estas dos habitaciones.

La habitación de la esquina
puede haber sido contaminada

por la apertura de la esclusa,
pero no pasa nada

porque puedes destruir la entrada
después de tu segunda visita.

Ese viaje de vuelta te da cuatro
opciones para una ruta exitosa,

y un grupo similar de opciones
si destruiste esta habitación primero.

Enhorabuena.

Has evitado una epidemia
de dimensiones apocalípticas,

pero tras un suceso tan estresante,
necesitas un descanso.

Tal vez deberías aceptar
esa nueva oferta de trabajo

para ser vendedor ambulante.