1
00:00:08,173 --> 00:00:10,778
צוות המחקר שלכם מצא וירוס פרהיסטורי

2
00:00:10,778 --> 00:00:12,689
שנשמר בקפאת העד,

3
00:00:12,689 --> 00:00:15,170
ובודד אותו לשם עריכת מחקר.

4
00:00:15,170 --> 00:00:16,859
אחרי יום עבודה ארוך,

5
00:00:16,859 --> 00:00:20,489
אתם בדיוק סוגרים את המעבדה
כשרעידת אדמה פתאומית מתרחשת

6
00:00:20,489 --> 00:00:22,449
וגורמת להפסקת חשמל.

7
00:00:22,449 --> 00:00:27,449
כשגנרטור החרום נכנס לפעולה,
אזעקה מאשרת את חששותיכם הכבדים ביותר:

8
00:00:27,449 --> 00:00:30,734
כל מבחנות הדוגמיות נשברו.

9
00:00:30,734 --> 00:00:32,953
הוירוס מוכל בינתיים,

10
00:00:32,953 --> 00:00:34,546
אבל אם לא תוכלו להשמידו,

11
00:00:34,546 --> 00:00:40,072
פתחי האוורור יפתחו בקרוב
וישחררו מגפה קטלנית הנישאת באויר.

12
00:00:40,072 --> 00:00:42,640
בלי היסוס, אתם תופסים את חליפת החומ״ס שלכם

13
00:00:42,640 --> 00:00:46,250
ומתכוננים להציל את העולם.

14
00:00:46,250 --> 00:00:50,041
המעבדה היא מתחם ריבועי
של 16 חדרים

15
00:00:50,041 --> 00:00:54,991
עם כניסה בצידו הצפון מערבי
ויציאה בצידו הדרום מזרחי.

16
00:00:54,991 --> 00:00:58,412
כל חדר מקושר לחדרים הסמוכים אליו
על ידי מנעול אויר,

17
00:00:58,412 --> 00:01:03,030
והוירוס שוחרר בכל חדר חוץ מבכניסה.

18
00:01:03,030 --> 00:01:06,040
כדי להשמיד אותו,
אתם חייבים להכנס לכל חדר נגוע

19
00:01:06,040 --> 00:01:09,480
ולמשוך את מתג ההשמדה העצמית שלו.

20
00:01:09,480 --> 00:01:11,540
אבל יש קאץ'.

21
00:01:11,540 --> 00:01:13,822
בגלל שמערכות האבטחה בנעילה,

22
00:01:13,822 --> 00:01:16,111
ברגע שנכנסתם לחדר נגוע,

23
00:01:16,111 --> 00:01:19,580
אתם לא יכולים לצאת בלי להפעיל את הכפתור,

24
00:01:19,580 --> 00:01:21,070
וברגע שתעשו זאת,

25
00:01:21,070 --> 00:01:25,401
לא תהיו מסוגלים לחזור לאותו חדר.

26
00:01:25,401 --> 00:01:29,150
אתם מתחילים לשרטט
מסלולים אפשריים על פיסת נייר,

27
00:01:29,150 --> 00:01:31,324
אבל שום מסלול לא נראה שמוביל אתכם ליציאה

28
00:01:31,324 --> 00:01:34,410
בלי לפספס לפחות חדר אחד.

29
00:01:34,410 --> 00:01:38,341
אז איך אתם יכולים
להשמיד את הוירוס בכל חדר נגוע

30
00:01:38,341 --> 00:01:40,732
ולשרוד כדי לספר את הסיפור?

31
00:01:40,732 --> 00:01:45,592
עצרו פה אם אתם רוצים להבין בעצמכם.

32
00:01:45,592 --> 00:01:47,036
תשובה עוד: 3

33
00:01:47,036 --> 00:01:48,890
תשובה עוד: 2

34
00:01:48,890 --> 00:01:50,843
תשובה עוד" 1

35
00:01:50,843 --> 00:01:54,800
אם האינסטינקט הראשון שלכם הוא לנסות
לשרטט את התנועות האפשריות שלכם על הגריד,

36
00:01:54,800 --> 00:01:56,960
הרעיון שלכם נכון.

37
00:01:56,960 --> 00:02:00,310
הפאזל מקושר לבעיית המסלול ההמילטונית

38
00:02:00,310 --> 00:02:05,491
שנקראת על שם המתמטיקאי האירי
מהמאה ה 19 וויליאם רוואן המילטן.

39
00:02:05,491 --> 00:02:07,050
האתגר של בעיית המסלול

40
00:02:07,050 --> 00:02:11,811
הוא למצוא אם לגרף נתון יש מסלול המילטוני.

41
00:02:11,811 --> 00:02:16,081
זה מסלול שמבקר בכל נקודה בתוכו
בדיוק פעם אחת.

42
00:02:16,081 --> 00:02:19,541
סוג זה של בעיה, שמקוטלג כמושלם NP,

43
00:02:19,541 --> 00:02:24,171
ידוע לשמצה בקושי שלו כשהגרף גדול מספיק.

