רוטר - חידה - חידת כובעים.

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"חידה - חידת כובעים."

גירסת הדפסה

קבוצות דיון לימודים, מדע ותרבות נושא #10342	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 10342

Deuce
חבר מתאריך 1.9.08
6225 הודעות

15:47 03.07.10

חידה - חידת כובעים.

ערכתי לאחרונה בתאריך 04.07.10 בשעה 03:47 בברכה, Deuce

רק עכשיו חזרתי הבייתה.
לבקשתכם ניסוח החידה:
יש 1000 צבעים שונים ו-11 אנשים חכמים.
מסבירים לאנשים כי עליהם לתכנן אסטרטגיה לגילוי הכובעים כאשר כללי המשחק הם כאלה:
בא אדם מבחוץ ששם כובע בצבע כלשהו לכל אחד מ-11 האנשים. כל אחד רואה את הכובעים על ראשם של חבריו, אך לא רואה את הכובע שנמצא על ראשו. ברגע כלשהו כל האנשים חושפים פתק עליו רשומה הספרה 0 או 1.
לאחר חשיפת הפתקה כל אחד מהאנשים יודע את צבע הכובע שעל ראשו.
כיצד אפשר לתכנן אסטרטגיה מנצחת?
שימו שבסיום התהליך כולם יודעים מה צבע הכובע שעל ראשם, לא רק אחד.
http://rotter.name/cgi-bin/nor/dcboard.cgi?az=show_thread&om=12127&forum=club

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
פרסם גם פה =]	Yariv-H	03.07.10 21:28	1
מצטרף לבקשה	dr70	03.07.10 23:51	2
:	Zippo	04.07.10 00:59	3
מכתב	The Slayer	04.07.10 01:22	4
מכתב	Deuce	04.07.10 03:39	5
מחלקים את המספר הבינארי ל 2..	Yariv-H	04.07.10 07:56	6
הוא לא יכול לרשום 9 כובעים אדומים.	Deuce	04.07.10 13:25	9
החידה שלך נורא מזכירה RAID ע''י ייצוג ביטים :X	xzoooooom	04.07.10 10:07	7
קצת חח :)	Deuce	04.07.10 13:26	10
רעיון שחשבתי עליו, לא בטוח עובד, אבל נראה לי שכן	DOWNTOWN	04.07.10 13:22	8
יפה ! זה הפתרון.	Deuce	04.07.10 13:27	11
XOR המלך	DOWNTOWN	04.07.10 13:28	12
תותח	ronen333	04.07.10 21:05	13
כמובן.	Deuce	05.07.10 04:34	14
גאוני.. תודה :)	ronen333	05.07.10 12:23	15
מישהוא יכול להסביר לי את הפתרון?	Yariv-H	05.07.10 22:14	16
האמת שגם אני לא הבנתי כלום, הבנתי שהפתרון	כמה עוד	05.07.10 22:55	17
זה שנתנו לכול צבע מספר בינארי סבבה	Yariv-H	06.07.10 08:50	18
לא הבנת את תגובה 14?	Deuce	06.07.10 14:07	19
אוקי את זה הבנתי ,	Yariv-H	06.07.10 16:19	20
כן.	Deuce	06.07.10 20:31	21
אוקי עכשיו הבנתי =]	Yariv-H	06.07.10 21:20	22

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

21:28 03.07.10

1. פרסם גם פה =]
בתגובה להודעה מספר 0

אין לי גישה =]

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dr70
חבר מתאריך 17.9.02
21400 הודעות

23:51 03.07.10

2. מצטרף לבקשה
בתגובה להודעה מספר 1

שבוע טוב,

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Zippo
חבר מתאריך 26.5.02
7921 הודעות

00:59 04.07.10

3. :
בתגובה להודעה מספר 1

יש 1000 צבעים שונים ו-11 אנשים חכמים.
מסבירים לאנשים כי עליהם לתכנן אסטרטגיה לגילוי הכובעים כאשר כללי המשחק הם כאלה:
בא אדם מבחוץ ששם כובע בצבע כלשהו לכל אחד מ-11 האנשים. כל אחד רואה את הכובעים על ראשם של חבריו, אך לא רואה את הכובע שנמצא על ראשו. ברגע כלשהו כל האנשים חושפים פתק עליו רשומה הספרה 0 או 1.
לאחר חשיפת הפתקה כל אחד מהאנשים יודע את צבע הכובע שעל ראשו.
כיצד אפשר לתכנן אסטרטגיה מנצחת?
ציטוט מאת: Deuce

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

The Slayer
חבר מתאריך 29.4.03
7959 הודעות, 2 פידבק

