צוות המחקר שלכם מצא וירוס פרהיסטורי
שנשמר בקפאת העד,
ובודד אותו לשם עריכת מחקר.
אחרי יום עבודה ארוך,
אתם בדיוק סוגרים את המעבדה כשרעידת אדמה פתאומית מתרחשת
וגורמת להפסקת חשמל.
כשגנרטור החרום נכנס לפעולה, אזעקה מאשרת את חששותיכם הכבדים ביותר:
כל מבחנות הדוגמיות נשברו.
הוירוס מוכל בינתיים,
אבל אם לא תוכלו להשמידו,
פתחי האוורור יפתחו בקרוב וישחררו מגפה קטלנית הנישאת באויר.
בלי היסוס, אתם תופסים את חליפת החומ״ס שלכם
ומתכוננים להציל את העולם.
המעבדה היא מתחם ריבועי של 16 חדרים
עם כניסה בצידו הצפון מערבי ויציאה בצידו הדרום מזרחי.
כל חדר מקושר לחדרים הסמוכים אליו על ידי מנעול אויר,
והוירוס שוחרר בכל חדר חוץ מבכניסה.
כדי להשמיד אותו, אתם חייבים להכנס לכל חדר נגוע
ולמשוך את מתג ההשמדה העצמית שלו.
אבל יש קאץ'.
בגלל שמערכות האבטחה בנעילה,
ברגע שנכנסתם לחדר נגוע,
אתם לא יכולים לצאת בלי להפעיל את הכפתור,
וברגע שתעשו זאת,
לא תהיו מסוגלים לחזור לאותו חדר.
אתם מתחילים לשרטט מסלולים אפשריים על פיסת נייר,
אבל שום מסלול לא נראה שמוביל אתכם ליציאה
בלי לפספס לפחות חדר אחד.
אז איך אתם יכולים להשמיד את הוירוס בכל חדר נגוע
ולשרוד כדי לספר את הסיפור?
עצרו פה אם אתם רוצים להבין בעצמכם.
תשובה עוד: 3
תשובה עוד: 2
תשובה עוד" 1
אם האינסטינקט הראשון שלכם הוא לנסות לשרטט את התנועות האפשריות שלכם על הגריד,
הרעיון שלכם נכון.
הפאזל מקושר לבעיית המסלול ההמילטונית
שנקראת על שם המתמטיקאי האירי מהמאה ה 19 וויליאם רוואן המילטן.
האתגר של בעיית המסלול
הוא למצוא אם לגרף נתון יש מסלול המילטוני.
זה מסלול שמבקר בכל נקודה בתוכו בדיוק פעם אחת.
סוג זה של בעיה, שמקוטלג כמושלם NP,
ידוע לשמצה בקושי שלו כשהגרף גדול מספיק.
למרות שכל פיתרון מוצע יכול להיות מוודא בקלות,
אין לנו נוסחה אמינה או קיצור דרך למצוא אחד,
או לקבוע שאחד קיים.
ואנחנו אפילו לא בטוחים שזה אפשרי גם למחשבים
למצוא באמינות כאלה פתרונות.
החידה הזו מוסיפה טוויסט לבעיית המסלול ההמילטוני
בכך שאתם חייבים להתחיל ולסיים בנקודות מסויימות.
אבל לפני שאתם מבזבזים המון נייר גרפים,
אתם צריכים לדעת שמסלול המילטוני אמיתי
לא אפשרי עם נקודות הסיום האלו.
זה בגלל שהחדרים יוצרים צורה של גריד עם מספר זוגי של חדרים בכל צד.
בכל גריד עם סידור כזה,
מסלול המילטוני שמתחיל ונגמר בפינות מנוגדות הוא לא אפשרי.
הנה דרך אחת להבין למה.
חשבו על גריד לוח דמקה עם מספר זוגי של ריבועים בכל צד.
כל מסלול דרכו ישתנה בין שחור ולבן.
לגרידים האלה יהיה גם מספר כולל זוגי של ריבועים
בגלל שמספר זוגי כפול מספר זוגי הוא זוגי.
אז מסלול המילטוני על גריד זוגי שמתחיל בשחור
יהיה חייב להסתיים בלבן.
ואחד שמתחיל בלבן יהיה חייב להסתיים בשחור.
עם זאת, בכל גריד עם מספר זוגי,
פינות מנוגדות הן באותו צבע,
אז זה בלתי אפשרי להתחיל ולסיים מסלול המילטוני בפינות מנוגדות.
נראה שאין לכם מזל,
אלא אם אתם מביטים בכללים בקפידה ומבחינים בחריגה חשובה.
זה נכון שברגע שאתם מפעילים את המתג בחדר מזוהם,
הוא מושמד ואתם לא יכולים לחזור אליו.
אבל יש חדר אחד שלא היה מזוהם - הכניסה.
זה אומר שאתם יכולים לעזוב אותו פעם אחת בלי להפעיל את המתג
ולחזור לשם כשהשמדתם אחד משני החדרים האלה.
החדר הפינתי אולי מזוהם
מפתיחת מנעול האויר אבל זה בסדר
בגלל שאתם יכולים להשמיד את הכניסה אחרי הביקור השני.
הביקור החוזר נותן לכם ארבע אופציות למסלול מוצלח,
וסט דומה של אפשרויות אם השמדתם את החדר הזה קודם לכן.
ברכות, מנעתם מגפה בממדים אפוקליפטיים,
אבל אחרי כזו אפיזודה מלחיצה, אתם צריכים הפסקה.
אולי אתם צריכים לקחת את הצעת העבודה האחרונה להפוך לאיש מכירות נוסע.