PDA

צפה בגרסה המלאה : חידה יפה



עשהאל
26-06-2008, 18:00
בס"ד

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

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

yoavzilberman
26-06-2008, 18:08
טוב, אז לדעתי ניתן להציל את כל הדרדרסים למעט הראשון שמדבר(שהוא האחרון בתור).
הראשון (האחרון בתור) יאמר שצבע כובעו הוא הצבע של זה שעומד לפניו ואותו הוא רואה.
הבא בתור שכבר יודע מה צבע כובעו צריך לאמר כך:
אם צבע הבא אחריו זהה לצבעו שיאמר מהו צבע כובעו, אם צבע הבא אחריו שונה מצבעו של הבא אחריו שיאמר מהו לא צבעו (הצבע שהוא מציין שאינו שלו הוא של הבא בתור אחריו). כך כל אחד יעשה בתורו, מכיוון שהגמדים תיאמו לפני כן אז הם יודעים שכאשר הם שומעים צבע מפני קודמיהם זהו הצבע שלהם (אם הוא אמר צבע כובעי לבן אז צבע כובעו של הבא אחריו הוא לבן ואם הוא אמר צבע כובעי אינו שחור אז צבעו של הבא אחריו הוא שחור), כך ניתן יהיה להציל 99 גמדים, אך הראשון כפי שאמרתי מקריב את עצמו.
איני רואה פתרון בו כל 100 הגמדים יינצלו.
מה דעתך?

עשהאל
26-06-2008, 21:50
בס"ד

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

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

yoavzilberman
27-06-2008, 06:01
זה לא רימוז בטון אלא רימוז בניסוח או שאתה אומר צבע כובעי לבן או שאתה אומר צבע כובעי אינו שחור (ביקשת אסטרטגיה וקיבלתי אסטרטגיה).

אריאל
27-06-2008, 10:42
כוונת עשהאל היא ש "כובעי אינו שחור" הינה גם התחכמות, וע"מ למנוע מקרים דומים בהמשך הזכיר דברים כגון "רימוז בטון בגובה " וכול'..
חידה נחמדה אגב :)

עשהאל
28-06-2008, 20:43
בס"ד

יואב, תפסיק להתחכם! אתה רוצה שגרגמל יאכל אותך?

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

chenfire
28-06-2008, 20:53
התחכמות נוספת, לבקש מגרגמל להתחיל מהדרדס האחרון, וכך הוא רואה בדיוק את מספר הכובעים הלבנים והשחורים שיש, ואומר מה לו יש..וכך הלאה:)

עשהאל
29-06-2008, 02:40
בס"ד

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

Paci
29-06-2008, 23:12
מצאתי דרך להציל 50 ועוד כמה דרדרסים עם מזל. P:

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

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

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

וככה זה ממשיך.

זה לא ממש דרך סתם פתרון התחלתי נראה לי, זה משנה אם גרגמל מתחיל הדרדס האחרון או הראשון?

אריאל
29-06-2008, 23:46
"זה שאחריו" "זה שאחריו"..
תיהיה קצת עקבי תנסה להשתמש ב "הדרדס הזוגי" כך וכך , "הדרדס האי זוגי" כך וכך.. :)

Paci
30-06-2008, 00:12
צודק, חשבתי להשתמש בזה אבל לא הייתי בטוח. P:

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

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

מה שנותן לנו 50 ניצולים בטוחים + כמה דרדסים שיש להם מזל.

:)

עשהאל
30-06-2008, 13:38
בס"ד

50 זה יפה, אבל אפשר יותר.

בהצלחה!

chenfire
30-06-2008, 22:21
הראשון שנשאל וגם רואה את 99 הכובעים, ויכריז את הצבע המבטא מספר אי זוגי.
נניח שהצבע שהוא הכריז שחור. כלומר מספר הכובעים השחורים אי זוגי!!!
אז השני סופר את כל הכובעים שלפניו ואם מספר הכובעים השחורים עדיין איזוגי לכן צבע כובעו לבן.
כך הלאה הספירה של הכובעים היא הסכום הכובעים השחורים שהוכרזו ועוד הכובעים שהגמד הנשאל רואה לפניו.

Paci
01-07-2008, 00:35
איך הצלחת לעלות על תשובה כזאת? :(

chenfire
01-07-2008, 01:39
היגיון נטו:)

עשהאל
02-07-2008, 00:27
בס"ד

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

chenfire
02-07-2008, 23:38
מה שבנתיים הצלחתי להבין (ממש לא הוכחה גמורה), היא שהמקרה של n צבעים, הוא בעצם הכללה של מקרה בעל 2 צבעים.
ועוד דבר חשוב, תמיד לראשון שמדבר יש גורם , איזשהו צבע של כובע שלא ייכלל בחישוב של מה הוא יגיד.
מה שבסהכ צריך לעשות הוא לפתח איזשהו קשר בין כמות הכובעים שיש לפי צבעים כתלות ב n. ואז כמובן לפי התכנונים והתחמונים שלהם ניתן יהיה להציל במקרה הטוב 100 דרדסים, ובמקרה הוודאי 99.

עשהאל
03-07-2008, 00:29
בס"ד

זה הכיוון.
יש לך הצעה לקשר שכזה, או שאני אכתוב את זה שלדעתי הוא הכי פשוט?

chenfire
03-07-2008, 00:58
יש n צבעים.
נניח שכמות הצבעים מחולקת בכמויות לא ידועות: qq A B........
לדעתי הנוסחא צריכה להראות כך:
qq (k-1)A+(K-1)B+.....
כאשר k הינו לא קבוע, כלומר בין כל איבר גדל ב 1.
qqq (1-1)A+(2-1)B+....
0A+1B+.....
זה מדוייק?

עשהאל
03-07-2008, 01:11
בס"ד

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

chenfire
03-07-2008, 12:23
אין כאן הרבה מה לומר- הגמד שמדבר ראשון מחשב את מה שנותר מהחלוקה(שארית???), ולפי מה שקבעו יחד קבוצת הגמדים אומר צבע

עשהאל
03-07-2008, 13:49
בס"ד

יפה! זו כבר תשובה!

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