100 כובעים שחור לבן

[הפרבולה1]

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

 

[Harrington]

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

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

 

[הפרבולה1]

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

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

 

[ai27]

האסיר הראשון יגיד לסוהר שהכובע שלו שחור אם מספר האסירים בעלי הכובע השחורים שהוא ראה אי זוגי
ולבן אם מספר הכובעים השחורים זוגי

וככה כל השאר יספרו את מספר הכובעים השחורים
וידעו מה הצבע של הכובע שלהם.
במקרה הגרוע, טעות אחת

 

[הפרבולה1]

האסיר הראשון יגיד לסוהר שהכובע שלו שחור אם מספר האסירים בעלי הכובע השחורים שהוא ראה אי זוגי
ולבן אם מספר הכובעים השחורים זוגי

וככה כל השאר יספרו את מספר הכובעים השחורים
וידעו מה הצבע של הכובע שלהם.
במקרה הגרוע, טעות אחת

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

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

 

[עריסטו]

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

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

50 אסירים מניחים שהמספר הכולל של כובעים שחורים הוא זוגי, ו-50 אסירים מניחים שהמספר הכולל של כובעים שחורים הוא אי זוגי.

 

[הפרבולה1]

50 אסירים מניחים שהמספר הכולל של כובעים שחורים הוא זוגי, ו-50 אסירים מניחים שהמספר הכולל של כובעים שחורים הוא אי זוגי.

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

 

[עריסטו]

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

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

 

[הפרבולה1]

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

אני לא בטוח , נראה לי שצריך להוכיח שבכל שיטה שנבחר התוחלת של הניחושים הנכונים תהיה 50 ....

 

[עריסטו]

אני לא בטוח , נראה לי שצריך להוכיח שבכל שיטה שנבחר התוחלת של הניחושים הנכונים תהיה 50 ....

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

 

[ai27]

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

אבל מה אם יש להם מזל רע
וכל אלו שיש להם השלמה לאי זוגי הם לבנים
וכל אלו שההשלמה שלהם לזוגי הם שחורים
אז לא יצא 50
אלא 0

 

[הפרבולה1]

אבל מה אם יש להם מזל רע
וכל אלו שיש להם השלמה לאי זוגי הם לבנים
וכל אלו שההשלמה שלהם לזוגי הם שחורים
אז לא יצא 50
אלא 0

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


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