danetka.ru

Есть 15 лошадей, бегающих с постоянными, у всех разными скоростями. В одном забеге могут участвовать не более 5 лошадей. Время мы замерять не умеем, умеем только фиксировать, кто в забеге был первый, кто второй и так далее. За сколько забегов можно определить трех самых быстрых лошадок?

Вроде за 5 получается
Нумеруем лошадок от 1 до 15. Разбиваем по пятеркам 1-5, 6-10, 11-15 (3 забега). Пусть расклад в группах получился по номерам: в первой группе вышли 1-3 (1>2>3), второй - 6-8, третьей - 11-13.
Далее в полуфинал выставляем 1, 2, 6, 7, 12 (забег 4). После этого во всех раскладах всегда есть возможность сформировать топ-5 лошадей.

Я еще думаю...
Очевидно, что трех забегов мало, а шести - точно хватит.
Справиться за пять забегов - тоже не очень сложно и есть много разных способов.
Это заставляет меня думать, что и четырех забегов может хватить, но пока не удалось этого ни доказать, ни опровергнуть.

Кстати, вопрос по формулировке задачи:
Требуется ли определить "порядок призеров"?

Юляша писал(а):Требуется ли определить "порядок призеров"?

Без понятия. Я напрочь забыл эту задачу. Надо решать заново.