Задача о вирусе (#12)

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

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

Каждая комната соединена со смежными комнатами шлюзом, и вирус был выпущен в каждой комнате, кроме комнаты со входом. Чтобы его уничтожить, вам надо войти в каждую зараженную комнату и дернуть аварийный рубильник самоликвидации. Но тут есть загвоздка. Так как система безопасности на блокировке, войдя в зараженную комнату, вы не сможете из нее выйти, пока не активируете рубильник, а сделав это, не сможете вернуться в эту комнату. Вы начали рисовать на листке бумаги возможные маршруты, но ни один из них не привел вас к выходу так, чтобы вы не пропустили как минимум одну комнату. Как же вы можете уничтожить вирус в каждой зараженной комнате и выжить, чтобы рассказать об этом? Ответ под картинкой.

ОТВЕТ:

Если вашей первой реакцией было начертить в сетке граф ваших возможных передвижений - идея верна. Эта головоломка относится к задаче о гамильтоновом пути, названной в честь математика XIX века Уильяма Роуэна Гамильтона. Проблема задачи о пути состоит в том, чтобы определить, имеет ли заданный граф гамильтонов путь - маршрут, проходящий через каждую точку лишь один раз. Этот тип задачи, классифицирующийся как NP-полная, является крайне сложным, когда граф достаточно большой. Хотя любое предложенное решение может быть легко проверено, у нас нет достоверной формулы или быстрого способа ее нахождения и способа установить, что она существует. И мы не уверены, что даже с помощью компьютеров есть возможность найти такое решение. Эта загадка усложняет задачу о гамильтоновом пути, так как вы должны начать путь и закончить его в конкретных точках. Но прежде, чем вы потратите тонны бумаги, вам следует знать, что нахождение гамильтонова пути невозможно с этими конечными точками, так как комнаты образуют сетку с четным количеством комнат на каждой стороне. В сетке с такой конфигурацией невозможно найти гамильтонов путь, который начинается и заканчивается в противоположных углах.

Вот один из способов понять почему. Рассмотрим шахматную доску с четным количеством квадратов на каждой стороне. Любой путь через доску связан с чередованием черных и белых квадратов. Такая сетка так же будет состоять из четного количества квадратов, потому что умножение четных чисел так же дает четное число. Гамильтонов путь, начавшийся с черного квадрата на сетке с четными сторонами, должен будет закончиться на белом. А тот, что начинается с белого, должен будет закончиться на черном. Однако на любой сетке с четным количеством сторон, противоположные углы одного и того же цвета, поэтому невозможно начать и закончить гамильтонов путь в противоположных углах.

Судя по всему, вам не повезло, но прочтите правила внимательнее, и вы заметите одно важное исключение. Это правда, что как только вы активируете рубильник в зараженной комнате, она уничтожится, и вы не сможете в нее вернуться. Но есть одна комната, которая не была заражена - входная. Это значит, что вы можете покинуть ее один раз, не дергая рубильник, и вернуться в нее, когда уничтожите одну из двух комнат по соседству. Угловая комната может быть заражена из-за открытия шлюза, но это не страшно, потому что вы можете уничтожить вход после вашего второго посещения.

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

Поздравляю! Вы предотвратили эпидемию катастрофических масштабов, но после такого стресса вам нужен отдых. Может быть, вам следует принять недавнее предложение о работе коммивояжером ;)

Источник: ed.ted.com