נושא: חידת הכובעים.

נשלח בתאריך: 13 May 2005 בשעה 18:44 | IP רשוּם

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

את כולם שמו באותו חדר, ואמרו להם כך: "בעוד כ24 שעות, אנחנו  נציב את כולכם בתור כך שהפנים של כולם לאותו כיוון, על כל אחד ואחד מכם נשים כובע, הכובע יכול להיות הוא כובע שחור, או כובע לבן, נתחיל מהאחרון שבתור (זה שרואה את הכובעים של כולם- חוץ מאת שלו), ונשאל אותו לצבע כובעו, אם הוא יענה נכונה- הוא ישוחרר, אם לא- הוא ימות, אחריו נשאר את הבא אחריו, וכך עד שנגיע לראשון, מי שיענה נכון- ישוחרר, ומי שלא- ימות."

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

לגנבים יש 24 שעות לתכנן תוכנית שתציל כמה שיותר מהם.

השאלה שלי היא:

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

בגלל שאני לא אכנס לפורום במהלך השבת, בשביל ההבנה אני אתן תשובה לדוגמא:

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

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

שני דברים:

א- אני מבקש ממי שמכיר את החידה לא לענות או לתת רמזים.

ב- התשובה היא תשובה הגיונית ומתמטית לחלוטין, אל תנסו להתפלסף :).

נשלח בתאריך: 14 May 2005 בשעה 20:35 | IP רשוּם

ניר, תחשוב רגע, אם למשל יש לנו תור של: BWBWBWBWBWBW הפתרון שלך נותן ל50% למות ול50% שנשארו ל50% לחיות ו50% למות.

אני אקל עליכם, נניח שיש רק 20 גנבים.

נ.ב.

מותר להשתמש בדיבאגר ;)

נשלח בתאריך: 15 May 2005 בשעה 02:31 | IP רשוּם

זאת אומרת שבמצב ממוצע יש לך כאן רק 75 אחוזי הצלחה, ובמצב ממש רע (BWBWBWBWBWBWBW למשל) יש לך כאן רק 50 אחוזי הצלחה, תשובה יפה, אבל יש יותר מוצלחת.

בהצלחה!

נשלח בתאריך: 15 May 2005 בשעה 12:24 | IP רשוּם

ניתן להציל  את כולם פרט לראשון .

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

אם הוא אי-זוגי אז הוא יצעק שחור אחרת לבן.

הרעיון הוא בדיקת זוגיות

נשלח בתאריך: 15 May 2005 בשעה 16:18 | IP רשוּם

זהו אכן הפתרון, אבל לפי נימת הכותב אני מניח שהוא הכיר את התשובה ולכן.. זה חבל..

נשלח בתאריך: 15 May 2005 בשעה 17:25 | IP רשוּם

לא הבנתי ממש את הפתרון =\

[ידעתי שיש איזו שהיא דרך להציל את כולם חוץ מהראשון אבל לא ידעתי איזו =\]

נשלח בתאריך: 19 May 2005 בשעה 16:55 | IP רשוּם

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

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

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

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

:)

נשלח בתאריך: 20 May 2005 בשעה 13:42 | IP רשוּם

SBD, זה לא חצי.. זה זוגי או לא זוגי, הראשון ששואלים- הוא האחרון בתור, ולכן הוא יכול לראת את הכובעים של כולם :)

נשלח בתאריך: 20 May 2005 בשעה 14:13 | IP רשוּם

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

נשלח בתאריך: 08 March 2007 בשעה 16:21 | IP רשוּם

יש לי תשובה לחידת הכובעים:

נניח שה"שחור"-ז"א מספרים שהכובעים השחורים הם מספר זוגי

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

עכשיו נגיד נחצה לחצי את המאה חצי אחד הוא 06 שחורים וחצי שני 04 לבנים

האחרון אומר שצבע הכובע שלו הוא לבן בכך הוא מרמז לקבוצתו רמז

והוא מסתכל ורואה 93 כובעים לבנים ו06 כובעים שחורים אז ז"א שהוא המספר ה04 של הלבנים

והכל קשור בזוגי ואי זוגי!!!!!

עכשיו ניקח 6 ילדים:

1.     לבן     =ראשון

2.    שחור     

3.     שחור     

4.     שחור    

5.  לבן  

6.לבן =אחרון

 חוצים לחצי של שלוש בכל קבוצה

עכשיוהאחרון רואה שיש מלפניו שלוש שחורים אז ז"א שיש לו לבן

והחמישי רואה שיש מלפניו שלוש שחורים אז ז"א שהוא רואה מה שהקודם רואה והוא גם לבן

והרביעי רואה שיש שתי שחורים ו2 זה זוגי אז ז"א שהוא שחור

וכן הלאה.......

שמחתי לעזור בתודה חסוי