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

[Иван Горин]

Задача с форума scitec
На бегах учавствуют 25 лошадей. Необходимо определить трех самых быстрых. Часов нет.
Забеги только по 5 лошадей.
Какое минимальное количество забегов необходимо.

[sergey_B_K]

И этим Сайтех мается? Полная деградация форума.
Шесть забегов - это минимум. Если с учётом вторых номеров в каждом из первых забегов, то семь.
В седьмом бегут
2 место у 1-го места в первом забеге
2 место во втором забеге
2 место по первому забегу у 2-го по второму забегу
3 во втором забеге
2 место по первому забегу у 3-го по второму забегу.
Выходят
1 место во втором забеге и два первых в третьем забеге.
Первых забегов пять (считается первым забегом).

[sergey_B_K]

Второй вариант
В седьмом бегут
2 и 3 место у 1-го места в первом забеге
2 место во втором забеге
2 место по первому забегу у 2-го по второму забегу
3 во втором забеге
2 место по первому забегу у 3-го по второму забегу.
Выходят
1 место во втором забеге и два первых в третьем забеге.

[Alexpo]

И этим Сайтех мается? Полная деградация форума.

Задача, на самом деле, неплоха.

Шесть забегов - это минимум. Если с учётом вторых номеров

Что значит "Если с учётом вторых номеров"?
Вы в решении должны учесть любой возможный вариант без всяких "если" и минимумов.

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

Надо учесть, что возможен вариант, что все 3 бегут в одном из первых забегов.

Во втором варианте, похоже вы нашли правильный ответ, поскольку у меня получилось похоже. Только вы всё запутываете своей нумерацией. Называли бы первые 5 забегов - первым этапом, проще было бы.

Сначала 5 забегов - 1-й этап.
6-й забег - бегут первые места всех забегов и определяют тройку лучших Л1, Л2 и Л3. Л1- однозначно первая в искомой тройке
7-й забег, бегут:

2 и 3 лошали из группы Л1 на первом этапе,
Л2, и 2- лошадь из её группы на первом этапе
Л3

Ответ: Л1 и две лучших из 7-го забега

[Иван Горин]

Задача, на самом деле, неплоха.

ДА, задача не простая, как кажется.
На sciteclibrary ее пока не решили. Может быть мы на БФ ее решим.
Не надо забывать, что в первых пяти забегах по пять лошадей, в одних из пятерок могут быть три самых быстрых, две или одна.
И чтобы выяснить трех самых быстрых необходимо найти минимальное количесто забегов.
Можно и сходу найти, если всех запустить сразу.
Но в условии задачи - один забег только по пять лошадей. Ни больше ни меньше. И нет часов.

[Alexpo]

ДА, задача не простая, как кажется.
На sciteclibrary ее пока не решили. Может быть мы на БФ ее решим.
Не надо забывать, что в первых пяти забегах по пять лошадей, в одних из пятерок могут быть три самых быстрых, две или одна.
И чтобы выяснить трех самых быстрых необходимо найти минимальное количесто забегов.
Можно и сходу найти, если всех запустить сразу.
Но в условии задачи - один забег только по пять лошадей. Ни больше ни меньше. И нет часов.

Так мы уже решили. В соответствии с условием. Вы что не стали читать?
Минимальное число забегов - 7.

[sergey_B_K]

ДА, задача не простая, как кажется.
На sciteclibrary ее пока не решили. Может быть мы на БФ ее решим.
Не надо забывать, что в первых пяти забегах по пять лошадей, в одних из пятерок могут быть три самых быстрых, две или одна.
И чтобы выяснить трех самых быстрых необходимо найти минимальное количесто забегов.
Можно и сходу найти, если всех запустить сразу.
Но в условии задачи - один забег только по пять лошадей. Ни больше ни меньше. И нет часов.

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

[Иван Горин]

Так мы уже решили. В соответствии с условием. Вы что не стали читать?
Минимальное число забегов - 7.

У вас правильное решение.

[Иван Горин]

Задача, на самом деле, неплоха.

Что значит "Если с учётом вторых номеров"?
Вы в решении должны учесть любой возможный вариант без всяких "если" и минимумов.

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

Надо учесть, что возможен вариант, что все 3 бегут в одном из первых забегов.

Во втором варианте, похоже вы нашли правильный ответ, поскольку у меня получилось похоже. Только вы всё запутываете своей нумерацией. Называли бы первые 5 забегов - первым этапом, проще было бы.

Сначала 5 забегов - 1-й этап.
6-й забег - бегут первые места всех забегов и определяют тройку лучших Л1, Л2 и Л3. Л1- однозначно первая в искомой тройке
7-й забег, бегут:

2 и 3 лошали из группы Л1 на первом этапе,
Л2, и 2- лошадь из её группы на первом этапе
Л3

Ответ: Л1 и две лучших из 7-го забега

На scitec есть правильное решение у пользователя GRAF.
И тоже все четко расписано, как и у вас.

[sergey_B_K]

На scitec есть правильное решение у пользователя GRAF.
И тоже все четко расписано, как и у вас.

Ну, вот... Усложним задачу. Нужно выделить первые пять мест... Теперь без моего решения, плз... 

