Условие
Есть лошадей с различными постоянными скоростями. Любой забег точно ранжирует участников по скорости; усталости, ничьих и случайных колебаний нет. Одновременно могут бежать не более пяти лошадей. Секундомера нет: известен только порядок финиша внутри каждого забега. Покажите, как за семь забегов определить трёх самых быстрых лошадей и их порядок. Доказывать минимальность семи забегов не требуется.
О задаче · Подростки и взрослые
Записать идеюЕсть запись
Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.
Черновик не сохраняется: текст только в этой вкладке.
Черновик изменён в другой вкладке. Твой текущий текст пока сохранён здесь, автоматическая запись остановлена.
Подсказка 1
Сначала проведите пять забегов по пять лошадей, затем сравните победителей.
Подсказка 2
Если уже известны три лошади быстрее некоторой лошади, она не может попасть в общую тройку.
Разобрать решение по шагам
Разбейте на группы
Первые пять забегов проведём в пяти группах. Внутри каждой запишем лошадей от быстрой к медленной. В шестом забеге сравним победителей групп. Переименуем группы так, чтобы результат был
В группе порядок , и так же для остальных. Здесь знак означает «быстрее».
Назовите общего победителя
Любая лошадь не быстрее победителя собственной группы, а победил всех победителей. Поэтому — самый быстрый из . Он больше не нуждается в сравнении. Теперь нужно найти только второе и третье места.
Исключите тех, кто заведомо ниже третьего
В группах и даже лидеры уступают , , . Лошадь и все ниже неё уступают , , . Лошадь и все ниже неё уступают , , . Лошадь и все ниже неё уступают , , . У каждого исключённого есть три заведомо более быстрых соперника.
Проведите последний забег
Кроме уже найденного остаются , , , , — ровно пять лошадей. Они участвуют в седьмом забеге. Первый на его финише занимает общее второе место, второй — общее третье. Все остальные либо проиграли им сейчас, либо были исключены по доказанным сравнениям.
Ответ
заездов. После пяти групповых заездов и заезда победителей сравнить ; два первых в нём дополняют победителя до тройки.
Главная идея
Сравнение даёт не только победителя: транзитивность позволяет исключать целые группы кандидатов.
Как заметить эту идею в другой задаче
В каждом заезде известно только взаимное место участников. После группового отбора и сравнения победителей исключайте тех, перед кем уже гарантированно есть трое.
Возможная ошибка
Сравнить победителей групп и объявить их тройку общей тройкой. Второй и третий в сильнейшей группе могут обогнать победителей других групп.
Источник и примечания
Источник и редакция
Классическая задача. Формулировка и разбор — Popov Academy.
Проверь себя
Если требуется найти только самого быстрого, сколько забегов достаточно по описанному плану и почему?
Ответ к дополнительной задаче
Шести: пять групповых забегов и один забег их победителей. Самый быстрый обязательно выиграет свою группу, а затем обгонит остальных победителей.
Тема, знания и приёмы
Поиск и алгоритмы · Нужна школьная база
- Код писать не нужно. Понадобятся точный план и проверка всех возможных случаев.
Приёмы решения: Разделение пространства поиска