צילום: Antti T. Nissinen, Wikimedia Commons (CC BY 2.0)

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

הכללים ברורים:

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

זמני החצייה של הארבעה שונים זה מזה:

דנה - דקה אחת
יונתן - שתי דקות
מיכל - חמש דקות
אבי - עשר דקות

הרביעייה חייבת להיות כולה בצד השני של הגשר תוך שבע עשרה דקות.

השאלה: מהו סדר המעברים שמאפשר זאת?

רמז דק

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

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

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

רמז עבה

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

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

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

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

פתרון

התשובה: שבע עשרה דקות בדיוק, בחמישה מעברים.

1. דנה ויונתן חוצים יחד - 2 דקות. (בצד המרוחק: דנה, יונתן)
2. דנה חוזרת עם הפנס - דקה אחת. (בצד המרוחק: יונתן)
3. מיכל ואבי חוצים יחד - 10 דקות. (בצד המרוחק: יונתן, מיכל, אבי)
4. יונתן חוזר עם הפנס - 2 דקות. (בצד המרוחק: מיכל, אבי)
5. דנה ויונתן חוצים יחד - 2 דקות. (בצד המרוחק: כולם)

סך הכול: 2 + 1 + 10 + 2 + 2 = 17 דקות.

הרעיון בבסיס

שני האיטיים הם הבעיה. כל עוד כל אחד מהם חוצה בנפרד, אנחנו משלמים גם 10 וגם 5. ברגע שהם חוצים יחד, אנחנו משלמים 10 בלבד - והחמש של מיכל "מתחבאות" בתוך העשר של אבי.

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

יש גם וריאציה שנייה

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

ומה אם הזמנים היו אחרים?

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