חידת אסטרטגיית נצחון

[עריסטו]

חידת אסטרטגיית נצחון

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

 

[MaD PenGuiN]

../images/Emo62.gif

לרשום מספר אחד, גדול ככל האפשר.

 

[עריסטו]

../images/Emo128.gif אפילו עם שני מספרים מה שכתבת לא עובד

למשל, אם המספרים הם 1 ו -3, לפי מה שכתבת הופכים את ה-3 ל-2. אבל אז היריב הופך את ה-2 ל-0 ומנצח. לעומת זאת, אם אנחנו היינו הופכים בהתחלה את ה-3 ל-0 היינו מנצחים. חוץ מזה מה שכתבת לא מוגדר היטב - אם המספרים הם 1,2, מה זה "לכתוב מספר גדול ככל האפשר"? המספר הגדול ביותר שאנחנו יכולים לכתוב הוא 0, אבל איזה משני המספרים הנתונים להפוך לאפס

 

[ייץ]

נסיון

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

 

[עריסטו]

לא הבנתי את התשובה

 

[ייץ]

אני לא בטוח לגבי התשובה

אבל אני אדגים את התשובה שלי עם מספרים. נניח בחרנו 3 מספרים (N=3) נסתכל על ה XOR של 1,2,3 ונקבל 000 לכן נצטרך לאפס רק את 3 הספרות הראשונות מימין. נניח שנבחרו המספרים 8,12,25 נבצע XOR על 8,12 ונקבל 0100 לכן המספר הקטן!!! ביותר שאם נפעיל XOR איתו יתן 000 (הספרה הרביעית אינה חשובה) הוא 4 לכן על הראשון לבחור את המספר 4. מקווה שכעת זה ברור (אם כי אני לא משוכנע שזאת האסטרטגיה המנצחת).

 

[ייץ]

לאחר חשיבה קלה נוספת

יש לבחור את המספר האחרון כך שהXOR שיתקבל יהיה שווה לXOR של 1,2,3,,,N.

 

[עריסטו]

מה האסטרטגיה שלך אומרת

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

 

[Alkhimey]

נסיון עבור n=2

בדומה לחידה הקלאסית עם ערמות האגוזים, המנצח הוא זה שיכול בתורו לגרום למצב שיש שני מספרים עוקבים והגדול מבינהם הוא אי זוגי. למשל אם המספרים שנכתבו בהתחלה הם 12 ו13 אז המנצח הוא השחקן השני, אם המספרים הם 10 ו4 אז המנצח הוא השחקן הראשון.