Your research team has found a prehistoric virus preserved in the permafrost and isolated it for study. After a late night working, you're just closing up the lab when a sudden earthquake hits and knocks out the power. As the emergency generators kick in, an alarm confirms your worst fears: all the sample vials have broken. The virus is contained for now, but unless you can destroy it, the vents will soon open and unleash a deadly airborne plague. Without hesitation, you grab your HazMat suit and get ready to save the world. The lab is a four by four compound of 16 rooms with an entrance on the northwest corner and an exit at the southeast. Each room is connected to the adjacent ones by an airlock, and the virus has been released in every room except the entrance. To destroy it, you must enter each contaminated room and pull its emergency self-destruct switch. But there's a catch. Because the security system is on lockdown, once you enter the contaminated room, you can't exit without activating the switch, and once you've done so, you won't be able to go back in to that room. You start to draw out possible routes on a pad of paper, but nothing seems to get you to the exit without missing at least one room. So how can you destroy the virus in every contaminated room and survive to tell the story? Pause here if you want to figure it out for yourself. Answer in: 3 Answer in: 2 Answer in: 1 If your first instinct is to try to graph your possible moves on a grid, you've got the right idea. This puzzle is related to the Hamiltonian path problem named after the 19th century Irish mathematician William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a Hamiltonian path. That's a route that visits every point within it exactly once. This type of problem, classified as NP-complete, is notoriously difficult when the graph is sufficiently large. Although any proposed solution can be easily verified, we have no reliable formula or shortcut for finding one, or determining that one exists. And we're not even sure if it's possible for computers to reliably find such solutions, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at specific points. But before you waste a ton of graph paper, you should know that a true Hamiltonian path isn't possible with these end points. That's because the rooms form a grid with an even number of rooms on each side. In any grid with that configuration, a Hamiltonian path that starts and ends in opposite corners is impossible. Here's one way of understanding why. Consider a checkerboard grid with an even number of squares on each side. Every path through it will alternate black and white. These grids will all also have an even total number of squares because an even number times and even number is even. So a Hamiltonian path on an even-sided grid that starts on black will have to end on white. And one that starts on white will have to end on black. However, in any grid with even numbered sides, opposite corners are the same color, so it's impossible to start and end a Hamiltonian path on opposite corners. It seems like you're out of luck, unless you look at the rules carefully and notice an important exception. It's true that once you activate the switch in a contaminated room, it's destroyed and you can never go back. But there's one room that wasn't contaminated - the entrance. This means that you can leave it once without pulling the switch and return there when you've destroyed either of these two rooms. The corner room may have been contaminated from the airlock opening, but that's okay because you can destroy the entrance after your second visit. That return trip gives you four options for a successful route, and a similar set of options if you destroyed this room first. Congratulations. You've prevented an epidemic of apocalyptic proportions, but after such a stressful episode, you need a break. Maybe you should take up that recent job offer to become a traveling salesman.
Ваша команда исследователей нашла доисторический вирус, сохранившийся в вечной мерзлоте, и изолировала его для изучения. Завершив работу поздней ночью, вы как раз закрывали лабораторию, когда неожиданно произошло землетрясение и отключилось электричество. Как только заработали запасные генераторы, подтвердились ваши наихудшие страхи: все пробирки с образцами разбились. Вирус пока что локализован, но если вы его не уничтожите, то смертельная воздушно-капельная чума вырвется наружу через вентиляционные люки. Без малейших сомнений вы схватили ваш защитный костюм и приготовились спасти мир. Лаборатория представляет собой строение четыре на четыре из 16 комнат со входом на северо-западном углу и выходом на юго-восточном. Каждая комната соединена со смежными комнатами шлюзом, и вирус был выпущен в каждой комнате, кроме комнаты со входом. Чтобы его уничтожить, вам надо войти в каждую заражённую комнату и дёрнуть аварийный рубильник самоликвидации. Но тут есть загвоздка. Так как система безопасности на блокировке, войдя в заражённую комнату, вы не сможете из нее выйти, пока не активируете рубильник, а сделав это, не сможете вернуться в эту комнату. Вы начали рисовать на листке бумаги возможные маршруты, но ни один из них не привёл вас к выходу так, чтобы вы не пропустили как минимум одну комнату. Как же вы можете уничтожить вирус в каждой заражённой комнате и выжить, чтобы рассказать об этом? [Нажмите на паузу, если хотите придумать решение самостоятельно.] [Ответ через: 3] [Ответ через: 2] [Ответ через: 1] Если вашей первой реакцией было начертить в сетке граф ваших возможных передвижений, ваша идея верна. Эта головоломка относится к задаче о гамильтоновом пути, названной в честь математика XIX века Уильяма Роуэна Гамильтона. Проблема задачи о пути состоит в том, чтобы определить, имеет ли заданный граф гамильтонов путь — маршрут, проходящий через каждую точку лишь один раз. Этот тип задачи, классифицирующийся как NP-полная, является крайне сложным, когда граф достаточно большой. Хотя любое предложенное решение может быть легко проверено, у нас нет достоверной формулы или быстрого способа её нахождения и способа установить, что она существует. И мы не уверены, что даже с помощью компьютеров есть возможность найти такое решение. Эта загадка усложняет задачу о гамильтоновом пути, так как вы должны начать путь и закончить его в конкретных точках. Но прежде, чем вы потратите тонны миллиметровой бумаги, вам следует знать, что нахождение гамильтонова пути невозможно с этими конечными точками, так как комнаты образуют сетку с чётным количеством комнат на каждой стороне. В сетке с такой конфигурацией невозможно найти гамильтонов путь, который начинается и заканчивается в противоположных углах. Вот один из способов понять почему. Рассмотрим шахматную доску с чётным количеством квадратов на каждой стороне. Любой путь через доску связан с чередованием чёрных и белых квадратов. Такая сетка так же будет состоять из чётного количества квадратов, потому что умножение чётных чисел так же даёт чётное число. Гамильтонов путь, начавшийся с чёрного квадрата на сетке с чётными сторонами, должен будет закончиться на белом. А тот, что начинается с белого, должен будет закончиться на чёрном. Однако на любой сетке с чётным количеством сторон, противоположные углы одного и того же цвета, поэтому невозможно начать и закончить гамильтонов путь в противоположных углах. Судя по всему, вам не повезло, но прочтите правила внимательнее, и вы заметите важное исключение. Это правда, что как только вы активируете рубильник в заражённой комнате, она уничтожится, и вы не сможете в неё вернуться. Но есть одна комната, которая не была заражена — входная. Это значит, что вы можете покинуть её один раз, не дёргая рубильник, и вернуться в неё, когда уничтожите одну из этих двух комнат. Угловая комната может быть заражена из-за открытия шлюза, но это не страшно, потому что вы можете уничтожить вход после вашего второго посещения. Возможность возврата даст вам четыре варианта успешного маршрута, и подобный набор вариантов, если вы уничтожите эту комнату первой. Поздравляю! Вы предотвратили эпидемию катастрофических масштабов, но после такого стресса вам нужен отдых. Может быть, вам следует принять недавнее предложение о работе коммивояжёром.