חידות חשיבה (184)

לפניכם משחק שמיועד ל-2 אנשים – א' משחק ראשון, ב' משחק שני, וכך הלאה לסירוגין. כל שחקן בתורו חייב לקחת 1 או 2 או 3 גפרורים מתוך ערימה שבה 23 גפרורים. המנצח הוא זה שלוקח את הגפרור האחרון.

האם יש אסטרטגיה שמבטיחה ניצחון לאחד השחקנים, ואם כן מי המנצח (אנו מניחים ששני השחקנים משחקים באופן אופטימלי).

הערה: זוהי גרסה פשוטה של המשחק נים (Nim) שבו יש כמה ערימות של גפרורים, בכל ערימה מספר כלשהו של גפרורים ובכל תור השחקן יכול לקחת מספר גפרורים כלשהו מאחת הערימות.

רמז (אם אתם זקוקים לו):

המנצח יהיה מי שישאיר ליריבו 4 גפרורים.

פתרון:

אנו מניחים, לאורך כל הפתרון, ששני השחקנים משחקים באופן אופטימלי.

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

לשם פשטות, נניח לאורך כל הפתרון שתורו של א' לשחק.

אם בערימה יש 1 או 2 או 3 גפרורים, א' בתורו ייקח את כולם וינצח.

לכן 1, 2 ו-3 הם מצבים מנצחים עבור א'.

אם בערימה יש 4 גפרורים אזי:

אם א' ייקח 1, יישארו 3 וב' ייקח את כולם וינצח.

אם א' ייקח 2, יישארו 2 וב' ייקח את כולם וינצח.

אם א' ייקח 3, יישאר 1 וב' ייקח אותו וינצח.

לכן 4 הוא מצב מפסיד עבור א'.

אם בערימה יש 5 או 6 או 7 גפרורים אזי א' ייקח בתורו 1, או 2, או 3, בהתאמה, וישאיר את ב' עם 4 גפרורים שהם מצב מפסיד עבור ב'.

מסקנה: 5, 6 ו-7 הם מצבים מנצחים עבור א'.

אם בערימה יש 8 גפרורים, זהו מצב מפסיד עבור א'. זאת משום שלא משנה מה הוא יעשה, ב' יוכל להשאיר את א' עם 4 גפרורים שהם מצב מפסיד עבור א'.

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

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

האסטרטגיה שלו היא לקחת תמיד מספר גפרורים כזה שישאיר ליריב מספר גפרורים שהוא כפולה של 4. במהלך הפתיחה שלו הוא מוציא 3 גפרורים ובכך משאיר לב' 20 גפרורים. מכאן ואילך על א' לדאוג לכך שבכל צמד מהלכים של ב' ושל א', יוציאו שניהם ביחד 4 גפרורים. א' יעשה זאת באופן הבא: אם ב' יוציא גפרור אחד אזי א' יוציא 3 גפרורים, אם ב' יוציא 2 גפרורים אזי א' יוציא 2 גפרורים, אם ב' יוציא 3 גפרורים אזי א' יוציא גפרור אחד. התוצאה תהיה שבפעמים הבאות שבהן יהיה תורו של ב' לשחק יהיו לפניו 16 גפרורים, לאחר מכן 12, לאחר מכן 8, ולבסוף 4 גפרורים. זהו מספר מפסיד למי שתורו לשחק ולכן א' יזכה.

למעוניינים בהרחבה:

ומה קורה במקרה הכללי שבו כל שחקן בתורו חייב לקחת מספר גפרורים כלשהו בין 1 ו-N?

החידה עסקה במקרה שבו N שווה 3. עבור N כלשהו, המנצח הוא זה שמשאיר ליריבו אחד מהמצבים המפסידים שהם במקרה זה כפולות של (1N+).

כך, למשל, אם כל שחקן בתורו חייב לקחת מ-1 ועד 6 גפרורים מתוך ערימה שבה 37 גפרורים, אזי הדרך לניצחון היא להשאיר ליריב כפולות של 7. במקרה שלנו א' לוקח 2 גפרורים ומשאיר לב' 35 גפרורים שהם כפולה של 7. מכאן ואילך על א' לדאוג לכך שבכל צמד מהלכים של ב' ושל א', יוציאו שניהם ביחד 7 גפרורים. התוצאה תהיה שבפעמים הבאות שבהן יהיה תורו של ב' לשחק יישארו לו 28 גפרורים ולאחר מכן 21, 14 ולבסוף 7 גפרורים. זה יבטיח את ניצחונו של א'.