Можете ли вы решить загадку о вирусе? — Лиза Винер

Посмотреть урок полностью: http://ed.ted.com/lessons/can-you-solve-the-virus-riddle-lisa-winer

Ваша команда исследователей нашла доисторический вирус, сохранившийся в вечной мерзлоте, и изолировала его для изучения. Завершив работу поздней ночью, вы как раз закрывали лабораторию, когда неожиданно произошло землетрясение и все пробирки с образцами разбились. Сможете ли вы уничтожить вирус до того, как откроется вентиляция и высвободит смертельную, переносимую воздушно-капельным путём чуму? Лиза Винер покажет, как это сделать.

Урок — Лиза Винер, анимация — Artrake Studio.

Ваша команда исследователей
нашла доисторический вирус,

сохранившийся в вечной мерзлоте,

и изолировала его для изучения.

Завершив работу поздней ночью,

вы как раз закрывали лабораторию,
когда неожиданно произошло землетрясение

и отключилось электричество.

Как только заработали запасные генераторы,
подтвердились ваши наихудшие страхи:

все пробирки с образцами разбились.

Вирус пока что локализован,

но если вы его не уничтожите,

то смертельная воздушно-капельная чума
вырвется наружу через вентиляционные люки.

Без малейших сомнений
вы схватили ваш защитный костюм

и приготовились спасти мир.

Лаборатория представляет собой
строение четыре на четыре из 16 комнат

со входом на северо-западном углу
и выходом на юго-восточном.

Каждая комната соединена
со смежными комнатами шлюзом,

и вирус был выпущен в каждой комнате,
кроме комнаты со входом.

Чтобы его уничтожить, вам надо войти
в каждую заражённую комнату

и дёрнуть аварийный рубильник
самоликвидации.

Но тут есть загвоздка.

Так как система безопасности
на блокировке,

войдя в заражённую комнату,

вы не сможете из нее выйти,
пока не активируете рубильник,

а сделав это,

не сможете вернуться в эту комнату.

Вы начали рисовать на листке бумаги
возможные маршруты,

но ни один из них не привёл вас к выходу

так, чтобы вы не пропустили
как минимум одну комнату.

Как же вы можете уничтожить вирус
в каждой заражённой комнате

и выжить, чтобы рассказать об этом?

[Нажмите на паузу, если хотите
придумать решение самостоятельно.]

[Ответ через: 3]

[Ответ через: 2]

[Ответ через: 1]

Если вашей первой реакцией было начертить
в сетке граф ваших возможных передвижений,

ваша идея верна.

Эта головоломка относится к задаче
о гамильтоновом пути,

названной в честь математика XIX века
Уильяма Роуэна Гамильтона.

Проблема задачи о пути

состоит в том, чтобы определить,
имеет ли заданный граф гамильтонов путь —

маршрут, проходящий
через каждую точку лишь один раз.

Этот тип задачи,
классифицирующийся как NP-полная,

является крайне сложным,
когда граф достаточно большой.

Хотя любое предложенное решение
может быть легко проверено,

у нас нет достоверной формулы
или быстрого способа её нахождения

и способа установить, что она существует.

И мы не уверены,
что даже с помощью компьютеров

есть возможность найти такое решение.

Эта загадка усложняет
задачу о гамильтоновом пути,

так как вы должны начать путь
и закончить его в конкретных точках.

Но прежде, чем вы потратите
тонны миллиметровой бумаги,

вам следует знать, что нахождение
гамильтонова пути

невозможно с этими конечными точками,

так как комнаты образуют сетку с чётным
количеством комнат на каждой стороне.

В сетке с такой конфигурацией
невозможно найти

гамильтонов путь, который начинается
и заканчивается в противоположных углах.

Вот один из способов понять почему.

Рассмотрим шахматную доску с чётным
количеством квадратов на каждой стороне.

Любой путь через доску связан
с чередованием чёрных и белых квадратов.

Такая сетка так же будет состоять
из чётного количества квадратов,

потому что умножение чётных чисел
так же даёт чётное число.

Гамильтонов путь, начавшийся с чёрного
квадрата на сетке с чётными сторонами,

должен будет закончиться на белом.

А тот, что начинается с белого,
должен будет закончиться на чёрном.

Однако на любой сетке
с чётным количеством сторон,

противоположные углы
одного и того же цвета,

поэтому невозможно начать и закончить
гамильтонов путь в противоположных углах.

Судя по всему, вам не повезло,

но прочтите правила внимательнее,
и вы заметите важное исключение.

Это правда, что как только вы активируете
рубильник в заражённой комнате,

она уничтожится,
и вы не сможете в неё вернуться.

Но есть одна комната,
которая не была заражена — входная.

Это значит, что вы можете
покинуть её один раз, не дёргая рубильник,

и вернуться в неё, когда уничтожите
одну из этих двух комнат.

Угловая комната может быть заражена

из-за открытия шлюза, но это не страшно,

потому что вы можете уничтожить вход
после вашего второго посещения.

Возможность возврата даст вам
четыре варианта успешного маршрута,

и подобный набор вариантов,
если вы уничтожите эту комнату первой.

Поздравляю! Вы предотвратили эпидемию
катастрофических масштабов,

но после такого стресса вам нужен отдых.

Может быть, вам следует принять недавнее
предложение о работе коммивояжёром.