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

הולך רגל יוצא מהצומת שבפינה הדרומית-מערבית של הרשת, ורוצה להגיע לצומת שבפינה הצפונית-מזרחית.

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

כמה מסלולים קצרים ביותר שונים עומדים לרשותו?

שימו לב: אפשר לפתור את זה בלי לצייר ולו מסלול אחד.

רמז דק

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

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

רמז עבה

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

לאורך הרחוב התחתון ולאורך הרחוב השמאלי ביותר יש מסלול אחד בלבד לכל צומת, ולכן רושמים שם 1.

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

זהו בדיוק משולש פסקל, שהתיישב על רשת של רחובות.

פתרון

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

לבחור מסלול פירושו לבחור באילו ארבעה מקומות מתוך שמונה יופיעו הצעדים מזרחה. מספר האפשרויות הוא מספר הצירופים של 4 מתוך 8:

8 עצרת חלקי (4 עצרת כפול 4 עצרת), כלומר 40320 חלקי (24 כפול 24), שהם 40320 חלקי 576.

התוצאה: 70 מסלולים קצרים ביותר.

אפשר לאמת את זה גם בשיטה הוויזואלית של הרמז העבה. ממלאים את הרשת שורה אחר שורה, מלמטה למעלה:

השורה התחתונה: 1, 1, 1, 1, 1.

השורה השנייה: 1, 2, 3, 4, 5.

השורה השלישית: 1, 3, 6, 10, 15.

השורה הרביעית: 1, 4, 10, 20, 35.

השורה העליונה: 1, 5, 15, 35, 70.

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

אגב, ברשת של n בלוקים על n בלוקים התשובה הכללית היא מספר הצירופים של n מתוך 2n. ברשת 2 על 2 יש 6 מסלולים, ברשת 3 על 3 יש 20, וברשת 8 על 8 כבר יש 12870.