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.
Tim risetmu telah menemukan virus prasejarah yang tersimpan dalam lapisan es dan kemudian menyimpannya untuk diteliti lebih jauh. Setelah bekerja sampai larut malam, kamu baru saja mengunci lab saat tiba-tiba terjadi gempa bumi dan mematikan tegangan listrik. Saat generator darurat menyala, bunyi alarm menegaskan kekhawatiranmu: semua botol sampel telah rusak. Saat ini virus masih tertahan, namun jika kamu tak menghancurkannya, lubang angin akan segera terbuka dan melepaskan wabah mematikan ke udara. Tanpa ragu, kamu meraih baju HazMat dan bersiap menyelamatkan dunia. Lab terdiri dari 16 ruangan yang tersusun empat kali empat dengan pintu masuk di sudut barat laut dan pintu keluar di tenggara. Masing-masing ruangan yang berdekatan terhubung oleh bilik kedap udara, dan virus telah memasuki setiap ruangan kecuali pintu masuk. Untuk menghancurkannya, kamu harus masuk ke tiap ruangan dan menarik tuas penghancur darurat. Namun, ada masalah. Karena sistem keamanan dalam kondisi terkunci, tiap memasuki ruangan yang terkontaminasi, kamu tidak dapat keluar tanpa mengaktifkan tuas darurat, dan jika kamu telah melakukannya, kamu tidak bisa kembali ke ruangan tadi. Kamu mulai menggambar rute yang memungkinkan di secarik kertas, namun tak ada yang bisa membawamu ke pintu keluar tanpa melewatkan satu ruangan pun. Jadi bagaimana cara menghancurkan virus di tiap ruangan dan tetap hidup untuk menceritakannya? Tekan tombol jeda sekarang jika kamu ingin menyelesaikannya sendiri. Jawab dalam: 3 Jawab dalam: 2 Jawab dalam: 1 Jika insting pertamamu adalah menggambar semua rute yang mungkin, kamu hampir benar. Teka-teki ini berhubungan dengan soal jalur Hamilton yang dinamai dari ahli matematika Irlandia abad ke-19, William Rowan Hamilton. Tantangan dari soal jalur adalah menemukan jalur Hamilton dalam sebuah gambar. Jalur Hamilton adalah rute yang melewati tiap titik dalam gambar hanya sekali. Jenis soal ini, yang dikategorikan sebagai soal NP-Complete, terkenal sangat sulit terutama untuk gambar berukuran besar. Meskipun jawaban yang ada bisa diperiksa dengan mudah, tidak ada rumus baku atau jalan pintas untuk menjawabnya, atau sekadar mengetahui jawabannya ada atau tidak. Dan kita juga tidak tahu apakah sebuah komputer dapat diandalkan untuk menyelesaikannya. Teka-teki ini memberi tambahan syarat dalam soal jalur Hamilton dimana kamu harus mulai dan berakhir di titik tertentu. Sebelum kamu menghabiskan berton-ton kertas, kamu harus tahu soal jalur Hamilton yang sesungguhnya mustahil dengan adanya syarat ini. Itu karena kotak yang terbentuk punya jumlah ruang yang sama di tiap sisinya. Dengan kombinasi demikian, jalur Hamilton dengan titik awal dan akhir di sudut yang berseberangan itu mustahil. Berikut cara memahaminya. Bayangkan sebuah papan catur dengan jumlah kotak sama di tiap sisi. Tiap jalur yang dilewati akan berganti warna hitam dan putih. Jumlah kotak di dalam papan pasti genap karena angka genap dikalikan angka genap hasilnya pasti genap pula. Sehingga jalur Hamilton pada papan bersisi sama yang dimulai dari warna hitam sudah pasti berakhir di warna putih. Dan yang dimulai dari warna putih, pasti berakhir di warna hitam. Namun pada setiap papan sama sisi, sudut yang berseberangan memiliki warna yang sama, sehingga menyelesaikan jalur Hamilton di sudut yang berseberangan itu mustahil. Sepertinya kamu tak akan berhasil, kecuali jika kamu teliti lagi aturannya dan perhatikan ada sebuah pengecualian. Benar, setelah kamu mengaktifkan tuas darurat dalam ruangan yang terkontaminasi, ruangan akan hancur dan kamu tidak bisa masuk lagi. Tapi ada satu ruangan yang belum terkontaminasi - pintu masuk. Artinya kamu bisa meninggalkan ruangan tersebut tanpa menarik tuas darurat dan kembali setelah kamu menghancurkan salah satu dari kedua ruangan ini. Ruangan ini mungkin sudah terkontaminasi dari bilik kedap udara yang terbuka, tapi tidak apa karena kamu bisa menghancurkannya saat kamu kembali ke ruangan tersebut. Metode ini menyediakan empat pilihan jalur yang mungkin, dan pilihan lain yang serupa jika kamu menghancurkan ruangan ini terlebih dahulu. Selamat. Kamu sudah mencegah penyebaran kiamat pandemi, namun setelah semua stres itu, kamu pasti butuh istirahat. Mungkin kamu sebaiknya ganti profesi menjadi pedagang keliling.