קומבינטוריקה, בדיקת מקרים, תהליכים

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

  • שני הרגלים

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

    מקורות:

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

    הנה משחק סוליטר קטן שהוא די קל, אבל לא כל כך קל שהוא לא מעניין. אתה יכול לסמן את הריבועים על גיליון קרטון או נייר, או שאתה יכול להשתמש בחלק מלוח השחמט שלך. הצגתי אסימונים ממוספרים באיור כדי להפוך את הפתרון לקל ומובן לכולם, אבל חיילי שחמט או דמקה יתאימו באותה מידה בפועל. הפאזל הוא להסיר את כל האסימונים מלבד אחד, והאחד הזה שנשאר חייב להיות מס' `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`; וכן הלאה. יתגלה שזהו משחק סבלנות קטן ומרתק, והפתרון דורש הפעלת תושייה מסוימת. מקורות:

  • קערת הוואסייל

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

    מקורות:

  • חביות הדבש

     

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

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

    מקורות:

  • חציית הנחל

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

  • חציית נהר אקס

    לפני שנים רבות, בימי המבריח הידוע כ"רוב רוי של המערב", כנופיית פיראטים קברה על חוף דרום דבון כמות של אוצר אשר, כמובן, ננטש על ידם בצורה בלתי מוסברת כרגיל. כעבור זמן מה, מקום הימצאו התגלה על ידי שלושה כפריים, אשר ביקרו במקום לילה אחד וחלקו את השלל ביניהם, ג'יילס לקח אוצר בשווי £`800`, ג'ספר בשווי £`500`, וטימותי בשווי £`300`. בחזרתם הם נאלצו לחצות את נהר אקס בנקודה שבה הם השאירו סירה קטנה בהיכון. כאן, עם זאת, הייתה קושי שלא ציפו לו. הסירה יכלה לשאת רק שני אנשים, או אדם אחד ושק, והיה להם כל כך מעט אמון זה בזה שאף אדם לא יכול היה להישאר לבד על היבשה או בסירה עם יותר מחלקו בשלל, אם כי שני אנשים (בהיותם בלמים זה על זה) עשויים להישאר עם יותר מחלקם. החידה היא להראות כיצד הם עברו את הנהר במספר המינימלי האפשרי של חציות, תוך שהם לוקחים איתם את האוצר שלהם. אין להשתמש בתחבולות, כגון חבלים, "גשרים מעופפים", זרמים, שחייה או תחבולות דומות. מקורות:

  • חֲמִשָּׁה בְּעָלִים קַנָּאִים

    בְּמַהֲלַךְ שִׁטְפוֹנוֹת מְקוֹמִיִּים מְסוּיָּמִים, חֲמִשָּׁה זוּגוֹת נְשׂוּאִים מָצְאוּ אֶת עַצְמָם מֻקָּפִים בְּמַיִם, וְהָיוּ צְרִיכִים לִבְרֹחַ מִמַּצָּבָם הַבִּלְתִּי נָעִים בְּסִירָה שֶׁיָּכְלָה לְהַכִיל רַק שְׁלֹשָׁה אֲנָשִׁים בְּכָל פַּעַם. כָּל בַּעַל הָיָה כָּל כָּךְ קַנָּא שֶׁלֹּא הָיָה מַרְשֶׁה לְאִשְׁתּוֹ לִהְיוֹת בַּסִּירָה אוֹ עַל אַחַת הַגְּדוֹת עִם גֶּבֶר אַחֵר (אוֹ עִם גְּבָרִים אֲחֵרִים) אִם הוּא עַצְמוֹ לֹא הָיָה נוֹכֵחַ. הַצִּיגוּ אֶת הַדֶּרֶךְ הַמְּהִירָה בְּיוֹתֵר לְהַעֲבִיר אֶת חֲמֵשֶׁת הָאֲנָשִׁים הָאֵלֶּה וְנְשֵׁיהֶם לְמָקוֹם מִבְטָחִים.

    קִרְאוּ לַגְּבָרִים A, B, C, D, E, וְלִנְשֵׁיהֶם הַתּוֹאֲמוֹת a, b, c, d, e. מַעֲבָר וְחֲזָרָה נֶחְשָׁבִים כִּשְׁנֵי חֲצִיּוֹת. אֵין לְהִשְׁתַּמֵּשׁ בְּטְרִיקִים כְּגוֹן חֲבָלִים, שְׂחִיָּה, זְרָמִים וְכוּ'.

    מקורות:

  • ארבע הבריחות

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

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

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

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

    במשך זמן רב היה זה תעלומה כיצד הצליחה קבוצת שמונת האנשים לחצות את הנהר בסירה הקטנה ההיא מבלי שאף נערה תישאר אי פעם עם גבר, אלא אם כן גם ארוסה היה נוכח. השיטה המועדפת היא לקחת שמונה אסימונים או פיסות קרטון ולסמן אותם A, B, C, D, a, b, c, d, כדי לייצג את ארבעת הגברים ואת הכלות העתידיות שלהם, ולשאת אותם מצד אחד של שולחן למשנהו בקופסת גפרורים (כדי לייצג את הסירה), כאשר מטבע מוצב באמצע השולחן כאי.

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

    מקורות:

  • גְּנֵבַת אוֹצַר הַטִּירָה

    הַדֶּרֶךְ הַמְּתוּחְכֶּמֶת בָּהּ נִגְנְבָה תֵּבַת אוֹצָר, הַמְּכִילָה בְּעִיקָרָהּ תַּכְשִׁיטִים וַאֲבָנִים יְקָרוֹת, מִטִּירַת גְּלוּמְהֶרְסְט, עָבְרָה כְּמָסֹרֶת בְּמִשְׁפַּחַת דֶּה גּוּרְנֵי. הַגַּנָּבִים הִתְכַּלְּלוּ מֵאִישׁ, נַעַר וְיֶלֶד קָטָן, שֶׁדֶּרֶךְ הַמִּלּוּט הַיְּחִידָה שֶׁלָּהֶם עִם תֵּבַת הָאוֹצָר הָיְתָה דֶּרֶךְ חַלּוֹן גָּבוֹהַּ. מִחוּץ לַחַלּוֹן הוּצַּב גַּלְגֶּלֶת, שֶׁעָלֶיהָ עָבַר חֶבֶל עִם סַל בְּכָל קָצֶה. כְּשֶׁסַּל אֶחָד הָיָה עַל הַקַּרְקַע, הַשֵּׁנִי הָיָה בַּחַלּוֹן. הַחֶבֶל סֻדַּר כָּךְ שֶׁהָאֲנָשִׁים בַּסַּל לֹא יָכְלוּ לַעֲזֹר לְעַצְמָם בְּאֶמְצָעוּתוֹ וְלֹא לְקַבֵּל עֶזְרָה מֵאֲחֵרִים. בְּקִצּוּר, הַדֶּרֶךְ הַיְּחִידָה לְשִׁמּוּשׁ בַּסַּלִּים הָיְתָה עַל יְדֵי הַצָּבַת מִשְׁקָל כָּבֵד יוֹתֵר בְּאֶחָד מֵהַשֵּׁנִי.

    עַכְשָׁו, מִשְׁקַל הָאִישׁ הָיָה `195` לִיבְּרוֹת, הַנַּעַר `105` לִיבְּרוֹת, הַיֶּלֶד `90` לִיבְּרוֹת וְתֵּבַת הָאוֹצָר `75` לִיבְּרוֹת. הַמִּשְׁקָל בַּסַּל הַיּוֹרֵד לֹא יָכֹל לַחְרֹג מִזֶּה שֶׁבַּשֵּׁנִי בְּיוֹתֵר מִ `15` לִיבְּרוֹת בְּלִי לִגְרֹם לִירִידָה כֹּה מְהִירָה שֶׁתִּהְיֶה מְסֻכֶּנֶת בְּיוֹתֵר לְבֶן אָדָם, אַף עַל פִּי שֶׁלֹּא תִּגְרֹם נֶזֶק לָרְכוּשׁ הַגָּנוּב. רַק שְׁנֵי אֲנָשִׁים, אוֹ אָדָם אֶחָד וְהָאוֹצָר, יָכְלוּ לְהָנִיחַ בְּאוֹתוֹ סַל בְּבַת אַחַת. אֵיךְ הֵם הִצְלִיחוּ לִבְרֹחַ וְלָקַחַת אִתָּם אֶת תֵּבַת הָאוֹצָר?

    הַחִידָה הִיא לִמְצֹא אֶת הַדֶּרֶךְ הַקְּצָרָה בְּיוֹתֵר לְבִצּוּעַ הַמַּעֲשֶׂה, שֶׁכְּשֶׁעַצְמוֹ אֵינוֹ קָשֶׁה. זִכְרוּ, אָדָם לֹא יָכוֹל לַעֲזֹר לְעַצְמוֹ עַל יְדֵי תְּלִיָּה עַל הַחֶבֶל, הַדֶּרֶךְ הַיְּחִידָה הִיא לָרֶדֶת "עִם מַהֲלוּמָה," כְּשֶׁהַמִּשְׁקָל בַּסַּל הַשֵּׁנִי כְּמִשְׁקָל נֶגְדִּי.

    מקורות: