Задача про 25 лошадей

Есть ипподром, 5 беговых дорожек, табун из 25 лошадей/коней (все бегают с разной скоростью).

Условие ограничено тем, что любая выбранная лошадь X в любом забеге скачет с одинаковой скоростью.

При этом использовать ничего нельзя (секундомеры, калькуляторы и так далее).

Нужно найти среди них 3-х самых быстрых и какое минимальное количество забегов на это потребуется.

Ответ: 7 забегов!

Решение:

Нарисуем пять груп, с номерами лошадей по-порядку:

Проведем 5 забегов в пяти группах.

В следующем забеге ставим лошадей, победивших в своей группе.

На рисунке это 1, 6, 11, 16, 21 лошадь. Для простоты отображения будем считать что лошади на рисунке расположены по убыванию их скоростей после забегов.

Итого мы провели уже 6-й забег.

Нарисуем последнюю картинку и разберем ее:

Почему мы исключили 4-ю и 5-ю группу? Потому что если призеры этих групп оказались медленнее 3-го места в общем зачете, то остальные и подавно!

Теперь разберем почему мы исключили номер 12-й и ниже следующие за ним номера. Если 12-й номер медленнее 11, то он никак не может быть в тройке призеров, а тем более номера ниже.

Пойдем дальше. Почему мы оставили в «потенциальных» 7 номер? Потому что он может претендовать на 3-е место в общем зачете! Мы же не знаем наверняка, что он медленнее 11-го номера, они никогда в одной группе не участвовали. Почему же мы исключили 8-й номер? Потому, что претендент на 3-е место в общем зачете может быть только один.

С первой группой проводим аналогичные рассуждения. Мы оставили номера 2 и 3, потому как они являются потенциальными претендентами на 2 и 3-е место в общем зачете.

И последний 7-й забег. Выставляем в него все потенциальные номера обозначенные красным (2, 3, 6, 7, 11), кроме 1-го, выявляя таким образом 2 и 3-е место в общем зачете. 1-е место абсолютного чемпиона было выявлено еще в 6-й скачке.