בתשובה לירדן ניר-בוכבינדר, 18/11/22 13:25
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754116
תודה!

___

שכחתי לכתוב באותיות קטנות שההשתתפות אסורה על הקשה המקשה ובני משפחתו :) כל הכבוד לו על הפיצוח!
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754119
נזכרתי בחידה דומה, אבל הפעם בלי אסירים: לשני שחקנים יש על הראש ערימה של אינסוף כובעים, שחורים ולבנים בסדר אקראי, שניהם צריכים להגיד בו זמנית (נגיד, על פי סימן) מספר טבעי לבחירתם. אם שניהם בחרו מספרים כך שהכובע על ראשם שזה מספרו (הכי תחתון הוא 1, זה שעליו הוא 2 וכך הלאה) הוא לבן הם נצחו, אחרת הם הפסידו. האם יש אסטרטגיה שנותנת להם סיכוי יותר טוב מ-‏0.25 לנצח?
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754125
שניהם יכולים לראות את הערימה שעל ראש האחר?
אם כן, כנראה שיש לי משהו כך שההסתברות מתכנסת לשליש. אני בכיוון?
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754126
כן.
כן!
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754128
נראה לי שהבנתי. האם הסדרה אכן מתכנסת לשליש או סתם גבוהה מרבע?
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754129
התשובה, אם הבנתי נכון, היא:
השחקנים מהמרים על כך שהכובעים התחתונים על ראשם זהים. אם אינם, הם הפסידו (50%), אם הם כן, וגם לבנים (25%), הם נצחו.
במידה שהכובעים זהים אך שחורים (25%), הם עוברים לכובע הבא - שם הם חוזרים על המשחק.

לכן האלגוריתם הוא בחירת מספר הכובע הלבן התחתון ביותר של השחקן השני. וההסתברות לניצחון היא סכום הסדרה רבע בחזקת N (מאחד לאינסוף).
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754130
ואמנם שליש, כמו שפסק המקשה:
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754132
זה אכן הפתרון.
(אתה באמת צריך את וולפרם בשביל סכום של סדרה הנדסית?)
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754133
אח שלי, אני תשע שנות לימוד אני. צברתי כמה חורים בהשכלה.
ובכל מקרה, תודה על שאלה יפה.
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754464
לא חייבים לסכום סדרה הנדסית, הם מצליחים אם ורק אם שני כובעים שחורים מופיעים לפני שמופיעים שחור-לבן או לבן-שחור וההסתברות לכך היא שליש.
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754465
דרך אגב, ההסתברות המקסימלית האפשרית בשאלה הזו לא ידועה. יש אסטרטגיה שנותנת 0.35 ויש חסם מלעיל של 0.375.
בעיה ממשפחת הבעיות שנראות בלתי פתירות 756741
מה האסטרטגיה שנותנת 0.35 ?
בעיה ממשפחת הבעיות שנראות בלתי פתירות 756743
לרגל הופעתך הנדירה במחוזותינו, קבל שי צנוע שיגזול שלוש שניות מזמנך.

בין הפותרים יוגרל כרטיס השתתפות בהפגנה בירושליים מחר.
בעיה ממשפחת הבעיות שנראות בלתי פתירות 756746
יכול להיות, אבל הן לא ממש נראות לי נשות היי-טק או מדעניות טילים.
בעיה ממשפחת הבעיות שנראות בלתי פתירות 756747
אל תהיה גזען!
בעיה ממשפחת הבעיות שנראות בלתי פתירות 756846
יש כמה אסטרטגיות, קצת שרירותיות. אחת מהן מתוארת במאמר הזה (משפט 2):
וגם נראה שיש חסם העליון טוב משזכרתי: 0.3616
בעיה ממשפחת הבעיות שנראות בלתי פתירות 756989
תודה
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754506
יפה!
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754466
החידה הזו קשורה לבעיה פתוחה: יש n שחקנים במקום 2 וכל השאר זהה. האם יש אסטרטגיה שמבטיחה הסתברות הצלחה חיובית קבועה בלי תלות ב-n או שההסתברות דועכת לאפס כאשר n שואף לאינסוף?
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754505
האם אתה מאתגר אותנו למצוא אסטרטגיה עם הסתברות הצלחה חיובית קבועה, או שאתה מספר לנו שהוכחת/הפרכת קיומה זאת בעיה פתוחה?

____

כי בנתיים אני תקוע בתוחלת של חצי בחזקת לוג n, שדועכת לה בשקדנות עם השאיפה לאינסוף ...
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754507
אני מספר שזו בעיה פתוחה להכריע האם יש או אין אסטרטגיה שמבטיחה הסתברות הצלחה חיובית קבועה, ללא תלות ב-n. יש אסטרטגיה ידועה שנותנת הסתברות הצלחה אחד חלקי לוג n (שזה הרבה יותר טוב מחצי בחזקת לוג n). ידוע גם שאם דורשים מהם להצביע על הכובע השחור הראשון, אז אי אפשר להשיג יותר מאחד חלקי לוג.
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754508
מה האסטרטגיה הנ״ל?
(אם היא פשוטה מספיק להסבר להדיוטות)
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754509
היא פשוטה ודומה למדי לפתרון החידה המקורית. נסתכל על המיקום של הכובע השחור הראשון על ראש כל משתתף. בהסתברות גבוהה (הכנס חישוב מתאים) כל המיקומים הללו קטנים מלוג n. המשתתפים מנחשים מה סכום המיקומים מודולו לוג n. אם הם צודקים (מה שקורה בהסתברות אחד חלקי לוג n), אז כל אחד יכול לחשב את מיקום הכובע השחור הראשון על ראשו.
בעיה ממשפחת הבעיות שנראות בלתי פתירות 754510
תודה על ההסבר!

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים