Савватеев2019q3

Вопрос Google: Есть 25 лошадей. Какое минимальное число забегов необходимо провести, чтобы определить 3 самых быстрых лошади? В одном забеге могут участвовать до 5 лошадей, но часов для замера времени у вас нет. [Савватеев2019_11:07]
{Савватеев для наглядности чертит таблицу из двадцати пяти ячеек, соответствующим количеству лошадей. Для начала он предлагает провести пять забегов и выявить в каждом из них чемпиона. Затем провести забег среди чемпионов, чтобы определить их места в забеге. Таким образом мы знаем, кто пришел первым, кто вторым и т. д. Для удобства можно пронумеровать чемпионов от 1 до 5, а те лошади, которые участвовали с ними в личном забеге, соответственно, входят в их группу. Задача осложняется тем, что у нас нет часов, и мы не знаем время каждой лошади, поэтому не можем точно сказать, что, к примеру, чемпион № 5 быстрее, чем какая-нибудь лошадь из группы 2. И здесь Савватеев применяет метод исключения лишних лошадей:
- исключаем всех участников групп 4 и 5, так как они уже не смогут войти в тройку лучших,
- также исключаем участников группы 3, кроме чемпиона,
- вычеркиваем последних двух из первой группы и последних трех из второй (они пришли последними в своих группах и так же не смогут быть в числе трех самых быстрых),
- остается 6 лошадей, но так как мы знаем абсолютного чемпиона, его можно не включать в забег.
Таким образом Савватеев за семь заездов определил трех победителей. Но все-таки лучше воспользоваться часами и определить победителей за 5 заездов.}

Савватеев2019_11:07

См. также Паундстоун2012p289