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.
Nhóm nghiên cứu của bạn đã tìm thấy một loại vi rút thời tiền sử, được bảo tồn trong lớp bằng vĩnh cửu, và tách nó ra để nghiên cứu. Sau một đêm dài làm việc, khi bạn đóng cửa phòng thí nghiệm thì một trận động đất bất ngờ ập đến, và làm mất nguồn điện. Khi máy phát điện dự phòng khởi động, điều bạn lo sợ nhất được thông báo, những lọ chứa mẫu đã bị vỡ. Vi rút vẫn chưa thoát ra, nhưng nếu bạn không tiêu diệt nó cửa thông gió sẽ mở và một bệnh dịch chết chóc sẽ lan truyền. Bạn ngay lập tức mặc bộ đồ bảo vệ, và sẵn sàng giải cứu thế giới. Phòng nghiên cứu gồm 16 khu được xếp theo hình vuông, với lối vào ở góc hướng tây bắc, và lối ra ở góc hướng đông nam. Mỗi phòng đều nối với phòng sát nó bằng một cửa không khí, và vi rút đã lan khắp các phòng ngoại trừ lối vào, Để tiêu diệt nó, bạn phải đi vào từng phòng bị nhiễm và kéo công tắc tự hủy diệt. Nhưng có một quy tắc: Bởi vì hệ thống an ninh đang ở chế độ khẩn cấp, một khi bạn bước vào phòng nhiễm vi rút, bạn không thể thoát ra nếu không kích hoạt công tắc tự huỷ. Một khi bạn đã kéo công tắc, bạn không thể bước vào lại căn phòng đó. Bạn bắt đầu vẽ ra lộ trình thích hợp trên một mảnh giấy, nhưng không có cách nào giúp bạn thoát được, mà không bỏ lỡ ít nhất một phòng. Làm sao để bạn tiêu diệt vi rút trong tất cả các phòng, mà vẫn sống sót để kể lại câu chuyện? Dừng ở đây nếu bạn muốn tự tìm lời giải. Ba. Hai. Một. Nếu bản năng đầu tiên của bạn là vẽ thử các đường đi có thể lên giấy, thì bạn đã có ý tưởng đúng rồi đấy. Câu đố này liên quan đến bài toán tìm đường đi của Hamiltonian, được đặt tên theo nhà toán học Ireland ở thế kỉ 19, William Rowan Halmilton Thử thách của bài toán là tìm ra một sơ đồ có đường đi dạng Hamiltonian. Đó là đường đi qua tất cả các điểm chứa trong nó chính xác 1 lần. Bài toán này là bài toán NP đầy đủ, sẽ cực kì khó giải khi sơ đồ đủ lớn. Mặc dù có thể dễ dàng xác minh lời giải, nhưng không có công thức hay lối tắt nào để tìm ra nó, hay chứng minh nó tồn tại. Và cũng không chắc rằng liệu máy tính có thể chắc chắn tìm ra lời giải hay không. Câu đó này làm bài toán đường đi Hamiltonian thêm khó, rằng bạn phải bắt đầu và kết thúc tại những điểm cố định. Nhưng để tránh mất công vẽ một đống sơ đồ, trước tiên bạn nên biết rằng, một đường đi Hamiltonian sẽ không tồn tại với những điểm kết thúc như vậy. Bởi vì các phòng được xếp hình lưới với một số chẵn số phòng ở mỗi cạnh. Đối với cấu trúc như thế, không thể có đường đi Hamilton bắt đầu và kết thúc tại những góc đối diện nhau. Để hiểu tại sao lại như vậy, hãy liên tưởng đến một bàn cờ với một số chẵn hình vuông mỗi cạnh, mọi con đường sẽ liên tục là trắng và đen. Tổng số ô của bàn cờ cũng là số chẵn, bởi vì tích của hai số chẵn cũng là số chẵn. Do đó, đường đi Hamiltonian nếu bắt đầu ở ô đen, thì phải kết thúc ở ô trắng. Và một khi bắt đầu ở ô trắng thì phải kết thúc ở ô đen. Tuy nhiên, bàn cờ với mỗi cạnh đều là số chẵn, thì hai góc đối diện nhau lại cùng màu, nên không thể có đường Hamiltonian bắt đầu và kết thúc ở hai góc đối diện. Có vẻ như bạn đã hết cách, nếu bạn không quan sát kĩ yêu cầu và chú ý một ngoại lệ. Đúng là một khi bạn đã kích hoạt công tắc trong phòng nhiễm vi rút, nó sẽ bị phá hủy và bạn không thể quay lại. Nhưng có một phòng không bị nhiễm là lối vào, Có nghĩa là bạn không cần phải phá hủy nó trong lần đầu đi qua, và trở lại sau khi đã phá hủy một trong hai căn phòng sát bên. Căn phòng này có thể bị nhiễm vi rút khi ô thông gió mở, nhưng không sao cả. vì bạn có thể phá hủy căn phòng sau khi quay trở lại. Việc quay trở lại này cho bạn bốn lời giải khác nhau, và tương tự nếu bạn chọn phá hủy căn phòng này trước. Chúc mừng. Bạn vừa ngăn ngừa một bệnh dịch với quy mô khủng khiếp. Sau thử thách cam go này, bạn cần nghỉ ngơi. Có lẽ bạn nên chấp nhận lời đề nghị và thử làm một người bán hàng rồi đấy.