לפניכם משחק שמיועד ל-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 גפרורים. זה יבטיח את ניצחונו של א'.
3 תגובות
סדרת החידות חשיבה הכי טובה שאני מכיר
אלה חידות חשיבה שצריך זמן של נחת לשבת להבין לפתור וללמוד. לא כמו חידות חשיבה ברוב המקומות שבהם הפתרון בשלוש שורות, שכז כמובן שיטחי. אבל מצד שני אפשר להתעסק איתם בפסק זמן קצר
אשר, לכבודך כתבתי פתרון בן 3 שורות והנה הוא:
על א' לקחת 3 גפרורים ולהשאיר לב' 20 גפרורים. עתה, אם ב' יקח 1, א' יקח 3; אם ב' יקח 2, א' יקח 2; אם ב' יקח 3, א' יקח 1. כך יישארו בתורות הבאים של ב' 16, אחר כך 12, לאחר מכן 8, ולבסוף 4 גפרורים. עתה, לקיחה כלשהי של ב' תאפשר לא' לקחת את כל הגפרורים הנותרים ולנצח.
אבל אני מעדיף לתת פתרון מורחב שמלווה בהסבר.