חידה

[king iverson]

חידה

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

 

[עריסטו]

נסיון

קודם נחלק את הסוסים לחמש חמישיות וכל חמישיה תתחרה ואחר כך המנצחים בכל מרוץ יתחרו ביניהם. נניח שבחמישיה הראשונה התוצאה היא 1 2 3 4 5 (1 המהיר ו - 5 האיטי), בחמישיה השניה 6 7 8 9 10, בשלישית 11 12 13 14 15, ברביעית 16 17 18 19 20, ובחמישית 21 22 23 24 25. אז 1 6 11 16 21 מתחרים ביניהם ונניח שזו גם התוצאה (1 המהיר ו - 21 האיטי). אז אנחנו יודעים ש - 1 הוא המהיר ביותר ושהסוסים השני והשלישי הם שניים מבין 2 3 6 7 11. לכן החמישה האלה יתחרו ביניהם וכך נמצא את המקומות השני והשלישי. סך הכל שבעה מירוצים.

 

[אורי769]

שאלה

האם יש לך דרך להוכיח שלא ניתן בפחות?

 

[עריסטו]

אני חושב שבשישה מירוצים

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

 

[אורי769]

מעניין

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