Написать пост

У вас есть 25 лошадей. Сколько забегов вам нужно устроить, чтобы определить трех самых быстрых из них?

Аватар Типичный программист

Обложка поста У вас есть 25 лошадей. Сколько забегов вам нужно устроить, чтобы определить трех самых быстрых из них?

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

Вы можете начать свой ответ с уточнения: спросите интервьюера, следует ли считать «самой быстрой лошадью» ту, которая выигрывает конкретную скачку. Хотя этот вариант не работает на ипподроме, он в значительной степени упрощает задачу: предположим, что если А побеждает В в одной гонке, то А объективно и бесспорно более быстрая лошадь, чем В. Если вам скажут, что использовать это допущение можно, то в отдельной гонке действительно победит самая быстрая лошадь.

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

Логично. Второй вывод: пяти забегов недостаточно. Разделите 25 лошадей на группы по пять, и устройте забеги. В каждом забеге одна лошадь будет конкурировать с другими четырьмя. Скажем, в одной из гонок будут участвовать лошади, которые придут к финишу в следующем порядке.

1. Ридонна2. Бавкида3. Харцея4. Вероника5. Альмадена

Хотя в этом забеге победила Ридонна, по его результатам вы не можете прийти к выводу, что она является самой быстрой лошадью из 25 или даже входит в тройку сильнейших. Чтобы пояснить последнее утверждение, воспользуемся крайним случаем: представим, что все самые медленные лошади в других заездах являются более быстрыми, чем Ридонна (которая, возможно, в общем рейтинге займет лишь 21-е место из 25 возможных).

Узнали ли мы что-нибудь из этого заезда? Разумеется, да. Мы узнали, как проранжировать пять конкретных лошадей. Мы также узнали, что можем вычеркнуть из числа претенденток на число лучших Веронику и Альмадену. Поскольку они не вошли в тройку первых в этом заезде, они не могут быть и в тройке самих быстрых из 25 лошадей.

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

Шестая гонка должна сравнить лошадей, которые хорошо показали себя в первых пяти заездах. Кажется разумным устроить гонки для победителей первых пяти заездов. Давайте так и сделаем. Возьмем Ридонну из заезда, описанного выше, и отправим ее на соревнования с победителями других заездов. Конечный результат может выглядеть следующим образом.

1. Фидана2. Ридонна3. Флавия4. Принцесса Гита5. Сикарель

Опять же мы можем обоснованно вычеркнуть из числа претендентов на победу Принцессу Гиту и Сикарель. Они, очевидно, если руководствоваться результатами этого забега, не могут входить в число трех быстрейших из 25. Мы также узнаем, что самой быстрой лошадью является Фидана, поскольку она опередила всех остальных лошадей, которые были первыми в предыдущих забегах. Если вопрос заключался бы в том, чтобы определить самую быструю лошадь из 25, то мы уже получили бы ответ. Ею является Фидана.

Однако нам надо определить трех самых быстрых. Из числа претенденток на победу мы можем вычеркнуть не только Принцессу Гиту и Сикарель, но и всех тех лошадей, которых они опередили в первых скачках. Лошади, которых они опередили, были более медленными, а мы уже знаем, что победители двух забегов из списка вычеркнуты.

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

Теперь перейдем к Ридонне. Исходя из последней гонки, она, возможно, в лучшем случае является второй лошадью из всех. Это оставляет открытым вопрос о Бавкиде. которая в первом круге пришла второй, после Ридонны, но в целом она может быть третьей из всех лошадей. (В этом случае список победителей был бы таким: Фидана, Ридонна, Бавкида).

Харцея, пришедшая третьей в первой гонке, где победителем была Ридонна, теперь выбывает из дальнейшего участия.

Две лошади, пришедшие второй и третьей после Фиданы в первой гонке, все еще остаются претендентами. Возможно, эти лошади быстрее Ридонны. но они никогда с ней не соревновались.

Итак, осталось шесть лошадей. Из них три были первыми в последней гонке: две, которые пришли второй и третьей в гонке с общим победителем, и одна, которая пришла второй в своей первой гонке, уступив только лошади, которая в общем зачете заняла второе место.

Мы уже знаем, что самая быстрая из всех лошадей — Фидана. По этой причине нет смысла опять устраивать с ней гонки. Остается всего пять лошадей. Естественно, мы устроим забег для них в седьмом и последнем раунде. Первые две лошади, оказавшиеся здесь победителями, в итоге займут второе и третье места.

Небольшое изменение правил. Начните с квалификационного раунда из пяти забегов, в которых будут соревноваться все 25 лошадей. Затем выберите вариант чемпионской гонки: в следующий круг будут допущены только победители квалификационных заездов. Лошадь, которая придет первой во второй гонке, и станет общим победителем.

Разбор по книге «Действительно ли Вы достаточно умны, чтобы работать в Google?»

Следите за новыми постами
Следите за новыми постами по любимым темам
47К открытий47К показов