44
00:02:24,171 --> 00:02:27,752
למרות שכל פיתרון מוצע
יכול להיות מוודא בקלות,

45
00:02:27,752 --> 00:02:31,461
אין לנו נוסחה אמינה
או קיצור דרך למצוא אחד,

46
00:02:31,461 --> 00:02:33,542
או לקבוע שאחד קיים.

47
00:02:33,542 --> 00:02:36,091
ואנחנו אפילו לא בטוחים
שזה אפשרי גם למחשבים

48
00:02:36,091 --> 00:02:40,351
למצוא באמינות כאלה פתרונות.

49
00:02:40,351 --> 00:02:43,541
החידה הזו מוסיפה טוויסט
לבעיית המסלול ההמילטוני

50
00:02:43,541 --> 00:02:47,602
בכך שאתם חייבים להתחיל ולסיים
בנקודות מסויימות.

51
00:02:47,602 --> 00:02:50,202
אבל לפני שאתם מבזבזים המון נייר גרפים,

52
00:02:50,202 --> 00:02:52,672
אתם צריכים לדעת שמסלול המילטוני אמיתי

53
00:02:52,672 --> 00:02:55,371
לא אפשרי עם נקודות הסיום האלו.

54
00:02:55,371 --> 00:03:01,183
זה בגלל שהחדרים יוצרים צורה
של גריד עם מספר זוגי של חדרים בכל צד.

55
00:03:01,183 --> 00:03:03,442
בכל גריד עם סידור כזה,

56
00:03:03,442 --> 00:03:10,222
מסלול המילטוני שמתחיל ונגמר
בפינות מנוגדות הוא לא אפשרי.

57
00:03:10,222 --> 00:03:12,831
הנה דרך אחת להבין למה.

58
00:03:12,831 --> 00:03:17,562
חשבו על גריד לוח דמקה
עם מספר זוגי של ריבועים בכל צד.

59
00:03:17,562 --> 00:03:21,012
כל מסלול דרכו ישתנה בין שחור ולבן.

60
00:03:21,012 --> 00:03:25,702
לגרידים האלה יהיה
גם מספר כולל זוגי של ריבועים

61
00:03:25,702 --> 00:03:29,653
בגלל שמספר זוגי כפול מספר זוגי הוא זוגי.

62
00:03:29,653 --> 00:03:34,243
אז מסלול המילטוני
על גריד זוגי שמתחיל בשחור

63
00:03:34,243 --> 00:03:36,483
יהיה חייב להסתיים בלבן.

64
00:03:36,483 --> 00:03:40,294
ואחד שמתחיל בלבן יהיה חייב להסתיים בשחור.

65
00:03:40,294 --> 00:03:43,152
עם זאת, בכל גריד עם מספר זוגי,

66
00:03:43,152 --> 00:03:46,112
פינות מנוגדות הן באותו צבע,

67
00:03:46,112 --> 00:03:52,753
אז זה בלתי אפשרי להתחיל ולסיים
מסלול המילטוני בפינות מנוגדות.

68
00:03:52,753 --> 00:03:54,734
נראה שאין לכם מזל,

69
00:03:54,734 --> 00:04:00,644
אלא אם אתם מביטים בכללים בקפידה
ומבחינים בחריגה חשובה.

70
00:04:00,644 --> 00:04:04,504
זה נכון שברגע שאתם מפעילים
את המתג בחדר מזוהם,

71
00:04:04,504 --> 00:04:07,283
הוא מושמד ואתם לא יכולים לחזור אליו.

72
00:04:07,283 --> 00:04:11,473
אבל יש חדר אחד שלא היה מזוהם - הכניסה.

73
00:04:11,473 --> 00:04:14,994
זה אומר שאתם יכולים לעזוב אותו
פעם אחת בלי להפעיל את המתג

74
00:04:14,994 --> 00:04:19,978
ולחזור לשם כשהשמדתם אחד משני החדרים האלה.

75
00:04:19,978 --> 00:04:22,034
החדר הפינתי אולי מזוהם

76
00:04:22,034 --> 00:04:24,983
מפתיחת מנעול האויר אבל זה בסדר

77
00:04:24,983 --> 00:04:28,618
בגלל שאתם יכולים להשמיד
את הכניסה אחרי הביקור השני.

78
00:04:28,618 --> 00:04:32,588
הביקור החוזר נותן לכם
ארבע אופציות למסלול מוצלח,

79
00:04:32,588 --> 00:04:37,154
וסט דומה של אפשרויות
אם השמדתם את החדר הזה קודם לכן.

80
00:04:37,154 --> 00:04:42,755
ברכות, מנעתם מגפה בממדים אפוקליפטיים,

81
00:04:42,755 --> 00:04:46,169
אבל אחרי כזו אפיזודה מלחיצה,
אתם צריכים הפסקה.

82
00:04:46,169 --> 00:04:50,587
אולי אתם צריכים לקחת את הצעת
העבודה האחרונה להפוך לאיש מכירות נוסע.