У вас имеется 25 скаковых лошадей, среди которых требуется выбрать трех самых быстрых. К сожалению, вам запрещено пользоваться любыми измерениями для определения скорости лошади или времени забега.
Какое минимальное количество забегов потребуется провести, если в скачках одновременно могут участвовать только 5 лошадей?
Ответ: Потребуется 7 забегов.
Разбиваем лошадей на 5 равных групп A, B, C, D, E и в каждой группе проводим забег. Результаты запишем в виде:
A1, A2, A3, A4, A5
B1, B2, B3, B4, B5
C1, C2, C3, C4, C5
D1, D2, D3, D4, D5
E1, E2, E3, E4, E5
где число означает занятое место. Например, B2 - лошадь, занявшая 2-е место в группе B
Проводим забег между победителями каждой группы. Результат запишем в виде:
A1, B1, C1, D1, E1
Отсюда однозначно определяем самую быструю лошадь - это A1.
Теперь отберем лошадей, которые могут претендовать на два оставшихся призовых места:
Группа A: отбрасываем A4 и A5, т.к. они уступили трем лошадям в своей группе; остаются A2 и A3.
Группа B: отбрасываем B3, B4 и B5, т.к. они уступили B1 и B2, которые в свою очередь уступили A1; остаются B1 и B2.
Группа C: отбрасываем C2, C3, C4 и C5, которые уступили C1, B1 и A1; остается только C1.
В группах D и Е претендентов быть не может, т.к. даже победители этих групп проиграли лошадям A1, B1 и C1.
Итого 5 претендентов, среди которых проводим последний забег:
A2, A3, B1, B2, C1
Первые две лошади в этом забеге и будут искомыми.
Комментарии
проедположим что В5 пробежал быстрее чем С1 и А1
как данное решение может согласовать данную ситуацию????
В5 не может быть лучше А1, так как в 6-м забеге А1 опередила В1, а В1 уже раньше опережала В5.
Почему не 6 забегов? Каждая группа делает по 1 забегу, таким образом выделяется 5 самых быстрых лошадей, т.к. остальные лошади уступили тем, кто победил в своей группе. Это 5 заездов. И 6-й между первыми местами каждой из групп. Таким образом, первые 3 пришедших лошади становятся самыми быстрыми.
Например, в группу A могут попасть все 3 самые быстрые лошади. А вы возьмете из этой группы всего одну
Вроде намного больше чем 7, т.к. н.р. у моих лошадей скорости от 1-25 км/ч.
а если 2 и 3 по скорости в группе Е? они проиграли А1, но дальше их сразу выкинули
E1 уступила A1, B1 и C1 в шестом забеге, поэтому из группы E никто в тройку лучших войти не может
Всё верно, но решение написано коряво, поэтому вызывает много вопросов.
Пронумеровать лошадей указанным образом можно только после 6-го забега, а не после 5-го, как написано в решении.
А где доказательство того, что 7 это минимальное количество забегов?
Минимальное количество забегов - 11, не меньше. При условии, что лошади не устают и каждый забег бегут за одинаковое время.
НАМ НЕОБХОДИМО АБСОЛЮТНО ВСЕХ ЛОШАДЕЙ СРАВНИТЬ МЕЖДУ СОБОЙ.
1й забег - 3 выиграли из 5ти - осталось 23 лошади, (три самые быстрые лошади из первого забега перешли во второй забег, 2 выбыло)
2й забег - 3 выиграли из 5ти - осталось 21 (три самые быстрые лошади из второго забега перешли в третий забег)
3й забег - 3 выиграли из 5ти - осталось 19 (три самые быстрые лошади из третьего забега перешли в четвёртый забег)
4й забег - 3 выиграли из 5ти - осталось 17 (три самые быстрые лошади из четвертого забега перешли в пятый забег)
5й забег - 3 выиграли из 5ти - осталось 15
(три самые быстрые лошади из пятого забега перешли в шестой забег)
6й забег - 3 выиграли из 5ти - осталось 13 (три самые быстрые лошади из шестого забега перешли в седьмой забег)
7й забег - 3 выиграли из 5ти - осталось 11 (три самые быстрые лошади из седьмого забега перешли в восьмой забег)
8й забег - 3 выиграли из 5ти - осталось 9 (три самые быстрые лошади из восьмого забега перешли в девятый забег)
9й забег - 3 выиграли из 5ти - осталось 7 (три самые быстрые лошади из девятого забега перешли в десятый забег)
10 забег - 3 выиграли из 5ти - осталось 5 (три самые быстрые лошади из 10 забега перешли во одиннадцатый забег)
11 забег - 3 выиграли из 5ти - осталась лучшая тройка лошадей.
При условии, что лошадь не устает и бежит каждый забег за одинаковое время.
Одна проблема.
Лошади не паровозы, они устают. Скорость лошади, бегущей свой второй забег уже не та, что в первом забеге.
Говоря языком математики, забеги в этом турнире не являются взаимно-независимыми испытаниями.
--------------------------------------------------
Допустим, лошадь Е1 самая быстрая среди всех 25 лошадей. Но в первом забеге она "выложилась". Свою первую дистанцию она летела птицей. Свой второй забег она плелась в хвосте как кляча.
Лошадь же А1 по скорости возглавляет третий десяток в рейтинге-25. Обогнать она может всего четверых из 25. Просто в своём первом забеге она поберегла силы, чтобы хорошо выступить во втором туре.
Лошади Е2 и Е3 лишь чуть-чуть уступают Е1 в скорости, но весьма выносливы. Во втором туре они бы уверенно заняли первое и второе места. Но наш прекрасный алгоритм даже не допускает их во второй тур.
--------------------------------------------------
Формально-то алгоритм вроде правильный, не придерёшься. Просто применять его к испытаниям лошадей нет никакого практического смысла.
Применять этот алгоритм к "неустающим" паровозам тоже бессмысленно. Максимальная скорость паровоза известна с момента выхода его за ворота завода-изготовителя и указана производителем в паспорте изделия. Можно сравнивать даже не проводя "забегов".
--------------------------------------------------
Так что просто алгоритм ради алгоритма. Чистая схоластика. "Сколько бесов поместится на острие иглы?" Да сколько надо, столько и поместится! Сколько бы бесов у вас ни нашлось, я всегда сумею подобрать такую иглу, чтобы на её острие им хватило места. То же самое с этими лошадьми. Заранее зная, что будет применяться именно этот алгоритм, и объективно представляя возможности каждого из 25 скакунов, всегда можно так сформировать "пятёрки участников" в первом туре забегов, чтобы первые три места в турнире достались заранее намеченным лошадкам.