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.
گروه تحقیقاتی شما یک ویروس ماقبل تاریخ را کشف کرده است که در لایههای یخ باقی مانده و برای مطالعه جدا شده است. بعد از یک شب کار طولانی، میخواهید آزمایشگاه را تعطیل کنید که ناگهان زلزلهای ناگهانی باعث قطع شدن برق میشود. وقتی برق اضطراری وصل میشود، صدای آژیر بدترین ترس شما را تایید میکند: تمام ظرفهای نمونه شکسته است. ویروس فعلا تحت کنترل است، اما اگر نتوانید آن را نابود کنید، به زودی دریچهها باز خواهند شد و طاعونی مرگبار در هوا پخش خواهد شد. بی لحظهای تعلل لباس مخصوص خود را برمیدارید و برای نجات دنیا آماده میشوید. آزمایشگاه مجموعهای چهار در چهار از ۱۶ اتاق است و ورودی در گوشه شمال غربی وخروجی در گوشه جنوب شرقی قرار دارد. هر اتاق با یک قفل هوا به اتاقهای مجاور راه دارد، و ویروس در همه اتاقها غیر از اتاق ورودی آزاد شده است. برای نابود کردن آن، باید به هر اتاق آلوده وارد شوید و سوییچ خودنابودگر اضطراری آن را بکشید. اما مشکلی هست. از آنجا که سیستم ایمنی فعال شده است، وقتی به اتاق آلوده وارد میشوید نمیتوانید بدون فعال کردن سوییچ خارج شوید، و وقتی این کار را کردید، دیگر نخواهید توانست به آن اتاق برگردید. راههای ممکن را روی کاغذی میکشید، اما به نظر میرسد هیچ راهی وجود ندارد که بدون جا انداختن هیچ اتاقی به خروجی برسید. پس چطور میتوانید ویروس را در تمام اتاقهای آلوده نابود کنید و برای تعریف داستان نجات پیدا کنید؟ اگر میخواهید خودتان راه حل را پیدا کنید اینجا توقف کنید. جواب در: ۳ جواب در: ۲ جواب در: ۱ اگر به نظرتان باید اول مسیرهای ممکن را روی یک شبکه بکشید، ایده درستی دارید. این معما به مسئله راههای همیلتون مربوط است که نام آن از ریاضیدان ایرلندی قرن ۱۹ام ویلیام روان همیلتون گرفته شدهاست. چالش مسئله مسیر فهمیدن این است که آیا گراف داده شده مسیر همیلتون دارد یا نه. آن همان راهی است که از تمام نقاط شبکه دقیقاً یک بار عبور میکند. اینگونه مسائل که در دسته NP کامل طبقهبندی میشوند، در صورت بزرگ بودن گراف بسیار دشوار هستند. هرچند صحت هر راه پیشنهادی را میتوان به سادگی بررسی کرد، هیچ فرمول معتبر و میانبری برای پیدا کردن جواب، و حتی اطمینان از وجود آن وجود ندارد. و حتی مطمئن نیستیم کامپیوترها هم بتوانند جوابی قابل قبول برای این مسائل پیدا کنند. این معما مسئله مسیر همیلتون را تاب داده و نقاط شروع و پایان مسیر مشخص هستند. اما پیش از اینکه هزار کیلو کاغذ حرام کشیدن گراف کنید، باید بدانید که یک مسیر همیلتون واقعی با این نقاط ابتدا و انتها ممکن نیست. به این دلیل که اتاقها شبکهای با تعداد اتاقهای زوج در هر سمت را شکل دادهاند. در هر شبکه با این پیکربندی، هر مسیر همیلتونی که نقاط آغاز و پایان آن در گوشههای مقابل باشد غیر ممکن است. این راهی است برای درک علت آن. یک صفحه شطرنجی را با تعداد مربعهای زوج در هر طرف در نظر بگیرید. هر مسیری یکی در میان از خانههای سیاه و سفید عبور میکند. تعداد خانههای این شبکهها هم زوج است زیرا هر عدد زوج در هر عدد زوج عددی زوج خواهد شد. پس هر مسیر همیلتون که در یک شبکه با ابعاد زوج از یک خانه سیاه شروع شود باید در یک خانه سفید به پایان برسد. و اگر از سفید شروع شود باید در سیاه تمام گردد. از آنجا که در یک شبکه با ابعاد زوج گوشههای مخالف همرنگ هستند، پس غیر ممکن است بتوان یک مسیر همیلتون را در گوشههای مقابل شروع و تمام کرد. به نظر میرسد هیچ شانسی ندارید، مگر اینکه دوباره به قوانین نگاه کنید و متوجه یک استثنای بسیار مهم شوید. درست است که اگر سوییچ یک اتاق آلوده را فعال کنید، نابود میشود و دیگر هرگز نمیتوانید به آن برگردید. اما یک اتاق هست که هنوز آلوده نشده - ورودی. یعنی میتوانید یک بار بدون کشیدن سوییچ آن را ترک کنید و وقتی هرکدام از این اتاقها را نابود کردید باز به آن برگردید. اتاق گوشه هم به خاطر باز ماندن قفل هوا آلوده میشود اما اشکالی ندارد چون میتوانید ورودی را بار دومی که داخل آن هستید نابود کنید. این کار چهار انتخاب برای یک مسیر موفق به شما میدهد، و همچنین به همین ترتیب اگر اول این اتاق را نابود کنید. آفرین. شما از شیوع یک بیماری آخرالزمانی جلوگیری کردید، اما بعد از همچین کار پراسترسی به استراحت احتیاج دارید. شاید بد نباشد دوباره نگاهی به آن پیشنهاد فروشندگی دوره گرد بیاندازید.