בתשובה ליוסי, 18/11/22 16:00
 |
|
 |
||
|
||||
 |
נזכרתי בחידה דומה, אבל הפעם בלי אסירים: לשני שחקנים יש על הראש ערימה של אינסוף כובעים, שחורים ולבנים בסדר אקראי, שניהם צריכים להגיד בו זמנית (נגיד, על פי סימן) מספר טבעי לבחירתם. אם שניהם בחרו מספרים כך שהכובע על ראשם שזה מספרו (הכי תחתון הוא 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 מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |