Решение. Кони (#106)
Ответ: 7
Решение
Шаг 1. Забеги 1–5
Необходимо прогнать всех лошадей, чтобы никого не обидеть. Поэтому, как минимум 5 забегов придётся устроить. Итак, разобьём всех лошадей на 5 групп (a, b, c, d, e) по 5 лошадей в каждой и устроим забеги внутри группы.
Заметим, что лошадь из глобального топ-3 обязательно войдёт в топ-3 заезда внутри группы. Поэтому круг претендентов сужается. Занумеруем лошадей по результатам заездов внутри групп: от a1 (самая быстрая в группе a) до e5 (самая медленная в группе e).
Шаг 2. Забег 6
Теперь свяжем результаты забегов на первом шаге. Для этого проведём забег среди чемпионов каждой групп. Без ограничения общности считаем, что a1 > [быстрее] b1 > c1 > d1 > e1.
Во-первых, a1 — глобальный чемпион (по транзитивности >).
Далее, понятно, что лошади d1 в топ-3 не быть. Может ли в топ-3 попасть, например, лошадь b3? Мы знаем, что b3 < b2 < b1 < a1, поэтому самое большое на что может рассчитывать b3 — это глобальное 4-е место.
Рассуждая аналогично, получаем 6 претендентов, как на рисунке 2.
Шаг 3. Забег 7
Так как с а1 всё решено на предыдущем шаге, то этой лошади в забегах участвовать нет необходимости. Поэтому оставшиеся 5 претендентов умещаются в один забег. Допустим, места распределились следующим образом
Это значит, что топ-3 составят a1 > a2 > b1. Прочие случаи рассматриваются аналогично.
Итого 7 забегов гарантированно определяют самую быструю тройку.
Оптимальность
Изложим доказательство на языке теории графов. Пусть вершины — это лошади, а ребро между двумя вершинами означает, что лошади заняли соседние места в забеге. Изначально у нас есть из 25 вершин без рёбер, а по мере проведения забегов будут появляться рёбра.
Чтобы определить хотя бы лидера (топ-1), необходимо иметь связный граф. Так как за забег появляется максимум 4 ребра, то 6 забегов — это необходимый минимум для определения лидера, не говоря уже о топ-3.
Заметим, что если от лидера ведут два ребра, то необходим седьмой забег, чтобы определить хотя бы топ-2.
Теперь, пусть мы совершили 5 забегов, поэтому у нас обязательно есть есть 5 связных подграфа (ровно 5 и только они). Хотя бы в одном из них — более двух вершин. В силу рандомности вершина в подграфе с более чем одной вершиной может быть лидером. Поэтому от неё пойдут два ребра. Значит, необходим седьмой забег.
