Библиотека задач / Алгоритмы сравнения

Подростки и взрослые

Двадцать пять лошадей и короткая дорожка

Условие

Есть 2525 лошадей с различными постоянными скоростями. Любой забег точно ранжирует участников по скорости; усталости, ничьих и случайных колебаний нет. Одновременно могут бежать не более пяти лошадей. Секундомера нет: известен только порядок финиша внутри каждого забега. Покажите, как за семь забегов определить трёх самых быстрых лошадей и их порядок. Доказывать минимальность семи забегов не требуется.

О задаче · Подростки и взрослые
Тема
Алгоритмы сравнения
Для кого
Подростки и взрослые
Уровень библиотеки
Продвинутый · ориентир
Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

Сначала проведите пять забегов по пять лошадей, затем сравните победителей.

Подсказка 2

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

Разобрать решение по шагам
01

Разбейте на группы

Первые пять забегов проведём в пяти группах. Внутри каждой запишем лошадей от быстрой к медленной. В шестом забеге сравним победителей групп. Переименуем группы так, чтобы результат был

A1, B1, C1, D1, E1.A_1,\ B_1,\ C_1,\ D_1,\ E_1.

В группе AA порядок A1>A2>A3>A4>A5A_1>A_2>A_3>A_4>A_5, и так же для остальных. Здесь знак >> означает «быстрее».

02

Назовите общего победителя

Любая лошадь не быстрее победителя собственной группы, а A1A_1 победил всех победителей. Поэтому A1A_1 — самый быстрый из 2525. Он больше не нуждается в сравнении. Теперь нужно найти только второе и третье места.

03

Исключите тех, кто заведомо ниже третьего

В группах DD и EE даже лидеры уступают A1A_1, B1B_1, C1C_1. Лошадь C2C_2 и все ниже неё уступают A1A_1, B1B_1, C1C_1. Лошадь B3B_3 и все ниже неё уступают A1A_1, B1B_1, B2B_2. Лошадь A4A_4 и все ниже неё уступают A1A_1, A2A_2, A3A_3. У каждого исключённого есть три заведомо более быстрых соперника.

04

Проведите последний забег

Кроме уже найденного A1A_1 остаются A2A_2, A3A_3, B1B_1, B2B_2, C1C_1 — ровно пять лошадей. Они участвуют в седьмом забеге. Первый на его финише занимает общее второе место, второй — общее третье. Все остальные либо проиграли им сейчас, либо были исключены по доказанным сравнениям.

После забега победителей остаётся пять кандидатов
01A₁ быстрее всехпобедитель шестого забега
02A₂, A₃; B₁, B₂; C₁кандидаты на второе и третье места
03Седьмой забегего два лидера завершают тройку
Ответ

77 заездов. После пяти групповых заездов и заезда победителей сравнить A2,A3,B1,B2,C1A_2,A_3,B_1,B_2,C_1; два первых в нём дополняют победителя A1A_1 до тройки.

Главная идея

Сравнение даёт не только победителя: транзитивность позволяет исключать целые группы кандидатов.

Как заметить эту идею в другой задаче

В каждом заезде известно только взаимное место участников. После группового отбора и сравнения победителей исключайте тех, перед кем уже гарантированно есть трое.

Возможная ошибка

Сравнить победителей групп и объявить их тройку общей тройкой. Второй и третий в сильнейшей группе могут обогнать победителей других групп.

Источник и примечания

Источник и редакция

Классическая задача. Формулировка и разбор — Popov Academy.

Проверь себя

Если требуется найти только самого быстрого, сколько забегов достаточно по описанному плану и почему?

Ответ к дополнительной задаче

Шести: пять групповых забегов и один забег их победителей. Самый быстрый обязательно выиграет свою группу, а затем обгонит остальных победителей.

Продолжить тему: Поиск и алгоритмы →
Учебная схема

Popov Academy · Библиотека задач

Двадцать пять лошадей и короткая дорожка

https://popov.academy/library/adult-horse-races/

Условие

Есть 2525 лошадей с различными постоянными скоростями. Любой забег точно ранжирует участников по скорости; усталости, ничьих и случайных колебаний нет. Одновременно могут бежать не более пяти лошадей. Секундомера нет: известен только порядок финиша внутри каждого забега. Покажите, как за семь забегов определить трёх самых быстрых лошадей и их порядок. Доказывать минимальность семи забегов не требуется.

Дополнительная задача

Если требуется найти только самого быстрого, сколько забегов достаточно по описанному плану и почему?