01:22 04.07.10

4. מכתב
בתגובה להודעה מספר 3

יש 11 אנשים כלומר 10 אנשים יודעים את הצבע של ה1
מספרו את הצבעים מ1 עד 1000
לכל אחד יש 2 אופציות 0 או 1
10 אנשים זה נותן 1024 אופציות
ה10 אנשים מוצאים את מספר הצבע ברשימתם
הופכים את המספר הזה למספר בינארי בעל 10 ספרות
והבן אדם שצריך לגלות את הצבע פשוט קורא את המספר מהבן אדם הראשון עד האחרון
ככה הם עושים אחד אחד מתאמים בין המספרים לצבעים ואותו בן אדם קורא את המספר

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

03:39 04.07.10

5. מכתב
בתגובה להודעה מספר 4

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

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

07:56 04.07.10

6. מחלקים את המספר הבינארי ל 2..
בתגובה להודעה מספר 5

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

נניח והראשון ראה 9 כובעים אדומים רשם פתק עם 9 כובעים אדומים.
אם לאחר הפתיחה הוא רואה 10פתקים שרשום 9 כובעים ובעים אדומים הוא יודע שגם לו יש כובע אדום =]

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

13:25 04.07.10

9. הוא לא יכול לרשום 9 כובעים אדומים.
בתגובה להודעה מספר 6

הוא יכול להרים ביט אחד - 0 או 1 ...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

xzoooooom
חבר מתאריך 19.3.02
20316 הודעות

10:07 04.07.10

7. החידה שלך נורא מזכירה RAID ע''י ייצוג ביטים :X
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

13:26 04.07.10

10. קצת חח :)
בתגובה להודעה מספר 7

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DOWNTOWN
חבר מתאריך 28.5.02
5388 הודעות

13:22 04.07.10

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

הבן אדם הראשון, רושם על הפתק שלו את ה
XOR של כל הביטים במיקום הכי שמאלי (חוץ משלו כמובן שהוא לא יכול)
הבן אדם השני, כותב על הפתק שלו את
XOR של כל הביטים במיקום הכי שמאלי - 1 (חוץ משלו כמובן שהוא לא יכול)
הבן אדם השלישי, כותב על הפתק שלו את
XOR של כל הביטים במיקום הכי שמאלי - 2 (חוץ משלו כמובן שהוא לא יכול)
וכן הלאה
לבן אדם ה11 נגיע בהמשך

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

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

עדכון:
הבן אדם ה-11 עושה XOR בין כל המיקומים של הביטים של האנשים, כלומר, XOR של הביטים החסרים.
כלומר, XOR בין הביט הכי שמאלי של הראשון לבין הביט השמאלי - 1 של השני, לבין הביט השמאלי - 2 של השלישי, כן הלאה
נראה לי שזה פותר את הבעיה

s22holyshits33

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

13:27 04.07.10

11. יפה ! זה הפתרון.
בתגובה להודעה מספר 8

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DOWNTOWN
חבר מתאריך 28.5.02
5388 הודעות

13:28 04.07.10

12. XOR המלך
בתגובה להודעה מספר 11

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

21:05 04.07.10

13. תותח
בתגובה להודעה מספר 8

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

04:34 05.07.10

14. כמובן.
בתגובה להודעה מספר 13

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

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

12:23 05.07.10

15. גאוני.. תודה :)
בתגובה להודעה מספר 14

אחלה חידה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

22:14 05.07.10

16. מישהוא יכול להסביר לי את הפתרון?
בתגובה להודעה מספר 0

או שלא הבנתי את הפתרון או שלא הבנתי את השאלה...
=]

אם מישהוא יוכל לרשום משהוא מסודר יהיה מגניב =]
תודה..

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
234 הודעות, 11 פידבק

22:55 05.07.10

17. האמת שגם אני לא הבנתי כלום, הבנתי שהפתרון
בתגובה להודעה מספר 16

הוא משהו בינרי, אבל פה ההבנה שלי נגמרת

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

08:50 06.07.10

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

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

אם אפשר הסבר אני ישמח =]

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

14:07 06.07.10

19. לא הבנת את תגובה 14?
בתגובה להודעה מספר 18

תשים לב שצריך 10 ביטים כדי לייצג מספרים מ-0 עד 1000 (יותר נכון עד 1023).

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

16:19 06.07.10

20. אוקי את זה הבנתי ,
בתגובה להודעה מספר 19

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

20:31 06.07.10

21. כן.
בתגובה להודעה מספר 20

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

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק

21:20 06.07.10

22. אוקי עכשיו הבנתי =]
בתגובה להודעה מספר 21

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד