 |
|
 |
||
|
||||
 |
אני כמעט בטוח שזה כבר נדון פעם באייל, אבל לא מצאתי. מדובר בחידה הזאת (מתורגמת מ 100_prisoners_problem [Wikipedia] ע"י גוגל, עם שלושה תיקונים שלי שמקטינים קצת את ההתלהבות שהבעתי במקום אחר בקשר למצב התרגום הממוכן1): "מנהל בית סוהר מציע ל-100 אסירים הנידונים למוות, הממוספרים מ-1 עד 100, הזדמנות אחרונה. חדר מכיל ארון עם 100 מגירות. ה̶ב̶מ̶א̶י̶ המנהל שם באקראי מספר של אסיר אחד בכל מגירה סגורה. האסירים נכנסים לחדר, בזה אחר זה. כל אסיר רשאי לפתוח ולהסתכל לתוך 50 מגירות בכל סדר. המגירות נסגרות שוב לאחר מכן. אם במהלך החיפוש הזה כל אסיר מוצא את המספר שלו באחת המגירות, כל האסירים מקבלים חנינה. אם ר̶ק̶ לפחות אסיר אחד לא מוצא את המספר שלו, כל האסירים מתים. לפני שהאסיר הראשון נכנס לחדר, האסירים ע̶ש̶ו̶י̶י̶ם̶ יכולים לדון באסטרטגיה - אך אינם יכולים לתקשר ברגע שהאסיר הראשון נכנס להסתכל במגירות. מהי האסטרטגיה הטובה ביותר של האסירים?" (אגב, לא ברור לי בשביל מה לאפשר לאסירים לתכנן את האסטרטגיה, מספיק שכולם יהיו גאונים - אלא אם קיימת אסטרטגיה אטרנטיבית שנותנת אותה תוצאה ועליהם לתאם באיזו אסטרטגיה לבחור). ____________ 1- הבעיה הראשונה שמוצפת כאן ("במאי")לא שייכת לכך שהתרגום הוא לעברית אלא לעניינים קשים של התייחסות להקשר: בד"כ director הוא אכן במאי, אבל כאן הוא לא. גם השלישית - "may" שתורגם ל"עשויים" - נובע מקושי דומה. הבעיה השניה נגרמת בגלל שגם באנגלית ("if just one prisoner does not find...") הניסוח אינו אופטימלי, אבל באנגלית הוא קביל, כלומר אפשר לצפות שדוברי אנגלית יפרשו אותו נכון, ואחרי התרגום ממש לא. |
 |
 |
 |
|
|
|
||
|
||||
|
גם אני חושב שנדון. לפני 3-4 שנים בערך, כי אני זוכר בן כמה בערך היה הבן שלי כשסיפרתי לו על זה. | |
|
|
|
|
|
||
|
||||
|
(בתקווה שזה לא יותר מידי ספוילר, כל פונקציה חד חד ערכית ועל ממספר האסיר למספר המגירה היא ''אסטרטגיה אלטרנטיבית'') | |
|
|
|
|
|
||
|
||||
|
אתה בטוח שמספר האסיר יהיה בלולאה בכל פונקציה כזאת שתבחר? אני מתקשה לראות זאת (אבל בהחלט סביר שהבעיה נעוצה בראיה שלי). מכל מקום, בהעדר תכנון מוקדם כל אסיר סופר-רציונלי יבין שהאסטרטגיה היחידה שיש לה סיכוי להבחר ע"י כל חבריו היא זאת שמתוארת בפתרון, כך שההערה שלי בתוקף). | |
|
|
|
|
|
||
|
||||
|
חידה מצוייינת, וגם לדעתי שמעתי עליה באייל לראשונה (מישהו קישור למאמר על "שבע חידות שבטוח תחשוב ששמעת לא נכון" או משהו דומה). לתזה שלך, אגב, יש שם: Focal_point_(game_theory) [Wikipedia]. |
|
|
|
|
|
|
||
|
||||
|
ברור, זה הרי סתם מורפיזם של הבעיה, הוא מתייחס לזה באיזה שהוא שלב... תחשוב שלאסירים אין מספרים מ-1 עד 100 אלא ת"ז (או שם פרטי ושם משפחה יחודיים, או תאריכי לידה..) והמגירות לא ממסופרות אלא מסודרות בשורות (א-י) ועמודות (1-10)... אחרי הכל, אם מנהל בית הכלא חכם כמו האסירים הוא יסדר את המגירות מראש ככה שפונקציית היחידה תוביל למעגל אחד גדול. |
|
|
|
|
|
|
||
|
||||
|
גם אני חושב שהתשובה לשאלה שלך היא שלילית. | |
|
|
|
|
|
||
|
||||
|
אני זוכר גרסה שונה במעט (במהלך מותר אחד כמדומני) שבה *באמת יש פתרון* שיחלץ את האסירים. נדמה לי שבגרסה הזאת הקריטריון רך יותר (ולכן אני פחות אוהב את החידה כך). פחות כיף לענות על חידה שבה התשובה לשאלה "מצא אסטרטגיה מיטבית" היא "מצאתי אסטרטגיה שתצליח ב-0.765 אחוז מהמקרים והיא הכי נפלאה", ויותר כיף לענות על חידה שבה הצלת את האסירים. |
|
|
|
|
|
|
||
|
||||
|
לא מדובר באיזה שיפור זניח, אלא ב-2 אסטרטגיות שנשמעות (לי) על-פניו כשקולות לחלוטין, ועם זאת באחת יש להם הסתברות אפסית להצליח (2 בחזקת מינוס 100), ובשניה יש להם הסתברות של 3\2 להצליח. זו חידה מוצלחת מאד לטעמי (אבל בסוף זה לא יותר מעניין של טעם). | |
|
|
|
|
|
||
|
||||
|
החידה הזאת מזכירה לי להיות קצת פחות זחוח כשאני מתווכח על שיטות פלא להעלאת הסיכוי בהגרלות הלוטו/טוטו. | |
|
|
|
|
|
||
|
||||
|
נראה שקשה להתקדם מכאן בלי לדון בפרטי הפתרון, כי לפחות עבורי כשאני מיישם את הכיוון שאני זוכר, אני מתקשה להכריז על רגל אחת שהסתברות ההצלחה שלו היא 2/3. | |
|
|
|
|
|
||
|
||||
|
לך לסרטון אליו קישרתי. על רגל אחת קצת קשה לחשב את (sum(1/n|n∈{51,100} | |
|
|
|
|
|
||
|
||||
|
אז לפני שאני הולך, על רגל אחת ומחשבון עשיתי קירוב של ln(100) - ln(51) ויצא לי 0.673, שנשמע לי די באזור, לא? | |
|
|
|
|
|
||
|
||||
|
אז אחרי שהלכתי לסרטון1, אני חוזר וטוען כמו שאמרתי קודם, שבנוסח שאני מכיר (והוא מזכיר אותו אי שם באמצע הסרטון), החידה הרבה יותר אלגנטית. בנוסח הזה2, גם יש פתרון חד וחלק לבעיה - שנראית בתחילה בלתי פתירה לחלוטין בדיוק כמו בנוסח המדובר כאן - וגם צריך הרבה פחות שכנועים למה זה עובד, כולל חישובים סטטיסטיים ארוכים ומפותלים. בנוסח הזה קל לראות שהפתרון עובד, בלי חישוב ולו של הסתברות אחד לרפואה, שלא לומר של טורים הרמוניים ארוכים. אפשר להסביר את זה לתלמיד כיתה ו' בקלות והוא יבין גם את הפתרון וגם למה זה פותר. בנוסף, מה שלא אהבתי בחישובים הסטטיסטיים, זה שיש להם הנחות יסוד על ההתפלגות של התנאים האפריוריים של הבעייה. כולל המילה "אקראי" שתמיד מכניסה קצת סיבוכים הגדרתיים. מנהל כלא שאין ברשותו מחולל מספרים אקראיים והוא אוהב לסדר את המספרים לפי הסדר (וכמובן לא להתחיל בתא הראשון דוקא), ישבור לחלוטין את האסטרטגיה של האסירים ויהפוך את סיכויי ההצלחה שלהם לאפס מאופס. בנוסח החביב עלי, גם הבעייה הזו לא קיימת. הפתרון יציב ותקף בלי קשר לתנאים האפריוריים של סידור המגרות. 1 וטפחתי לעצמי על השכם כל זה שעל רגל אחת הגעתי ל-ln(2) שהוא מראה שזה הגבול של החישוב כש-N שואף לאינסוף. 2 שמותר לאסיר הראשון להחליף שני פתקים. |
|
|
|
|
|
|
||
|
||||
|
הסתברות ההצלחה היא קצת מעל 30%. לא שזה גורע במשהו מהוואו. |
|
|
|
|
|
|
||
|
||||
|
האסירים הצליחו במשימתם, אך במקום לתת להם חנינה מנהל הכלא (שהוא סדיסט לא קטן ובכלל, ממתי מנהלי כלא מוסמכים להעניק חנינות?) הודיע לאסירים שכל אחד מהם מקבל את אחד משלושת השמות האמצעים - אייל, צבי, ודב. למחרת כל אחד מהם יכנס לחדר המכיל את רשימת כל השמות האמצעיים פרט לשלו ויצטרך לנחש את שמו האמצעי. אסיר שכבר ניחש לא יוכל לתקשר עם מי שלא. המנהל לא טרח לאיים בשכר ועונש, אך רמז שכדאי מאוד שכולם ינחשו נכונה כבר בנסיון הראשון - איזה אסטרטגיה תיתן להם סיכוי של שלושים אחוז לפחות להישאר בחיים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), אז כל אחד יכול לחשב את מיקום הכובע השחור הראשון על ראשו. | |
|
|
|
|
|
||
|
||||
|
תודה על ההסבר! | |
|
|
|
|
|
||
|
||||
|
לאוהבי הזאנר - עוד בעיה שנראית (לכאורה) בלתי פתירה. לאוהבי הספויילרים - היא מגיעה עם הפתרון. למדעני המחשב שהם גם חובבי 3כחול1חום, הפעם זה עלול להיות קצת מאכזב. ויזואליציה יפה לקוד האמינג, אך נראה לי שזה המקורי פשוט יותר להבנה. (או שאולי אני מרגיש כך כי למדתי את זה המקורי לפני רבע מאה; מצוייד במוח קצת יותר צעיר ורענן מזה הנוכחי) |
|
|
|
|
|
|
||
|
||||
|
על כל זה אני יכול להגיד רק הללויה!. | |
|
|
|
|
|
||
|
||||
|
מעולה! | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |