את העתיד משימת פאזל החודש שעבר היה לחסוך א מסע בין כוכבים מפלגת שטח של שמונה בראשות ה מִפְעָל קצין תקשורת סגן אוהורה (בגילומו של המנוח נישל ניקולס). הצוות נכלא על ידי גזע חייזרים, הקטנאטי, על כוכב לכת ב- ערפילית שרשרת. כדי לברוח, הם צריכים למקסם את ההסתברות שלהם לבצע משימה שנראה בהתחלה שהיא מציעה רק הסתברות עגומה להצלחה.
הצוות של שמונה מיודע על המשימה בזמן שהוא מוחזק זמנית בחדר משותף שבו הם חופשיים לתקשר ולתכנן אסטרטגיה. בעוד כמה שעות, הם יובלו, בזה אחר זה, לחדר שנקרא תא הרולטה. בחדר הזה יש שמונה כפתורים מסודרים בשורה, שכל אחד מהם מתוכנת להגיב לאיש צוות אחר. כדי להטעות את הצוות, כל כפתור מסומן באופן אקראי עם שם של חבר צוות אחר. כל איש צוות רשאי ללחוץ על עד ארבעה מהכפתורים, בכל סדר. בכל פעם שהם ילחצו על כפתור, הם יראו למי הכפתור באמת שייך. בתוך ארבעת הניסיונות שלהם, הם צריכים למצוא את הכפתור שהוקצה להם. כדי שהצוות ייצא לחופשי, כולם צריכים להצליח במשימה זו. אם אפילו אחד מהם ייכשל, כולם יבוצעו. לאחר שחבר צוות מסיים את הניסיון שלו, הם צריכים להיות מבודדים ללא שום דרך להעביר מידע לאף אחד מחבריו לצוות.
סיכויי ההצלחה נראים זעירים. אם חברי הצוות בוחרים בכפתורים באופן אקראי, לכל אחד יהיה סיכוי של 1 ל-2 למצוא את הכפתור שלו. הסיכוי שכל שמונה יצליחו הוא רק 1 ל-256, או כ-0.4%.
אבל הם לא צריכים ללחוץ על כפתורים באופן אקראי. דרך אחת להגדיל את ההסתברות להצלחה יכולה להיות לאזן את כל הלחיצות על הכפתורים בדרך כלשהי. זה מביא אותנו לשאלת הפאזל הראשונה שלנו.
פאזל 1
בכמה ניתן לשפר את הסתברות ההישרדות של הצוות אם הם מוודאים שכל כפתור נלחץ באותה תדירות (במקום ללחוץ על ארבעה כפתורים באופן אקראי)?
רוב קורלט ו JPayette ענו על זה היטב, כמו על כל שאר השאלות. באשר לרעיון המרכזי החמקמק מאחורי החידות בטור זה, רוב קורלט, JPayette ו ג'וני ספנן תיאר את זה יפה, תוך כדי סשה בונון תרם פתרון ממוחשב.
הנה התשובה של רוב קורלט:
דרך אחת להבטיח שכל כפתור נלחץ מספר שווה של פעמים היא להפריד את האסירים לשתי קבוצות שוות בגודל של 4.
כל קבוצה לוחצת רק על הכפתורים המתאימים לחברי הקבוצה שלה. לפיכך, אם A, B, C ו-D נמצאים כולם באותה תת-קבוצה הם לוחצים רק על הכפתורים של A, B, C ו-D.
זה משנה את הבעיה לבקשת ההסתברות שכל אסיר מוקצה לקבוצה הנכונה שכן אז מובטח לו ללחוץ על הכפתור שלו בארבע לחיצות או פחות.
מספר הדרכים לאכלוס הקבוצה הראשונה (ולכן גם את הקבוצה השנייה) בארבעה אנשים הוא מספר הדרכים לבחירה ב-4 מתוך 8 שהם C(8, 4) = 70. לכן, המספר הכולל של הדרכים של חלוקת כולם לשתי הקבוצות היא 70.
יש רק הקצאה אחת שמקצה נכון כל אסיר לקבוצה הנכונה ולכן ההסתברות שכולם יהיו בקבוצה הנכונה וכל האסירים ישרדו היא 1/70 שזה פי 3.66 טוב יותר מה-1/256 של האסטרטגיה הקודמת. [אבל זה עדיין קטן מאוד: רק סיכוי של 1.4%.]
פאזל 2
יש דרך לשפר את הסיכויים העגומים המקוריים פי 90, לכ-36.5%, מה שנראה פלאי! אסטרטגיה זו כוללת שימוש בלולאות או שרשרות של ניחושים - ומכאן ההתייחסויות לערפילית השרשרת והקטנאטי (שרשרת זה לטינית עבור שרשרת). בצורה הבסיסית של האסטרטגיה, כל איש צוות מתחיל בלחיצה על הכפתור הנושא את שמו, לאחר מכן ממשיך לכפתור הנושא את שם איש הצוות שאליו היה שייך למעשה הכפתור הראשון, וכן הלאה, יוצר שרשרת שמות.
בוא נראה איך זה עובד בפועל. בתרשים, הכפתורים מוצגים עם התוויות שלהם בלבן. האותיות הכחולות למטה מציגות את הבעלים האמיתיים של הכפתורים. כשחברת הצוות הראשונה, A, נכנסת לתא הרולטה, היא לוחצת תחילה על כפתור A. זה הכפתור של C, אז היא לוחצת על כפתור C הבא, ואז על כפתור E ולבסוף על כפתור F, שהוא למעשה הכפתור של A עצמה, אז היא מצאה אותו בהצלחה בארבעה ניסיונות. שימו לב שהלחצנים ACEF יוצרים לולאה סגורה של ארבעה כפתורים. כאשר חברי הצוות C, E ו-F יתחלפו בתורם, הם גם יסתובבו באותה לולאה סגורה, החל ממקומות משלהם, וגם ימצאו כפתורים משלהם בארבעה ניסיונות.
לסידור זה יש גם שתי לולאות קטנות יותר של שני כפתורים כל אחת: BD ו-GH. ארבעת חברי הצוות הללו ימצאו כפתורים משלהם תוך שני ניסיונות. אז, עם ההסדר הזה, כל אנשי הצוות יצליחו, והם יזכו בחופש שלהם. ברור שאם הסידור יכיל רק לולאות באורך 4 או פחות, כל אנשי הצוות יצליחו וישתחררו. אם, לעומת זאת, יש לולאה בודדת של 5 או יותר, אז כל חברי הצוות באותה לולאה לא יצליחו למצוא את הכפתור שלהם בארבעה ניסיונות, והצוות יבוצע. על מנת למצוא את ההסתברות להצלחה, נוכל למצוא את ההסתברות לקבל לולאה של 5, 6, 7 או 8, לחבר אותם ולהחסיר את הסכום הזה מ-1. זה קל יותר לחישוב מאשר בדרך אחרת, כי עבור שמונה כפתורים, יכולה להיות רק לולאה אחת עם 5, 6, 7 או 8 חברים.
יש 8! דרכים שונות לסדר שמונה כפתורים. אבל כאשר אנו יוצרים לולאות, אותה לולאה אחראית לשמונה מהסידורים הללו (ABCDEFGH יוצר את אותה לולאה כמו BCDEFGHA, שזהה ל-CDEFGHAB וכו'). אז ההסתברות לקבל לולאה בגודל 8 היא (8!/8)/8!, שזה פשוט 1/8. באופן דומה, ההסתברות ללולאה בגודל 7 היא 1/7, בגודל 6 היא 1/6, ובגודל 5 היא 1/5. לכן, ההסתברות להצלחה לצוות חסר הפחד שלנו היא 1 - (1/5 + 1/6 + 1/7 + 1/8), או 36.5%, כפי שהוזכר קודם לכן.
האסטרטגיה שלעיל עובדת עבור כל מספר של אסירים, והשיפור בסיכויים ביחס לגישה האקראית גדל במהירות ככל שמספר זה גדל. זה בערך פי שבעה עבור ארבעה אסירים, פי 24 עבור שישה, פי 93 עבור שמונה ומדהים (3.8 × 1029)-קיפול עבור 100 אסירים. המפתח להבנת הגידול העצום הזה הוא שהשיטה קושרת את ההצלחה או הכישלון של כל אחד מחברי הקבוצה לזו של האחרים. במידה רבה מאוד, כולם מצליחים או נכשלים ביחד. ההסתברות של הקבוצה להצליח לא יורדת יותר מדי מזו של אדם בודד, יורדת רק מ-50% לאסיר בודד ל-30.69% ככל שמספר האסירים גדל ללא הגבלה. מצד שני, ההסתברות שגישה אקראית או אפילו גישת "לחיצות על כפתור שווה" יצליחו יורדת במהירות לקרוב מאוד לאפס אפילו עבור מספר קטן של אסירים.
אם ההיגיון מאחורי האסטרטגיה הזו עדיין נראה מעורפל, הנה ניתוח של בעיית 100 האסירים בזה סרטון מעולה של Veritasium.
פאזל 3
הפאזל הזה היה על סגן אוהורה שנזכר במשחק ילדות, שהיה בעצם אותו פאזל, אבל עבור שישה אנשים. כרמז, הצעתי לפתור את הבעיה עבור ארבעה אנשים. עכשיו, כשיש לנו את הנוסחה, אנחנו יכולים בקלות לחשב את ההסתברויות.
עבור ארבעה אנשים, ההסתברות שהלולאה הארוכה ביותר היא רק 2 או 1 היא: 1 - (1/3 + 1/4) או 41.7% עם רווח של פי שבעה לעומת בחירה אקראית.
עבור שישה אנשים, ההסתברות שהלולאה הארוכה ביותר היא 3, 2 או 1 היא: 1 - (1/4 + 1/5 + 1/6) או 38.3% עם רווח של יותר מפי 24 לעומת בחירה אקראית.
פאזל 4
ככל שהסיפור שלנו נמשך, מתברר שאחד מהקטנאטים לא אהב במיוחד מִפְעָל צוות ועוקב אחריהם מרחוק. הוא חושד שהם המציאו אסטרטגיה יעילה על סמך הדיאגרמה של אוהורה. הוא נחוש לסכל את התוכנית שלהם על ידי החלקה לחדר ושינוי מכוון של סדר תוויות הכפתורים לפני שהרולטה מתחילה. האם הוא מצליח לסכל את התוכנית? מה על הנחיתה להקפיד במיוחד להסתיר?
מוקדם מאוד בדיון האסטרטגי של הצוות, עיניו של אוהורה הצטמצמו לפתע. היא נתנה אות לצוות שלה, והיא עברה לדבר בניקולז, והכריזה, "כל דיון נוסף בניקולז, בבקשה." ניקולזה הייתה שפה חדשה שאוהורה המציאה בתחילת הקריירה שלה בדיוק עבור מצבים מסוג זה, כדי לעקוף את השימוש במתרגמים אוניברסליים. "בטח שמת לב לקטנאטי החשוד הזה," היא המשיכה. "הוא יכול לנסות לחבל בנו, אז אנחנו צריכים לשנות את התוכנית שלנו. זה מה שאנחנו צריכים לעשות..."
אוהורה תיארה את התוכנית החדשה עד שהיתה מרוצה שכל אחד מחברי הצוות שלה מכיר אותה היטב. ואז היא הרהרה, במבט רחוק בעיניה, "קראתי לניקולז על שם שחקנית איקונית מהמאה ה-20. אני שמח שהתעקשתי שצי הכוכבים יעשה את זה כסטנדרט בכל הספינות שלנו".
היא הסתובבה בחזרה לצוות. "זה הכל, קצינים. אתה יודע מה לעשות!"
אנחנו לא יודעים בדיוק מה אוהורה אמרה לצוות שלה. אבל ל-JPayette ולרוב קורלט היה רעיון די טוב. הנה שוב רוב קורלט:
אם קטנאטי הרשע שומע שהם משתמשים באסטרטגיה הזו, הוא יכול להחליף את השמות המוצגים בתצוגה כדי להבטיח שיש מחזור ארוך מ-4.
כדי לשבור את זה אז האסירים צריכים להסכים לצו סודי אשר עושה אקראי את הרצף. הם עושים זאת על ידי אמירת משהו כמו "אם אתה רואה את השם של אוהורה, אז עבור אל הכפתור המסומן צ'קוב. אם אתה רואה את שמו של צ'קוב מוצג עבור אל הכפתור המסומן סמית' וכו'."
בדרך זו, הסדר מחדש על ידי ה-Catenati אינו משנה מכיוון שהוא עובד רק אם אתה יודע את הדרך שבה הצוות יגיב לשמות על התצוגות. עם זאת, הם צריכים לשמור כל הזמנה מחדש בסוד, אחרת זה יכול להישבר שוב.
כפי שראינו, אוהורה הבטיח שהסוד יישמר בטוח. כל אחד מחברי הצוות רק היה צריך להשתמש באותה הזמנה סודית ולהבטיח שקטנאטי הרשע לא ידע מה זה. למעשה, הסדר ששונה על ידי Catenati הרשע למעשה הגדיל את ההסתברות של הצוות להצליח!
זה מה שקרה. אוהורה היה הראשון שנלקח לתא הרולטה. היא לחצה על שלושה כפתורים. אף אחד לא היה שלה. האם היא צריכה להיות עצובה או שמחה? היא עצרה את נשימתה ולחצה על הרביעית. היא מצאה את הכפתור האמיתי שלה!
היא ידעה שכולם עומדים להינצל.
פאזל 5
לאיזה גבול מתקרב אחוז ההצלחה המקסימלי כאשר גודל הצד הנחיתה גדל ללא הגבלת זמן? האם תוכל להסביר מדוע השיטה הזו יעילה הרבה יותר מלחיצה אקראית על כפתור?
JPayette כתב:
כל האמור לעיל מכליל באופן ישיר לצוות של 2n כל אחד מהם רשאי ללחוץ לכל היותר n כפתורים. מפאזל 2, אנו מסיקים שהסיכוי שלהם להצליח הוא
1 - (סיכום מעל k בֵּין n + 1 ו-2n של 1/k).
ניתן להשוות את הסכום עם האינטגרל של 1/x על פני המרווח [n, 2n], מה שמאפשר לנו להוכיח את זה כ n גדל לאינסוף, ההסתברות לעיל יורדת להתכנס ל-1 − ln(2) ≈ 30.6% מדהים. [למעשה 30.69% עד שני מקומות עשרוניים.]
רוב קורלט הוסיף:
אם אינך מכיר את האינטגרציה, תוכל להגיע במהירות לתשובה משוערת על ידי חישוב באמצעות גיליון אלקטרוני. הגעתי ל-0.307 פעם אחת n הגיע לכ-750 שזה מדויק עד 3 מקומות עשרוניים.
כבר הסברנו לעיל מדוע שיטה זו עובדת. כל הלולאות ארוכות מ-1 משותפות למספר חברי צוות. אז ההצלחות והכישלונות שלהם נמצאים בקורלציה גבוהה. זה המחשה של העיקרון "כולם בשביל אחד ואחד בשביל כולם". ישר מהמדריך של צי הכוכבים!
תודה לכל התורמים שלנו. JPayette ורוב קורלט הגישו שניהם תשובות ראויות לפרס שגרמו לעמודת הפתרון הזו להיראות כמעט מיותרת. למרבה הצער, אני חייב להיצמד לכלל שלנו של בחירת מנצח אחד לכל טור חידה. פרס התובנות מגיע ל-JPayette כהוקרה על תרומות כאן ובפאזל הקודם. מזל טוב! רוב קורלט, התרומות שלך לא יישכחו.
נתראה בחודש הבא לתובנות חדשות!
