חידה

[טלמון סילבר]

חידה

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

 

[גדי20152015]

ניסיון

יכול להיות ש 7 ?
כי 100 בבינארית זה 1100100 כלומר 7 ספרות, אז מספיק 7 ביטים של מידע, לא משנה באיזה סדר, כדי לזהות את המספר. 6 ביטים לא יספיקו, בגלל שסדר שאילת השאלות אקראי אז צריך להסתכל על ה worst case.

 

[טלמון סילבר]

נגיד שהמנחה ענה "כן" על אחת השאלות,

איך תדע לאיזה ביט זה מתייחס?
למשל 7=111 נותן שלושה "כן", אבל גם 14=1110 נותן שלושה כן, וגם 28=11100, וגם 21=10101.

 

[גדי20152015]

השאלות צריכות להיות כאלו:

פתק 1: " יהי X מספר הקופסא עם הפרס בבינארית. האם הספרה הראשונה של X היא 1 ? "
פתק 2: " יהי X מספר הקופסא עם הפרס בבינארית. האם הספרה השנייה של X היא 1 ? "
וכן הלאה עד הספרה השביעית...
ואז לא משנה הסדר.

 

[טלמון סילבר]

בוא ניקח את שני הפתקים הראשונים שכתבת.

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

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

 

[הפרבולה]

אם ככה לדעתי התשובה היא

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

אז בהנחה שהקופסאות ממוספרות מ 1 עד 100 השאלות יהיו למשל:
האם מספר הקופסה עם הפרס גדול מ 1
האם מספר הקופסה עם הפרס גדול מ 2
.....
האם מספר הקופסה עם הפרס גדול מ 99

מספר הקופסא הוא מספר תשובות הכן +1

 

[עריסטו]

לא נראה לי נכון שהמידע היחיד הוא כן או לא

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

 

[טלמון סילבר]

הרשה לי בינתיים לא להגיב

 

[טלמון סילבר]

הבהרה חשובה לתנאי החידה

כאשר המנחה שולף פתקה, הוא קורא את השאלה בעיניים בלבד, לא בקול רם!
אנו שומעים רק את התשובה שלו - כן או לא - מבלי לדעת על איזה פתק הוא ענה!

 

[עריסטו]

נסיון

לוקחים שבעה פתקים ועל כל אחד מהם כותבים את השאלה הבאה:

תהי S קבוצת הקופסאות שלפי התשובות שמסרת עד עתה ייתכן שהפרס נמצא באחת מהן. יהי A המספר הקטן ביותר מבין מספרי הקופסאות ב - S, ויהי B המספר הגדול ביותר מבין מספרי הקופסאות ב - S. האם מספר הקופסה בה נמצא הפרס קרוב יותר ל - A מאשר ל - B?

 

[טלמון סילבר]

נראה לי מצוין

אני מכיר פתרון אחר.

 

[עעעערררר]

אפשר לנסח כך גם את הפתרון של גדי

שבע פתקאות, המכילות את השאלה (הזהה) הבאה:
יהי n מספר הפתקאות שכבר ענית עליהן. האם הספרה (הבינארית) ה-n מימין של מספר הקופסה עם הפרס היא 1?

 

[טלמון סילבר]

אכן

לפתרון הזה התכוונתי (עם תיקון זעיר).

 

[הפרבולה]

נסיון

מכינים 7 פתקים ובכל אחד מהם רושמים את השאלה הבאה:

יהי n מספר הפתקים שעניתה עליהם עד עכשיו , האם הביט ה n של מספר הקופסא עם הפרס ביצוג בינרי הוא 1 ?

 

[טלמון סילבר]

איה סנכרון מדהים!

נדברתם מראש?

הביט ה- n+1.

 

[טלמון סילבר]

טוב,

אם מקובל לקרוא לביט הימני - "ביט מספר 0", אז אתם צודקים "לגמרי"

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

 

[עריסטו]

בערך

הוא שקול אם מספר הקופסאות הוא חזקה של 2.

 

[טלמון סילבר]

התכוונתי שאותו הפרינציפ

 

[הפרבולה]

לא נדברנו מראש , אולי טלפתיה .....