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

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

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

  • ביקור בעיירות

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

  • חֲמִשָּׁה עָשָׂר פְּנוֹת

    הנה עוד חידת מסע מוזרה, שהפתרון שלה דורש תושייה. במקרה הזה, הנוסע מתחיל מהעיר השחורה ורוצה להגיע רחוק ככל האפשר תוך ביצוע חמש-עשרה פניות בלבד, ולעולם לא לנסוע באותה דרך פעמיים. ההנחה היא שהערים מרוחקות זו מזו במייל אחד. לדוגמה, נניח שהוא נסע ישר ל-A, אחר כך ישר ל-B, אחר כך ל-C, D, E ו-F, תגלו שהוא נסע שלושים ושבעה מיילים בחמש פניות. עכשיו, כמה רחוק הוא יכול להגיע בחמש-עשרה פניות? מקורות:

  • הזבוב על האוקטהדרון

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

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

     

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

    מקורות:

  • הפאזל של האיקוסהדרון

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

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

    מקורות:

  • בדיקת מכרה

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

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

    המלח המתואר באיור הצהיר שמאז נעוריו עסק במסחר עם כלי שיט קטן בין כעשרים איים קטנים באוקיינוס השקט. הוא סיפק את התרשים המחוספס שנתתי ממנו העתק, והסביר שהקווים מאי לאי מייצגים את המסלולים היחידים שהוא אי פעם אימץ. הוא תמיד התחיל מאי A בתחילת העונה, ואז ביקר בכל אי פעם אחת, ופעם אחת בלבד, וסיים את סיורו בנקודת ההתחלה A. אבל הוא תמיד דחה את ביקורו ב-C ככל האפשר, מטעמי מסחר שאיני צריך להיכנס אליהם. החידה היא לגלות את המסלול המדויק שלו, וניתן לעשות זאת בוודאות. קחו את העיפרון שלכם, ומתחילים ב-A, נסו לאתר אותו. אם תרשמו את האיים בסדר שבו אתם מבקרים בהם - לדוגמה, A, I, O, L, G וכו' - תוכלו לראות מיד אם ביקרתם באי פעמיים או השמטתם איזה מהם. כמובן, יש להתעלם מחציית הקווים - כלומר, עליכם להמשיך במסלולכם ישירות, ואין לכם רשות לעבור בצומת ולהמשיך בכיוון אחר. אין שום טריק מסוג זה בחידה. המלח ידע את המסלול הטוב ביותר. האם אתה יכול למצוא אותו? מקורות:

  • הטיול הגדול

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

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

    מקורות:

  • מים, גז וחשמל

    ישנם כחצי תריסר חידות, עתיקות כימי ההיסטוריה, שצצות ועולות תדיר, וכמעט שאין חודש בשנה שלא מביא עמו פניות בנוגע לפתרונן. מדי פעם אחת מהן, שאדם חשב שהיא הר געש כבוי, מתפרצת בצורה מפתיעה. קיבלתי מספר יוצא דופן של מכתבים בנוגע לחידה העתיקה שכיניתי "מים, גז וחשמל". היא עתיקה בהרבה מתאורת חשמל, או אפילו גז, אבל הלבוש החדש מעדכן אותה. החידה היא להניח מים, גז וחשמל, מ-W, G ו-E, לכל אחד משלושת הבתים, A, B ו-C, מבלי שאף צינור יחצה צינור אחר. קחו את העיפרון וציירו קווים המראים כיצד יש לעשות זאת. עד מהרה תמצאו את עצמכם נתקלים בקשיים. מקורות:

  • חידה לנהגים

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

  • חידה לחופשת בנק

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