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

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

  • ארבע הצפרדעים

    באיור יש לנו שמונה פטריות, עם צפרדעים לבנות על `1` ו-`3` וצפרדעים שחורות על `6` ו-`8`. החידה היא להזיז צפרדע אחת בכל פעם, בכל סדר, לאורך אחד הקווים הישרים מפטריה לפטריה, עד שהן החליפו מקומות, כשהצפרדעים הלבנות נשארות על `6` ו-`8` והשחורות על `1` ו-`3`. אם תשתמשו בארבעה אסימונים על דיאגרמה פשוטה, תגלו שזה די קל, אבל זה קצת יותר מבלבל לעשות זאת בשבעה מהלכים בלבד, כאשר כל מספר של מהלכים רצופים על ידי צפרדע אחת נחשב למהלך אחד. כמובן, יותר מצפרדע אחת לא יכולה להיות על פטריה בו זמנית. מקורות:

  • חידת המכלאה

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

  • מבוי סתום

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

  • המלך הנשכח

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

  • מסע הצלב

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

  • חיילים בלתי ניתנים להזזה

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

  • פאזל סיני עתיק

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

  • סוליטר משבצות

    הנה משחק סוליטר קטן שהוא די קל, אבל לא כל כך קל שהוא לא מעניין. אתה יכול לסמן את הריבועים על גיליון קרטון או נייר, או שאתה יכול להשתמש בחלק מלוח השחמט שלך. הצגתי אסימונים ממוספרים באיור כדי להפוך את הפתרון לקל ומובן לכולם, אבל חיילי שחמט או דמקה יתאימו באותה מידה בפועל. הפאזל הוא להסיר את כל האסימונים מלבד אחד, והאחד הזה שנשאר חייב להיות מס' `1`. אתה מסיר אסימון על ידי קפיצה מעל אסימון אחר למשבצת הבאה מעבר לו, אם המשבצת הזו פנויה, אבל אתה לא יכול לבצע קפיצה בכיוון אלכסוני. המהלכים הבאים יבהירו את המשחק: `1-9`, `2-10`, `1-2` וכן הלאה. כאן `1` קופץ מעל `9`, ואתה מסיר את `9` מהלוח; אז `2` קופץ מעל `10`, ואתה מסיר את `10`; אז `1` קופץ מעל `2`, ואתה מסיר את `2`. כל מהלך הוא אפוא לכידה, עד ללכידה האחרונה שנעשית על ידי מס' `1`. מקורות:

  • סוליטר לוח שחמט

    הנה הרחבה של משחק הסוליטר האחרון. כל מה שאתם צריכים זה לוח שחמט ושלושים ושניים כלים, או אותו מספר של דמקה או חיילים. באיור נעשה שימוש בחיילים ממוספרים. החידה היא להסיר את כל החיילים חוץ משניים, ושני אלה חייבים להיות במקור באותו צד של הלוח; כלומר, שני הנותרים חייבים להיות שייכים לקבוצה `1` עד `16` או לקבוצה השנייה, `17` עד `32`. מסירים חייל על ידי קפיצה מעליו עם חייל אחר למשבצת הבאה מעבר לו, אם המשבצת הזו פנויה, אבל אי אפשר לבצע קפיצה בכיוון אלכסוני. המהלכים הבאים יבהירו את המשחק: `3-11`, `4-12`, `3-4`, `13-3`. כאן `3` קופץ מעל `11`, ואתם מסירים את `11`; `4` קופץ מעל `12`, ואתם מסירים את `12`; וכן הלאה. יתגלה שזהו משחק סבלנות קטן ומרתק, והפתרון דורש הפעלת תושייה מסוימת. מקורות:

  • משחק החלוקים

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