אחת די קשה

[gmorphus]

אתם לא רציניים... ../images/Emo13.gif ענבל מה איתך?

ואחת יותר קשה: אינסוף אנשים ואינסוף צבעים?

 

[slallum]

היי, לפחות אני ניסיתי ../images/Emo3.gif../images/Emo8.gif

 

[inbal76]

../images/Emo3.gif ננסה

אם הפתרון הוא "הרחבה" של הפתרון המקורי, אז אני משערת שזה צריך להיות משהו עם מודולו. נניח 5 צבעים. קובעים להם סדר מסויים, נניח: אדום = 0 ירוק = 1 צהוב = 2 כחול = 3 לבן = 4 המנחש ראשון (זה שרואה את כולם חוץ מעצמו) סופר נניח כמה אדומים הוא רואה, מחלק את זה ב-5, ואומר את הצבע שמתאים לשארית. הבא אחריו יודע לפי זה כמה אדומים יש כולל את עצמו, וכיוון שרואה את כל השאר יכול להסיק אם יש לו אדום או לא. ולפי הכרזתו גם הבא יודע אם יש לו אדום וכן הלאה. הראשון שמסיק שאין לו אדום - לא יכול לדעת איזה צבע יש לו, אז הוא עושה את אותה פעולה שעשה הראשון עבור ירוק. כל הבאים אחריו כבר ידעו אם יש להם אדום או ירוק. הראשון שאין לו לא אדום ולא ירוק - ממשיך לצבע הבא. וכך הלאה. מספר האנשים שינחשו נכונה על בטוח הוא מספרם הכולל פחות (N-1). N-1 אנשים עלולים לטעות. לראשון מביניהם יש צ'אנס של 1 חלקי N, לשני 1 חלקי (N פחות 1) וכך הלאה... לא יודעת אם זה הכי טוב שאפשר, אבל מה שעולה לי כרגע.

 

[gmorphus]

התחלת נכון אבל

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

 

[lupoN]

כשמדובר על שלושה צבעים../images/Emo163.gif

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

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

בוקר טוב

 

[lupoN]

מצאתי את הקובץ עם הפתרון המתמטי:

טוב שעושים גיבוי כמה שנים לאחור

מצורף קובץ WORD ובו החידה בצרוף פתרון מתמטי ובאנגלית

(זה מה יש) לשלושה צבעים.

 

[lupoN]

אגב,

(שוב כתבתי לעצמי...)

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

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

 

[gmorphus]

תשובה

לא קראתי בעיון את ההסבר בקובץ המצורף, אבל בכל מקרה נראה לי שזה יעבוד רק עבור 3 צבעים. הפתרון שאני אראה עכשיו יעבוד עבור כל מספר של צבעים (והוא הוזכר בהודעה מעלי). נניח שיש n צבעים. ממספרים את הצבעים מ 0 עד n-1. האסיר הראשון סוכם את הצבעים שלפניו, עושה מודולו n (כך שהצבע שהוא יאמר יהיה חוקי) ואומר את הצבע שמתאים למספר. האסיר הבא בתור סוכם את כל הכובעים שלפניו ובודק את מספר צריך להוסיף כדי שאם נעשה מודולו n יתקבל הצבע שאמר האסיר הראשון. האסיר הבא בשורה סוכם את הצבעים שלפניו ומקבל מספר X. הוא צריך לחשב איזה מספר הוא צריך להוסיף שיתקבל המודולו המתאים. דוגמא: השורה: 0 2 2 1 1 2 1 0 0 הראשון בשורה (משמאל) סוכם ומקבל 9. מודולו 3 זה 0. הוא מכריז 0 (או את הצבע המתאים). במקרה הוא אפילו ישאר בחיים. הבא בתור סוכם ומקבל גם 9. מכיוון שעל ראשו יכול להיות 0,1,2 הוא מסיק שבטוח על ראשו יש 0. וזה מה שהוא מכריז. הבא בתור סוכם ומקבל 8. השארית באסיר שלפניו הייתה 0 זאת אומרת שעל ראשו חייב להיות מספר שיגרום לשארית להיות אפס - והוא 1. הבא בתור סוכם ומקבל 6. הוא יודע שבהתחלה השארית הייתה 0, אבל אסיר קודם היה על ראשו 1, זאת אומרת שהשארית עכשיו צריכה להיות 2 אז הוא יודע שעל ראשו יש 2. וכך הלאה. עבור אינסוף צבעים: כמובן שהשאלה הזאת היא כבר תיאורטית, אבל נניח שיש לנו אינסוף צבעים של כובעים. גם פה כל כובע מקבל מספר, אבל מספר הצבעים לא חסום. איך אפשר לפתור את זה עכשיו? הפתרון למטה פשוט מאוד, הראשון סוכם את כל הכובעים שלפניו ומכריז הסכום. הבאים אחריו פשוט מחסרים את הסכום שהם קיבלו ודואגים לזכור איזה צבעים כבר אמרו לפניהם.

 

[inbal76]

יפה!

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

 

[gmorphus]

אינסוף צבעים לא אינסוף אנשים

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