על נמלים, נזירים ומסלולים צרים

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

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

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

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

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

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

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

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

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

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

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

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

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

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