בבקשה תעזרו לי

[טטטטטטטט]

בבקשה תעזרו לי

יש לי בעיה- חידת היגיון: מלך מעמיד 10 אנשים נידונים למוות בטור. כך שכל אחד יכול לראות את זה שלפניו בטור. לכל אחד הוא מחלק כובע שחור או לבן. האסיר עצמו לא יודע איזה צבע כובע ניתן לו הוא רואה רק את צבע הכובע של זה שלפניו בטור אך לא את שלו. המלך עובר אסיר אסיר ושואל אותו מה צבע הכובע שלו. אם הוא טועה הוא יורה בו. האסירים תיכננו תוכנית לפני המסדר שבה הם יצליחו להינצל חוץ מאחד וגם לו יש סיכוי לא רע לחיות כלומר מקסימום אחד ימות וגם זה לא בטוח. במהלך המסדר לאסירים אסור לדבר או לזוז. הם צריכים לומר רק את צבע הכובע- שחור או לבן. והשאלה היא- מהי תוכניתם של האסירים? אם מישהוא יכול לעזור לי אז בבקשה! ומהר!

 

[pallidfool]

אני מניח שהוא מתחיל

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

 

[כרומטי]

הבעיה עם הפתרון הזה

היא שהראשון לא יודע איזה כובע יש עליו. מכאן שהשני יכול לטעות בגלל שהוא לא יודע מה יש על הראשון.

 

[pallidfool]

הראשון לא מסתמך על מה שיש עליו

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

 

[EranDavid]

מה הנוסח המדויק?

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

 

[jaXon]

נכון, ומספר הערות

הפתרון נכון, ויפיפה. יש כמובן להזכיר שהראשון שמדבר מוקרב למען השאר... (במקרה הטוב הוא ניצל). 1) נדמה לי שניתן להוכיח שזה הפתרון היחיד האפשרי(!), יחד עם הגישה ההפוכה כמובן (לסמן את הזוגיות/אי הזוגיות בלבן). הצלחתי להוכיח זאת עבור 3 אנשים, אבל זה מסתבך אחר כך... 2) חידת בונוס : הרחבת השאלה ל K צבעי כובעים, כאשר כל אחד יכול להגיד אחד מK הצבעים. האם לדעתכם עדיין ניתן להציל N-1 אנשים?

 

[bendelac]

פתרון ל K צבעים שונים.

לכל צבע ינתן משקל שונה למשל שחור=1 לבן=2 אדום=3 וכו´. הראשון מקריב עצמו לטובת הכלל(בטוח עבור K>2) ואומר את הסכום שהוא רואה (כולם!). הכל אחד סופר את הסכום של כל אלו להוא רואה(לפניו בטור). כל אחד אומר את דברו לפי הסדר בטור. וכך הם יכולים לדעת את כובעם ע"פ ההפרש שבין המס´ הכללי שהראשון אמר לבין מה שהם ספרו+מה שאמרו קודמיהם.

 

[jaXon]

ממממ

למה אתה מתכוון ב"סכום"? הרי אם יש 20 אנשים לפני מישהו הסכום שלהם הוא לפחות 20, אבל עבור k=5 למשל אסור לו להגיד מספר הגדול מ 5.

 

[bendelac]

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

השאר אומרים רק את הערך שלהם. למשל עבור שחור=1 לבן=2 ואדום=3. אם יש 5 אנשים הראשון אומר 12. השני רואה לפניו 10 לכן הוא יודע שיש לו לבן אז הוא אומר לבן. השלישי שומע את הראשון והשני והוא רואה מלפניו 7 לכן הוא עושה חישוב פשוט הראשון אמר 12 לשני יש לבן לכן לכל הנשארים בטור(כולל אותו) יש 10 הוא רואה "רק" 7 לכן הוא יודע שיש לו אדום. וכו´.

 

[jaXon]

מממממ (2)

מה שאני מנסה להגיד הוא שאם ישנם 3 צבעים אז לכל משתתף מותר להגיד אחד מ-3 ערכים שונים בלבד (0,1,2). לא ניתן להגיד 12 למשל.

 

[bendelac]

למה?

הוא יגיד 12 שזה לא אומר כלום ולכן הוא ימות בטוח!!!! ולמה שלא יוכל להגיע 12?

 

[stac]

טוב יש לי פיתרון,רק חבל על אחרון

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

 

[freedom rider]

באיזה מקום אתה בשורה?