קומבינטוריקה, תורת המשחקים

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

  • שני הצריחים

    זוהי משחק חידה לשני שחקנים. לכל שחקן יש צריח אחד. השחקן הראשון מניח את הצריח שלו על כל משבצת בלוח שהוא בוחר, ואז השחקן השני עושה את אותו הדבר. עכשיו הם משחקים בתורות, כאשר המטרה של כל תור היא ללכוד את הצריח של היריב. אבל במשחק הזה אי אפשר לשחק דרך קו תקיפה מבלי להילכד. כלומר, אם בתרשים זה תורו של השחור לשחק, הוא לא יכול להזיז את הצריח שלו למשבצת של הפרש של המלך שלו, או למשבצת של הצריח של המלך שלו, כי הוא ייכנס ל"קו האש" כשהוא עובר על פני המשבצת של הרץ של המלך שלו. מאותה סיבה הוא לא יכול לעבור לצריח של המלכה שלו במשבצת השביעית או השמינית. עכשיו, המשחק לעולם לא יכול להסתיים בתיקו. במוקדם או במאוחר אחד הצריחים חייב ליפול, אלא אם כן, כמובן, שני השחקנים מבצעים את האבסורד של לא לנסות לנצח. הטריק לנצח הוא פשוט להפליא כשאתה יודע אותו. האם אתה יכול לפתור את החידה? מקורות:

  • חתול בפינה

     

    גרסה זו של החידה האחרונה משוחקת גם היא על ידי שני אנשים. אחד מניח כלי משחק על מספר `6`, והשני מניח כלי משחק על מספר `55`, והם משחקים בתורות על ידי הזזת הכלי לכל מספר אחר בקו. אם היריב שלך עובר בכל עת לאחד הקווים שאתה תופס, או אפילו חוצה אחד מהקווים שלך, אתה מיד לוכד אותו ומנצח. ניקח משחק המחשה.

    א' זז מ-`55` ל-`52`; ב' זז מ-`6` ל-`13`; א' מתקדם ל-`23`; ב' הולך ל-`15`; א' נסוג ל-`26`; ב' נסוג ל-`13`; א' מתקדם ל-`21`; ב' נסוג ל-`2`; א' מתקדם ל-`7`; ב' הולך ל-`3`; א' זז ל-`6`; ב' חייב כעת ללכת ל-`4`; א' מתבסס ב-`11`, ויש ללכוד את ב' במהלך הבא מכיוון שהוא נאלץ לחצות קו שעליו עומד א'. שחקו זאת שוב ותבינו את המשחק ישירות. כעת, החלק החידתי של המשחק הוא זה: איזה שחקן צריך לנצח, וכמה מהלכים נחוצים?

    מקורות:

  • משחק חידה מלחמתי

    הנה עוד משחק חידה. שחקן אחד, המייצג את הגנרל הבריטי, מניח כלי בנקודה B, והשחקן השני, המייצג את האויב, מניח את הכלי שלו בנקודה E. הבריטי עושה את ההתקדמות הראשונה לאורך אחת הדרכים לעיר הבאה, ואז האויב עובר לאחת הערים הקרובות אליו, וכן הלאה בתורות, עד שהגנרל הבריטי מגיע לאותה עיר כמו האויב ולוכד אותו. למרות שכל אחד חייב תמיד לנוע לאורך דרך לעיר הבאה בלבד, והשחקן השני רשאי לעשות כמיטב יכולתו כדי להימנע מלכידה, הגנרל הבריטי (כפי שאנו אמורים להניח, מהאנלוגיה של החיים האמיתיים) חייב לנצח ללא טעות. אבל איך? זאת השאלה. מקורות:

  • תעלומת גפרורים

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

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

    "הנה שלושים גפרורים," אמר. "אני מחלק אותם לשלוש ערימות לא שוות. תן לי לראות. יש לנו `14, 11` ו-`5`, במקרה. עכשיו, שני השחקנים מושכים לסירוגין כל מספר מכל ערימה אחת, ומי שמושך את הגפרור האחרון מפסיד במשחק. זה הכל! אני אשחק איתך, וילסון. הרכבתי את הערימות, אז יש לך את התור הראשון."

    "מכיוון שאני יכול למשוך כל מספר," אמר מר וילסון, "נניח שאני מציג את המתינות הרגילה שלי ואקח את כל ערימת ה-`14`."

    "זה הכי גרוע שיכולת לעשות, כי זה מפסיד מיד. אני לוקח `6` מה-`11`, ומשאיר שתי ערימות שוות של `5`, ולהשאיר שתי ערימות שוות זה ניצחון בטוח (פרט לחריג היחיד של `1, 1`), כי מה שלא תעשה בערימה אחת אני יכול לחזור עליו בשנייה. אם אתה משאיר `4` בערימה אחת, אני משאיר `4` בשנייה. אם אתה משאיר רק `1` בערימה אחת, אז אני לוקח את כל הערימה השנייה. אם אתה לוקח את כל הערימה האחת, אני לוקח את הכל מלבד אחד בשנייה. לא, אסור לך אף פעם להשאיר שתי ערימות, אלא אם כן הן ערימות שוות ויותר מ-`1, 1`. בוא נתחיל שוב."

    "בסדר גמור," אמר מר וילסון. "אני אקח `6` מה-`14`, ואשאיר לך `8, 11, 5`."

    מר סטאבס אז השאיר `8, 11, 3`; מר וילסון, `8, 5, 3`; מר סטאבס, `6, 5, 3`; מר וילסון, `4, 5, 3`; מר סטאבס, `4, 5, 1`; מר וילסון, `4, 3, 1`; מר סטאבס, `2, 3, 1`; מר וילסון, `2, 1, 1`; שאותו מר סטאבס צמצם ל-`1, 1, 1`.

    "עכשיו ברור לחלוטין שאני חייב לנצח," אמר מר סטאבס, כי אתה חייב לקחת `1`, ואז אני לוקח `1`, ומשאיר לך את הגפרור האחרון. אף פעם לא היה לך סיכוי. יש בדיוק שלושה עשר דרכים שונות שבהן ניתן לקבץ את הגפרורים בהתחלה לניצחון בטוח. למעשה, הקבוצות שנבחרו, `14, 11, 5`, הן ניצחון בטוח, כי על מה שהיריב שלך ישחק יש קבוצה מנצחת אחרת שאתה יכול להבטיח, וכך הלאה עד הגפרור האחרון."

    מקורות:

  • חידת הסיגר

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

    שני אנשים יושבים ליד שולחן מרובע. אחד מניח סיגר רגיל (שטוח בקצה אחד, מחודד בקצה השני) על השולחן, ואז השני עושה את אותו הדבר, וכן הלאה לסירוגין, בתנאי שאף סיגר לא יגע באחר. איזה שחקן יצליח להניח את הסיגר האחרון, בהנחה שכל אחד מהם ישחק בצורה הטובה ביותר האפשרית? גודל פני השולחן וגודל הסיגר אינם נתונים, אך כדי לשלול את התשובה המגוחכת שהשולחן עשוי להיות כה קטן עד שהוא יכול להכיל רק סיגר אחד, נאמר שהשולחן לא יהיה קטן מ- `2` רגל מרובע והסיגר לא יותר מ- `4`½ אינץ' אורך. עם ההגבלות האלה אתה יכול לקחת כל מימד שתרצה. כמובן שאנו מניחים שכל הסיגרים זהים לחלוטין בכל מובן. האם השחקן הראשון או השחקן השני ינצח?

    מקורות: