צילום: Jeff Kubina, Wikimedia Commons (CC BY-SA 2.0)

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

ברשותכם מסלול מרוץ אחד ובו חמישה נתיבים בלבד. כלומר בכל מרוץ אפשר להריץ לכל היותר חמישה סוסים יחד.

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

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

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

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

רמז דק

התחילו מהמובן מאליו: חמישה מרוצים שבהם כל אחד מעשרים וחמישה הסוסים רץ בדיוק פעם אחת. עכשיו יש בידכם חמש רשימות מסודרות.

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

רמז עבה

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

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

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

פתרון

התשובה: שבעה מרוצים בלבד.

שלב ראשון - חמישה מרוצי מוקדמות

מחלקים את עשרים וחמישה הסוסים לחמש קבוצות בנות חמישה, ומריצים כל קבוצה. נסמן את הקבוצות באותיות A עד E, ובכל קבוצה נסמן את הסוסים לפי סדר ההגעה: A1 מהיר מ-A2, שמהיר מ-A3, וכן הלאה.

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

שלב שני - מרוץ המנצחים

המרוץ השישי מפגיש את חמשת המנצחים: A1, B1, C1, D1, E1. נניח שסדר ההגעה שלהם הוא A1, B1, C1, D1, E1.

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

שלב שלישי - מי עדיין במשחק?

נסרוק את המועמדים לשני המקומות שנותרו:

קבוצות D ו-E נפסלות כולן. D1 הפסיד ל-A1, ל-B1 ול-C1 - שלושה מהירים ממנו. E1 הפסיד לארבעה. וכל השאר בקבוצות האלה איטיים אף מהמנצחים שלהן.

מקבוצה C נשאר רק C1. הוא הפסיד רק ל-A1 ול-B1, ולכן עדיין מועמד למקום השלישי. C2 כבר הפסיד לשלושה - ל-C1, ל-B1 ול-A1 - ונפסל.

מקבוצה B נשארים B1 ו-B2. B1 הפסיד רק ל-A1, ולכן הוא מועמד למקום השני. B2 הפסיד ל-B1 ול-A1 - שניים בלבד - ולכן עדיין מועמד למקום השלישי. B3 כבר הפסיד לשלושה ונפסל.

מקבוצה A נשארים A2 ו-A3. A2 הפסיד רק ל-A1, ו-A3 הפסיד ל-A1 ול-A2. שניהם עדיין בתמונה. A4 הפסיד לשלושה ונפסל.

ספרנו: A2, A3, B1, B2, C1 - בדיוק חמישה מועמדים. וזה לא צירוף מקרים: זה בדיוק מספר הנתיבים שיש לנו.

שלב רביעי - המרוץ השביעי

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

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

סך הכול: 5 ועוד 1 ועוד 1 - שבעה מרוצים.

ולמה שישה לא מספיקים?

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

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

לכן דרוש מרוץ שביעי, ושבעה הם המינימום.

ומה אם רוצים גם את המקום הרביעי?

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