קומבינטוריקה

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

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

  • הלוח בתאים

     

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

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

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

    מקורות:

  • מסעי ארבעת הפרשים

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

  • מסע הפרשייה הקוביסטי

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

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

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

  • תרגיל לאסירים

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

     

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

    >
    8 3 12 1
    11 14 9 6
    4 7 2 13
    15 10 5

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

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

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

    מקורות:

  • חידת המכלאה

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

  • שני הרגלים

    הנה חידה קטנה ומסודרת בספירה. בכמה דרכים שונות יכולים שני הרגלים להתקדם למשבצת השמינית? אתה רשאי להזיז אותם בכל סדר שתרצה כדי ליצור רצף שונה. לדוגמה, אתה יכול להזיז את הרגלי `Q R P` (משבצת אחת או שתיים) תחילה, או את הרגלי `K R P` תחילה, או רגלי אחד רחוק ככל שתרצה לפני שאתה נוגע בשני. כל רצף מותר, רק בחידה הזו ברגע שרגלי מגיע למשבצת השמינית הוא מת, ונשאר שם ללא המרה. האם אתה יכול לספור את מספר הרצפים השונים? בהתחלה זה ייראה לך קשה מאוד, אבל אני אראה שזה ממש פשוט כשמתקיפים את זה כמו שצריך.

    מקורות:

  • הַצָּבַת הַלּוּחַ

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

  • ספירת מלבנים

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

  • מבוי סתום

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