 |
|
 |
||
|
||||
 |
האסירים הצליחו במשימתם, אך במקום לתת להם חנינה מנהל הכלא (שהוא סדיסט לא קטן ובכלל, ממתי מנהלי כלא מוסמכים להעניק חנינות?) הודיע לאסירים שכל אחד מהם מקבל את אחד משלושת השמות האמצעים - אייל, צבי, ודב. למחרת כל אחד מהם יכנס לחדר המכיל את רשימת כל השמות האמצעיים פרט לשלו ויצטרך לנחש את שמו האמצעי. אסיר שכבר ניחש לא יוכל לתקשר עם מי שלא. המנהל לא טרח לאיים בשכר ועונש, אך רמז שכדאי מאוד שכולם ינחשו נכונה כבר בנסיון הראשון - איזה אסטרטגיה תיתן להם סיכוי של שלושים אחוז לפחות להישאר בחיים1? ___ 1. אם לזה אפשר לקרוא חיים. כבר עדיף לחלק שלל עם פיראטים. |
 |
 |
 |
|
|
|
||
|
||||
|
האם נדרש רמז, או שגם ככה השאלה פשוטה מדי? | |
|
|
|
|
|
||
|
||||
|
לפחות לי זה לא פשוט. האם מובטח משהו על התפלגות השמות? | |
|
|
|
|
|
||
|
||||
|
בשלב הזה כבר ברור שמנהל הכלא הוא פסיכופאט לא צפוי, ואין לאסירים מושג כיצד יחלק את השמות. | |
|
|
|
|
|
||
|
||||
|
הסתברות או תורת המשחקים? | |
|
|
|
|
|
||
|
||||
|
אני מבין נכון שזה הכל או כלום? שהפיתרון הוא אסטרטגיה שנותנת 30% שכולם ינחשו נכונה? יש לי הוכחה (קלה מדי כנראה) שזה לא אפשרי... | |
|
|
|
|
|
||
|
||||
|
כן, כדי להישאר בחיים כולם עד האחרון צריכים לנחש נכונה. האם תוכל לשתף בהוכחה? |
|
|
|
|
|
|
||
|
||||
|
לא, היתה לי טעות ב''הוכחה''. | |
|
|
|
|
|
||
|
||||
|
ֿאוקי, אז אחכה לפתרון :) | |
|
|
|
|
|
||
|
||||
|
כל החכמים כאן שותקים, לי נדרש רמז. | |
|
|
|
|
|
||
|
||||
|
כל רמז שאני מצליח לחשוב עליו יהפוך את הפיתרון לטרוויאלי. כרגע אני בנסיעות/טיסות עם חיבור אינטרנט לא רציף. אם עד חג ההודיה שבעוד שבוע וחצי אף אחד לא יפתור, אכתוב את הפתרון (הפשוט למדי). | |
|
|
|
|
|
||
|
||||
|
אני מודה בבושה שלקח לי יומיים עד שנפל האסימון. בתור רמז, קבל שתי ורסיות קלות יותר של החידה. את הראשונה אני מניח שאתה מכיר: חידה 1 - עשרה אנשים בטור עורפי. כל אחד רואה רק את אלה שלפניו. שמים לכל אחד מהם על הראש כובע שחור או לבן.כל אחד בתורו, החל מהאחרון, אומר צבע (שחור או לבן) כשכולם שומעים. מותר להם לתאם אסטרטגיה מראש. איך לפחות תשעה יקלעו לצבע הכובע שעל ראשם? חידה 2 - הנח שלכל המשתתפים זכרון מעולה. איך תרחיב את הפתרון של החידה הראשונה למקרה שבו מספר צבעי הכובעים גדול מ-2 (אבל ידוע מראש)? |
|
|
|
|
|
|
||
|
||||
|
את התשובות לשתי הוורסיות שלך אני מכיר, והחידה המקורית שקולה למקרה של שלושה צבעים ושכל אחד רואה את הכובעים של כל האחרים. ההבדל הוא שאף אחד לא יודע מה אלה שלפניו ניחשו, בניגוד לוורסיות שלך. | |
|
|
|
|
|
||
|
||||
|
לכן זה רק רמז ולא הפתרון. הבדל נוסף הוא שכולם צריכים לנחש נכון, אבל בהסתברות של... (חישוב ההסתברות המדויקת ממש פשוט). |
|
|
|
|
|
|
||
|
||||
|
אז אם אני מבין נכון, נניח שהכובעים (או השמות) ממוספרים 0, 1, 2 והאסירים מגרילים מספר בתחום הזה ומחליטים ביניהם להניח שסכום כל המספרים מודולו 3 הוא המספר שהגרילו. כעת, כל אחד רואה את כל השמות/כובעים/מספרים חוץ משלו, ואומר שהשם/כובע שלו הוא המשלים מודולו 3 למספר שהוגרל. ככה כולם צודקים ביחד בהסתברות של שליש. | |
|
|
|
|
|
||
|
||||
|
וואו. יופי של חידה! | |
|
|
|
|
|
||
|
||||
|
תודה! ___ שכחתי לכתוב באותיות קטנות שההשתתפות אסורה על הקשה המקשה ובני משפחתו :) כל הכבוד לו על הפיצוח! |
|
|
|
|
|
|
||
|
||||
|
נזכרתי בחידה דומה, אבל הפעם בלי אסירים: לשני שחקנים יש על הראש ערימה של אינסוף כובעים, שחורים ולבנים בסדר אקראי, שניהם צריכים להגיד בו זמנית (נגיד, על פי סימן) מספר טבעי לבחירתם. אם שניהם בחרו מספרים כך שהכובע על ראשם שזה מספרו (הכי תחתון הוא 1, זה שעליו הוא 2 וכך הלאה) הוא לבן הם נצחו, אחרת הם הפסידו. האם יש אסטרטגיה שנותנת להם סיכוי יותר טוב מ-0.25 לנצח? | |
|
|
|
|
|
||
|
||||
|
שניהם יכולים לראות את הערימה שעל ראש האחר? אם כן, כנראה שיש לי משהו כך שההסתברות מתכנסת לשליש. אני בכיוון? |
|
|
|
|
|
|
||
|
||||
|
כן. כן! |
|
|
|
|
|
|
||
|
||||
|
נראה לי שהבנתי. האם הסדרה אכן מתכנסת לשליש או סתם גבוהה מרבע? | |
|
|
|
|
|
||
|
||||
|
התשובה, אם הבנתי נכון, היא: השחקנים מהמרים על כך שהכובעים התחתונים על ראשם זהים. אם אינם, הם הפסידו (50%), אם הם כן, וגם לבנים (25%), הם נצחו. במידה שהכובעים זהים אך שחורים (25%), הם עוברים לכובע הבא - שם הם חוזרים על המשחק. לכן האלגוריתם הוא בחירת מספר הכובע הלבן התחתון ביותר של השחקן השני. וההסתברות לניצחון היא סכום הסדרה רבע בחזקת N (מאחד לאינסוף). |
|
|
|
|
|
|
||
|
||||
|
ואמנם שליש, כמו שפסק המקשה: |
|
|
|
|
|
|
||
|
||||
|
זה אכן הפתרון. (אתה באמת צריך את וולפרם בשביל סכום של סדרה הנדסית?) |
|
|
|
|
|
|
||
|
||||
|
אח שלי, אני תשע שנות לימוד אני. צברתי כמה חורים בהשכלה. ובכל מקרה, תודה על שאלה יפה. |
|
|
|
|
|
|
||
|
||||
|
לא חייבים לסכום סדרה הנדסית, הם מצליחים אם ורק אם שני כובעים שחורים מופיעים לפני שמופיעים שחור-לבן או לבן-שחור וההסתברות לכך היא שליש. | |
|
|
|
|
|
||
|
||||
|
דרך אגב, ההסתברות המקסימלית האפשרית בשאלה הזו לא ידועה. יש אסטרטגיה שנותנת 0.35 ויש חסם מלעיל של 0.375. | |
|
|
|
|
|
||
|
||||
|
מה האסטרטגיה שנותנת 0.35 ? | |
|
|
|
|
|
||
|
||||
|
לרגל הופעתך הנדירה במחוזותינו, קבל שי צנוע שיגזול שלוש שניות מזמנך. בין הפותרים יוגרל כרטיס השתתפות בהפגנה בירושליים מחר. |
|
|
|
|
|
|
||
|
||||
|
יכול להיות, אבל הן לא ממש נראות לי נשות היי-טק או מדעניות טילים. | |
|
|
|
|
|
||
|
||||
|
אל תהיה גזען! | |
|
|
|
|
|
||
|
||||
|
יש כמה אסטרטגיות, קצת שרירותיות. אחת מהן מתוארת במאמר הזה (משפט 2): וגם נראה שיש חסם העליון טוב משזכרתי: 0.3616 |
|
|
|
|
|
|
||
|
||||
|
תודה | |
|
|
|
|
|
||
|
||||
|
יפה! | |
|
|
|
|
|
||
|
||||
|
החידה הזו קשורה לבעיה פתוחה: יש n שחקנים במקום 2 וכל השאר זהה. האם יש אסטרטגיה שמבטיחה הסתברות הצלחה חיובית קבועה בלי תלות ב-n או שההסתברות דועכת לאפס כאשר n שואף לאינסוף? | |
|
|
|
|
|
||
|
||||
|
האם אתה מאתגר אותנו למצוא אסטרטגיה עם הסתברות הצלחה חיובית קבועה, או שאתה מספר לנו שהוכחת/הפרכת קיומה זאת בעיה פתוחה? ____ כי בנתיים אני תקוע בתוחלת של חצי בחזקת לוג n, שדועכת לה בשקדנות עם השאיפה לאינסוף ... |
|
|
|
|
|
|
||
|
||||
|
אני מספר שזו בעיה פתוחה להכריע האם יש או אין אסטרטגיה שמבטיחה הסתברות הצלחה חיובית קבועה, ללא תלות ב-n. יש אסטרטגיה ידועה שנותנת הסתברות הצלחה אחד חלקי לוג n (שזה הרבה יותר טוב מחצי בחזקת לוג n). ידוע גם שאם דורשים מהם להצביע על הכובע השחור הראשון, אז אי אפשר להשיג יותר מאחד חלקי לוג. | |
|
|
|
|
|
||
|
||||
|
מה האסטרטגיה הנ״ל? (אם היא פשוטה מספיק להסבר להדיוטות) |
|
|
|
|
|
|
||
|
||||
|
היא פשוטה ודומה למדי לפתרון החידה המקורית. נסתכל על המיקום של הכובע השחור הראשון על ראש כל משתתף. בהסתברות גבוהה (הכנס חישוב מתאים) כל המיקומים הללו קטנים מלוג n. המשתתפים מנחשים מה סכום המיקומים מודולו לוג n. אם הם צודקים (מה שקורה בהסתברות אחד חלקי לוג n), אז כל אחד יכול לחשב את מיקום הכובע השחור הראשון על ראשו. | |
|
|
|
|
|
||
|
||||
|
תודה על ההסבר! | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |