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.
Araştırma ekibiniz, dondurulmuş ve araştırılmak üzere saklanan tarih öncesi bir virüs buldu. Uzun bir gece çalışması ardından, tam laboratuvarı kapatmak üzereyken aniden bir deprem olur ve elektrik kesilir. Acil durum jeneratörleri devreye girer, alarm çalar ve korktuğunuz başınıza gelir: tüm virüs flakonları kırılmıştır. Virüs şimdilik kontrol altında olsa da yok etmediğiniz takdirde, havalandırma yakında açılacak ve havayla ölümcül bir veba yayılacak. Tereddüt etmeden HazMat giysinizi giyiyorsunuz ve dünyayı kurtarmaya girişiyorsunuz. Laboratuvar her biri 4 odalı 4 kat ve toplam 16 odadan oluşuyor, girişi kuzeybatı, çıkışı ise güneydoğu cephesinde. Her oda bir diğerine hava kilidiyle bağlı ve virüs giriş hariç her odada yayıldı. Yok etmek için her enfekte odaya giriş yapmanız ve acil durum kendini yok etme şalterini çalıştırmanız lazım. Ancak bir sorun var. Güvenlik sistemi kilitli olduğundan, enfekte odaya giriş yaptığınız zaman şalteri çalıştırmadan çıkamazsınız ve eğer çalıştırırsanız, o odaya geri giremezsiniz. Bir kağıda mümkün olan çıkış yollarını çiziyorsunuz, fakat hiçbir yol en az bir oda kaçırmadan sizi çıkışa götürmüyor. Peki nasıl enfekte her odadaki virüsü yok edip hayatta kalarak bu olayı anlatabilirsiniz? Kendiniz çözmek istiyorsanız burada durdurun. Cevap için: 3 Cevap için: 2 Cevap için: 1 İlk içgüdünüz mümkün hareketlerinizi bir grafik üstünde göstermekse, doğru düşündünüz demektir. Hamilton yolu problemi ile bağlantılı bu bulmaca adını 19. yüzyıl İrlandalı matematikçi William Rowan Hamilton'dan alır. Yol probleminin zorluğu eldeki grafikte Hamilton yolu olup olmadığını bulabilmektir. Bu yol, her noktaya yalnızca bir kez uğranarak izlenen bir güzergâhtır. NP-tam olarak sınıflandırılan bu tür bir problem, grafik yeteri kadar büyükse bilindiği gibi epey zordur. Sunulan çözümler kolaylıkla doğrulansa da çözüm ve hatta bir çözümün olduğuna dair ne güvenilir bir formül, ne de bir kısayol vardır. Bilgisayarların bile güvenilir bir çözüm bulabileceğinden emin değiliz. Bu bulmaca Hamilton yolu problemine belli bir noktalarda başlayıp bitirmemiz gereken bir zorluk ekliyor. Bir yığın grafik kağıdı harcamadan önce, doğru bir Hamilton yolunun bu noktalarla mümkün olmadığını bilmenizde fayda var. Çünkü odalar her iki tarafta da çift sayı olduğu zaman bir tablo oluşturuyor. Bu şekilde ayarlanan her tabloda birbirine zıt noktalarda başlayıp biten bir Hamilton yolu imkansızdır. Anlamak için bir örnek verelim. Her tarafında çift sayıda kareler olan bir satranç tahtası düşünün. Üzerinden geçeceğiniz her yol siyah ve beyaz arasında değişecektir. Ayrıca bu tabloların toplam kare sayısı da çift olacaktır çünkü iki çift sayıyı çarptığınızda sonuç yine çift olur. Yani çift sayılı bir tabloda siyah ile başlanan bir Hamilton yolu beyaz üzerinde bitecektir. Beyaz üzerinde başlanan yol ise siyah ile bitecektir. Ancak, çift sayılı her tabloda zıt köşeler aynı renktedir, bu yüzden bir Hamilton yolunu zıt köşelerde başlayıp bitirmek imkansızdır. Şansınız yok gibi görünüyor, tabii eğer kurallara dikkatlice bakıp bir istisna fark etmediyseniz. Enfekte bir odadaki şalteri indirdiğinizde her şeyin yok olduğu ve geri dönemeyeceğiniz doğru. Ancak enfekte olmayan bir oda var: giriş. Bu da demektir ki şalteri indirmeden o odayı bir kez terk edip bu iki odadan birini yok ettikten sonra oraya geri dönebilirsiniz. Köşe oda hava kilidinin açılmasıyla enfekte olmuş olabilir ama sorun yok çünkü girişi ikinci ziyaretinizden sonra yok edebilirsiniz. Geri dönüş size başarılı bir güzergâh için dört seçenek ve eğer önce bu odayı yok ettiyseniz benzer bir grup seçenek sunuyor. Tebrikler. Apokaliptik ölçülerde bir salgını önlediniz ama böyle bir uğraşın ardından molaya ihtiyacınız var. Belki de şu seyyar satıcı işini kabul etseniz iyi olur.