חידת אסירים

[JDOE]

חידת אסירים

מודיעים למפקד בית הכלא שמתוך 100 האסירים שלו עליו להוציא להורג 50 הוא מעמיד את כולם בטור ושם על כל אחד כובע בצבע שחור או לבן כל אחד רואה את כל הכובעים שלפניו הוא עובר אחד אחד מהאחרון וכל אחד צריך להגיד לו מה צבע הכובע שלו (עליהם לומר את הצבע באופן אחיד מבחינת הקול ואסור להם לזוז) כל מי שטועה יוצא להורג אם פחות מ 50 יטעו יוצאו להורג כמה מהותיקים יותר כדי ליצוא השלמה אם יותר מ 50 יטעו אלה שלא יוצאו להורג ישארו בצינוק למשך כל חייהם בהנחה שנותנים לאסירים לתכנן אסטרטגיה, ובהנחה שכל האסירים רוצים סיכוי שווה להישאר בחיים בתא שלו ולא בצינוק מה צריכה להיות האסטרטגיה?

 

[gilrel]

אולי

כל אחד אומר את צבא הכובע של מי שיש לפניו

 

[JDOE]

ואיך ינצלו 50?

 

[jaXon]

רעיון

הראשון מכריז על הצבע של הרוב. כל הבאים בתור חוזרים על אותו הצבע. זה מבטיח שיצליחו לפחות 50. ולגבי הסיכויים של כל אחד להצליח - אם מנהל הכלא מחלק כובעים באופן אקראי ובלתי תלוי, זה נותן 50% סיכוי לכל אחד מהם להצליח (כולל לראשון).

 

[jaXon]

טעות שלי - צריך לשחרר |בדיוק| 50, נכון?

 

[JDOE]

נכון

 

[יאיר של תמר]

שאלה...

האם שאר האסירים יודעים כשאסיר מוצא להורג? [חידה נחמדה דרך אגב...]

 

[ןן גיל ןן]

רעיון

האסיר הראשון בוחר באופן אקראי. האסירים במקומות הזוגיים יוצאים מהנחה שהאסיר הראשון בחר את הצבע ע"פ זוגיות מס' הכובעים הלבנים שראה (כמו בפתרון החידה המקורית), ונוהגים ע"פ פתרון החידה המקורית. האסירים במקומות האיזוגיים יוצאים מהנחה שהאסיר הראשון בחר את ההיפך ממה שהאסירים במקומות הזוגיים מניחים, ונוהגים ע"פ פתרון החידה המקורית. בצורה כזו, מס' האסירים שטעו הוא בין 49 ל- 51, ולכולם יש סיכוי שווה (1/2) לשגות.

 

[ןן גיל ןן]

או אפילו יותר טוב

האסירים במקומות האיזוגיים מניחים שמס' הכובעים הלבנים איזוגי. האסירים במקומות הזוגיים מניחים שמס' הכובעים הלבנים זוגי. כל אסיר יודע מה ענו האסירים שמאחוריו (ואת האסטרטגיה שלהם), ומה הכובעים של האסירים שלפניו, ולכן יכול לומר מה צבע הכובע שעל ראשו ע"פ ההנחה שהניח. בשיטה זו בדיוק 50 אסירים יטעו ו- 50 יצדקו, ולכולם סיכוי 1/2 לשגות.

 

[jaXon]

יש כאן הנחה

שכל משתתף במשחק יודע כאשר מגיעים אליו מי מהקודמים הומת ומי לא. בחידה הקלסית הם לא יודעים את זה.

 

[ןן גיל ןן]

לא, לא משתמשים בזה

כל משתתף במשחק יודע רק מה ענו האסירים שמאחוריו, לא אם הם הומתו. (למעשה, אם הוא יודע מי הומת אז האסטרטגיה שלי לא תעבוד במציאות: כל האסירים ידעו אם האסטרטגיה של הזוגיים או של האי-זוגיים עדיפה, ולכן ישנו את האסטרטגיה שלהם- בכל זאת, מדובר בחיים שלהם).

 

[JDOE]

../images/Emo127.gif מצויין

 

[jaXon]

לא מסתדר לי

אולי אני צריך עוד הסברים 1) השיטה לא עובדת עבור כל מקרה. אם כל הכובעים שחורים למשל, כולם שוגים 2) אפשר להוכיח, בתנאיי החידה הזו, (אם אני מבין אותם היטב) שלא ניתן למצוא אסטרטגיה המבטיחה בדיוק X הצלחות. הרי בכל אסטרטגיה (דטרמיניסטית), מספיק שניתן שני קלטים הנבדלים זה מזה בצבע של הכובע הראשון, ובהכרח נקבל תוצאות הנבדלות זו מזו ב1.

 

[ןן גיל ןן]

אתה צודק-משהו חשוד כאן

אכן שינוי כובע האסיר הראשון לא משנה את בחירות האסירים באף מצב. צריך לחשוב על זה (כנראה לחזור לאסטרטגיה הראשונה שהצעתי).

 

[JDOE]

הסברים

כל מי שנמצא במקומות הזוגיים מבחינתו מספר הכובעים הלבנים זוגי כל מי שנמצא במקומות האי זוגיים מבחינתו מספר הכובעים הלבנים אי זוגי ובנוסף מבחינת כל קבוצה כל מי שנמצא בקבוצה השניה טועה לכן החישוב של כל אחד זה מספר הכובעים הלבנים שהוא רואה לפניו, מספר הכובעים הלבנים מהקבוצה שלו ומספר הכובעים השחורים מהקבוצה השניה מאחר והם טועים מבחינתו ולדוגמא שלך אם כל הכובעים שחורים הראשון יגיד שהוא לבן מאחר ויש מספר אי זוגי של לבנים השני יניח שהראשון טועה כלומר שהראשון שחור לכן הוא יגיד שהוא שחור מאחר ו 0 זה מספר זוגי וכך הלאה עד שבדיוק 50 יצדקו

 

[jaXon]

החידה לא פתירה

הטיעון שלי עומד בעינו - אף אסטרטגיה לא יכולה להבטיח תמיד 50 הצלחות בדיוק. מספיק שבדוגמא שהסברת, נחליף את הכובע הראשון לצבע לבן, ונקבל 51 הצלחות.

 

[pazro]

כמובן שיש פיתרון יותר טוב - רמז

יש פיתרון כזה שתוך 100 אסירים רק אחד ימות וגם זה לא בודאות

 

[jaXon]

אל תתבלבל

החידה הזו שונה מהחידה הקלאסית - תקרא אותה מחדש.

 

[pazro]

אני הבנתי את החידה טוב מאוד

 

[jaXon]

לשחרר 99 זה לא רלוונטי כאן