100. Лошадиные бега

7

7

6 заездов. Все лошади произвольным образом бъются на 5 пятерок и проводится 5 заездов, назовем их отборочными. В 6-ом, финальном заезде учавствуют лошади, пришедшие вторыми в отборочных заездах. Три самых быстрых лошади это лошадь пришедшая первой в финальном заезде и лошади, пришедшие первыми в отборочных заездах лошадей, занявших первое и второе места в финальном заезде.

решение ошибочно, снимаю сам ))

Ваш метод подойдёт для вычисления абсолютного победителя, а вот 2 и 3 место может быть полученно не заслуженно.(например в 1 забеге конь, который пришёл 2ым был бы лучшим в 2или3 или 4 или 5, но был отсеен, так как попал с абсолютным победителем)

7
5х5-5заездов(А,Б,В,Г,Д)
Выигрывшие-6 заезд(Е), победитель общий-1место
2 и 3 места из первого заезда где был победительЕ,2Е+2место из его первого с ним заезда,3Е,-заезд 7(1м-итог2общее,2м-3общее)

7
5х5-5заездов(А,Б,В,Г,Д)
Выигрывшие-6 заезд(Е), победитель общий-1место
2 и 3 места из первого заезда где был победительЕ,2Е+2место из его первого с ним заезда,3Е,-заезд 7(1м-итог2общее,2м-3общее)

7 заездов.

Доказательство:

1. Очевидно, минимальное число заездов N>5, так как увидеть каждую из 25 лошадей в деле невозможно менее чем при пяти забегах, при условии, что в забеге участвует максимум 5 лошадей. А гарантированное определение трёх лучших очевидно требует ещё
большего числа заездов.

2. Если более быстрая лошадь всегда победит более медленную, значит лошадь побеждающая другую лошадь гарантировано победит всех ею побеждённых.

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

4. Не факт, что лошадь B побеждённая в туре 1 лошадью A, проиграет лошади С из другой пятёрки проигравшей лошади А во втором туре. Ведь две самых быстрых лошади могут попасть в первом туре.

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

6. Из пункта №5 следует, что кратчайший путь решения задачи — решение через определение быстрейшей лошади. Чего нельзя добиться менее чем за 6 забегов. Пять отборочных и шестой забег победителей. Следовательно, N>6.

7. Лошадь пришедшая первой в забеге чемпионов гарантировано лучшая из 25. Но пришедшая второй — лучшая из 20, а пришедшая третьей — лучшая из 15. Необходимо сравнить с ними пришедших второй и третьей в первом туре в забеге, в котором выиграла чемпион чемпионов. А так же необходимо установить место лошади пришедшей
второй в первом забеге против лошади ставшей второй в забеге чемпионов, на случай если она в тройке наибыстрейших. Потому, делаем ещё один забег, в котором участвуют вышеупомянутые лошади вылетевшие в первом туре и лошади пришедшие в забеге чемпионов
второй и третьей. После этого забега тройка лучших будет гарантировано выявлена.

А почему вы считаете, что в первом забеге, в котором участвовал чемпион чемпионов не могли оказаться 5 самых быстрых лошадей из всех 25-ти?

Мне кажется, что здесь надо идти от обратного и просто убирать самых медленных.

лошади заезды
25 5
15 3
9 2
6 1
4 1
итого 12

Я проиллюстрирую ответ Гидона выше, потому что согласен с ним, но он слишком затуманил свой ответ.

1. Проводим 5 заездов, каждый раз с новой пятеркой.
2. Проводим 6-й заезд, в котором участвую только победители первых пяти.

Теперь составляем квадратную таблицу 5х5: в первую строку выпишем участников 6-го заезда слева направо по убыванию результата: ABCDE
Под каждым из них запишем участников первых пяти забегов, в которых участвовал "житель" данного столбца, по убыванию сверху вниз.
Получаем:
ABCDE
FGHIJ
KLMNO
PQRST
UVWXY
Можно представлять себе, что под буквами скрываются различные числа, и в первой строке они расположены по убыванию, как и в любом столбце, а по другим строкам и тем более диагоналям информации нет. Если писать это на листе бумаги, то удобно расставлять знаки "больше" в соответствующих местах.

В первую очередь ясно, что A — абсолютно лучшая лошадь всего турнира, но с этим пока делать нечего.
Рассмотрим, например, лошадь D. Лучше нее лошади A, B, C. Значит, она не в тройке! Все лошади в ее столбце медленнее ее. То же верно и для лошадей в столбце E. То есть правые два столбца можно не рассматривать. Немного подумав, не рассматриваем и две нижние строки, оставляя табличку 3х3:

ABC
FGH
KLM
Рассмотрим теперь лошадь H — в одном из первых 5 забегов мы узнали, что C — быстрее ее, тогда как A и B — быстрее С. Значит, H — тоже не в тройке. Аналогичными рассуждениями отбросим L и M.

ABC
FG
K
Осталось шесть лошадей, из которых одна — достоверно самая быстрая. Проводим седьмой забег среди остальных лошадей B, C, F, G, K. Две лучших из них, очевидно, занимают, соответственно, вторую и третью строки общего рейтинга.

Ответ: семь забегов.

P.S. Любопытно, обобщается ли задача на случай N лошадей, при условии, что в один забег можно ставить не более k лошадей, и нам требуется найти p лучших? Для начала попробую рассмотреть случай p<k, k^2=N.

7
разбиты на 5 групп по 5: А,В,С,К,Т.. Проводятся 5 заездов. Так как ищем троих лучших, то занявших четвертые и пятые места можно исключить. Осталось 15 претендентов. Победители проводят 6-ой забег .Пусть первая тройка из забегов А, В,и С, У А точно первое место.Осталось определить второе и третье.Значит можно исключить всех лошадей из К и Т.Осталось пока 9: по три из А,В и С. Но! Из А надо оставить вторую и третью, из В первую и вторую участницу, из С только первую( так как вторая может быть только четвёртой). То есть осталось 5 лошадей для определения второго и третьего места. ?-ой забег: первая в нём становится второй в общем зачёте, вторая становится третьей. Финиш.

Получается за 7 заездов можно не только определить трёх сильнейших, но и точно сказать кто первый, кто второй и кто третий

Интересней решить для 28 лошадей