[Иван Горин]

Ну, вот... Усложним задачу. Нужно выделить первые пять мест... Теперь без моего решения, плз... 

Минимум 10 забегов.

[sergey_B_K]

Минимум 10 забегов.

И основания для такого решения? 

[Иван Горин]

И основания для такого решения? 

Такой же алгоритм Алекспо и Графа, как и для трех первых мест.

[sergey_B_K]

Такой же алгоритм Алекспо и Графа, как и для трех первых мест.

Такой же не пойдёт... Если бы было так, как Вы говорите, Алекспо с Графом давно уже описали бы его...   

[Иван Горин]

Такой же не пойдёт... Если бы было так, как Вы говорите, Алекспо с Графом давно уже описали бы его...   

Моя задача была для трех первых мест.
Алекспо эту задачу решил. И Граф на scitec тоже решил.
А сколько забегов необходимо, чтобы определить 5 мест, это уже ваша задача. Кому интересно пусть решают.

[sergey_B_K]

Моя задача была для трех первых мест.
Алекспо эту задачу решил. И Граф на scitec тоже решил.
А сколько забегов необходимо, чтобы определить 5 мест, это уже ваша задача. Кому интересно пусть решают.

Вот и момент истины, Иван... А меня в Вашем списке первой задачи нет, хотя мой пост первый. Конечно, всякой гадости придумаете, как и с ЭД, но факт остаётся фактом и дальше меня вы не продвинетесь. Потому и так, как бы вас ни корёжило от меня...

[Alexpo]

Такой же не пойдёт... Если бы было так, как Вы говорите, Алекспо с Графом давно уже описали бы его...   

У меня сразу получилось 13 забегов.
Просто ищу способ уменьшить их число. В конце мешает требование, делать забег по 5 лошадей.

Для 13 могу привести решение
1) 5 забегов
2) 6-й забег - бегут первые места всех забегов
Расставляем лошадей как матрицу L_ij
i - забег из первых пяти, j - номер в забеге.
Столбцы ставятся в порядке, заданным 6-м забегом т.е. L₁₁ - самая быстрая, L₅₁ - самая медленная среди первых
11 - опять самая быстрая из всех - входит в искомую пятёрку, осталось найти 4 лошади

отсеиваем лошади ниже диагонали 15-51
это аналогично задаче для трёх первых. А дальше по другому

3)7-й забег бегут лошади  диагонали 15-51 из них только первая может быть среди искомых, остальные отбрасываем.

теперь остаётся 10 лошадей, среди которых надо найти 4.

4) 8, 9 забеги - отбрасываем последние (5-е) - остаётся 8.

5) 10-13 забеги - добавляем по одной лошади  из второй четвёрки в первую, и каждый раз отбрасываем 5-ю

Первые 4 лошади в 13 забеге - искомые.

[sergey_B_K]

Для 13 могу привести решение
3)7-й забег бегут лошади  диагонали 15-51 из них только первая может быть среди искомых, остальные отбрасываем.

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

[Alexpo]

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

Получится.

[Иван Горин]

У меня нумерация лошадей сквозная.
Первый тур. Пять забегов по 5 лошадей.
1 забег 01 02 03 04 05
2 забег 06 07 08 09 10
3 забег 11 12 13 14 15
4 забег 16 17 18 19 20
5 забег 21 22 23 24 25
Это таблица 1

 6 забег из первых в первом туре
Это лошади 01 06 11 16 21
Пусть лошади шестого забега пришли в том же порядке
Перепишем табл. 1

01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
Это таблица 2.

Красным цветом в строках обозначены лошади в порядке сверху вниз, как они пришли в шестом заезде.
В строках стоят номера лошадей, как они пришли в первом туре заездов.

Определим первые три места.
Имеем четыре варианта из табл.2

1 вариант
01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25


Красный цвет 1 место
зелёный второе
желтый третье.

2 вариант
01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25



3 вариант
01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25



4-й вариант
01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25



Совмещаем варианты таблиц и получаем, что в седьмом забеге должны учавствовать 5 лошадей 2, 3, 6,7 и 11 для распределения второго и третьего мест.

Для определения четвертого и пятого мест необходимо по крайней мере ещё два забега.

Уже из анализа нахождения трёх первых мест очевидно,что использование нижней диоганали без необходимости.
И в дальнейшем рисуем таблицы только с верхней диагональю.
1 вариант
01 02 03 04 05
06 07 08 09
11 12 13
16 17
21   


Эта задача на минимизацию и излишняя информация нам ни к чему.
Лошади, которые ниже главной диоганали не имеют шансов на вторые, третьи и дальнейшие места.

Для анализа четвёртого  и пятого мест выбираем вариант
4-й вариант
01 02 03 04 05
06 07 08 09
11 12 13
16 17
21



Места 1 -3 исключаем
Остаются лошади
02 03
07 08
12 13
16 17
21

Эти лошади - претенденты на 4 и 5 места.
8-й забег 02  07 12 16 21 претенденты на 4-е место
Пусть первой пришла лошадь 12.

Остаются лошади- претенденты на 5-е место
02
07
13
16
21
из этого 9-го забега - первая получает пятое место.


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