Зарядка для ума: кто быстрее в автогонке?

Приложение Русской службы BBC News доступно для IOS и Android. Вы можете также подписаться на наш канал в Telegram.

В чемпионате по автоспорту участвуют 100 машин; в одной гонке могут участвовать любые 10 из них. Можно ли определить четыре самых быстрых машины не более чем за 12 гонок?

(Предполагается, что более быстрая машина всегда обгоняет более медленную.) Оказывается, это не так сложно.

Автор фото, Getty Images

Да, можно.

Ответ

Мысленно расположим все 100 машин в виде квадрата 10x10, и первые 10 гонок проведем по столбцам этого квадрата.

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

После нее переставим местами столбцы так, чтобы расположить их по порядку (самая быстрая машина - в самом левом столбце).

Теперь машины, претендующие на попадание в первую четвёрку, расположены только в таких десяти позициях:

Если эти 10 машин поставить в последнюю гонку, то ее результаты правильно определят первые 4 машины.

Замечание. Более простое - интуитивно почти очевидное - решение требует 16 гонок. В первой гонке участвуют любые 10, в каждой следующей - 4 лучших машины предыдущей гонки и 6 еще не участвовавших. Тогда все 100 машин пройдут за 1+(100-10)/6 = 16 гонок, в конце определятся 4 лучших машины.

Источник: загадка народная, версия К. Кнопа