משחק נגד שקרן

[עריסטו]

משחק נגד שקרן

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

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

 

[JDOE]

בטח אפשר פחות

לשאול כל שאלה פעמיים כך שמקסימום נגיע ל 40 שאלות

 

[עריסטו]

../images/Emo3.gif אפשר בהרבה פחות

 

[צחי עציוני]

אני לא יודע איך, אבל

אני יכול לנחש די בוודאות שצריך 25 שאלות

 

[עריסטו]

../images/Emo127.gif../images/Emo128.gif המספר שנתת נכון. האם תוכלו:

א. למצוא דרך לנחש את המספר ב - 25 שאלות? ב. להוכיח ש - 24 שאלות אינן מספיקות?

 

[צחי עציוני]

לא הוכחה, אבל... ../images/Emo9.gif

צריך 20 סיביות כדי לייצג את המספר וצריך להוסיף 5 סיביות כדי למצוא סיבת אחת שגוייה (כדי לתאר מספר בין 0 ל 20 צריך 5 סיביות) למי שמכיר במדעי המחשב קודים לתיקון שגיאות, קוד המינג יבצע את העבודה. צריך רק לתרגם את המימוש של הקוד לשאלות. אני מתאר לעצמי שהחידה שלך רוצה פיתרון יותר יפה מאשר לשאול אותו על איך הוא היה מייצג את המספר ואיך הוא היה מוסיף קוד המינג לייצוג...

 

[בוקי צים]

קשה קשה

 

[עריסטו]

../images/Emo127.gif

 

[Tesseract]

זאת התשובה?

זאת התשובה שהיינו אמורים לעלות עליה? ייצוג בסיביות? קוד המינג? עבדת עלינו

או שאולי יש פתרון "יפה" יותר, שלא נכתב עדיין?

 

[עריסטו]

לא צריך להכיר קוד המינג

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

 

[Tesseract]

צודק..

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

 

[עריסטו]

כמעט

אל תשכח שהוא יכול לשקר בחמש השאלות האחרונות (אם לא שיקר ב - 20 הראשונות).

 

[Tesseract]

אם כך..

לא צריכה להיות שאלה נוספת, כדי ליישב את הסתירה שנוצרת באחת הספרות? או שאת 5 השאלות האחרונות מותר לשאול מהצורה "אם שיקרת באחת מ-20 השאלות הראשונות, האם...?"?

 

[עריסטו]

מותר לשאול כל שאלה שהתשובה

עליה היא כן או לא. 25 שאלות מספיקות.