במשחק נים ישנן ערמות גפרורים אחדות. כל שחקן בתורו יכול לקחת כמה גפרורים שהוא רוצה אבל רק מערמה אחת. מי שלוקח את הגפרור האחרון מנצח. עבור מצב התחלתי שבו יש שלוש ערמות שבהן 5 ,6 ,9 גפרורים, האם כדאי להיות השחקן הפותח, או לתת ליריב לשחק קודם? מה אסטרטגיית הניצחון במשחק?
למי שמכיר את החידה, או פתר אותה והתלהב, ישנה גם חידת בונוס.
| פתרון
|
| אסטרטגיית הניצחון בנים מבוססת על כך שכותבים כל אחד ממספרי הערמות בבסיס בינארי, ואז מבצעים XOR למספרים שיצאו (כל ספרה בנפרד) אם יצא 0, זהו מצב מפסיד. אם יצא משהו אחר, יש לקחת גפרורים כך שישארו מספרים שיוצרים 0, ואז השחקן השני יפסיד (כי בכל תור אפשר להחזיר ל-0, עד שלוקחים את הגפרור האחרון)
בדוגמה:
XOR של כל המספרים יוצר 1010. כדי לאפס, יש לשנות לאחד המספרים את הספרה הרביעית והשנייה. זה חייב להיות ל-9 (אי אפשר להוסיף גפרורים) ולכן יש להפוך אותו ל-11, כלומר 3 גפרורים, ואז השחקן השני יקלע למצב מפסיד.
|
|