5
1

Из 30 скакунов нужно выбрать трех самых быстрых. Более быстрый скакун в забеге приходит к финишу раньше. Отношение более быстрый транзитивно. В одном забеге могут участвовать 5 скакунов.

Какое минимальное количество забегов нужно провести?

P.S. Простая, по-моему, задача, но вызывает затруднения.

задан 9 Дек '19 21:47

1

Я встречал ту же задачу про 25 лошадей. Там, по-моему, 7 заездов нужно.

(10 Дек '19 3:17) falcao
2

Я давал еще более простую про боксеров. Выбрать 2-х лучших. Тоже трудно шла.

(10 Дек '19 3:38) FEBUS
1

@FEBUS: про выбор двух лучших, вроде бы, на форуме была задача.

(10 Дек '19 9:25) falcao

Мне непонятно,что значит минимальное число забегов.Какой ответ будет,если требуется упорядочить скакунов (по скорости) ,а всего их 3 , и в каждом забеге участвуют два скакуна? Самый минимум - 2 забега,не ?

(12 Дек '19 14:36) panda201
1

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

(12 Дек '19 15:22) spades

@panda201: Нет, конечно. @spades прав.

(12 Дек '19 15:22) FEBUS

А в общем виде решить возможно ? Если всего скакунов $%n$%, а остальные условия те же ?

(12 Дек '19 19:03) lawyer
1

@lawyer: пока что даже для частного случая идею решения никто не изложил.

(12 Дек '19 19:15) falcao

@falcao Я не заметил: имел ввиду условия @panda201 - в каждом забеге два скакуна

(12 Дек '19 19:47) lawyer

@spades Понятно,спасибо.

@lawyer Я нашел в интернете такую формулу(для 2 скакунов в забеге): $%n + 3$%[$%\log_2 n$%]$% - 5$%

(12 Дек '19 23:13) panda201

@falcao: Неужели вы не решили? даже для 25?

(13 Дек '19 0:01) FEBUS

@FEBUS: для 25, наверное, можно доказать, что 6 забегов мало, но у меня получается как-то слишком "кустарно". А для 30 у меня нет идей.

(13 Дек '19 1:48) falcao
показано 5 из 12 показать еще 7
10|600 символов нужно символов осталось
6

Для начала решим задачу для 25 лошадей. Проводим 5 забегов (предварительный этап) и шестой (финал) для победителей этих забегов . В седьмой забег попадают 2 лошади из предварительного забега, где участвовал победитель финала, второй призер финала и лошадь, участвовавшая с ней в предварительном забеге, а также третий призер финала. Первые две лошади седьмого забега и становятся на второе и третье место.
Добавим теперь еще 5 лошадей.
Выберем группу А из 25 лошадей. Отбираем за 7 забегов первую тройку этой группы, причем упорядоченную. Далее, берем вице-чемпиона А и к ней отправим 4 лошади из оставшейся пятерки.
Если вице-чемпион занимает первое или второе место, то проводим забег из трех победителей 8 забега, оставшейся лошади и третьей призера группы А. Лучшая двойка отправится к победителю группы А.
Если вице-чемпион не попадает в тройку, то три победителя 8 забега, оставшейся лошади и победителя группы А разыгрывают три места.
Если вице-чемпион занимает третье место, то в последнем забеге участвуют 2 победителя 8 забега, чемпион группы А и 30-я лошадь.
Итого 9 забегов. Интуитивно понятно, что меньше нельзя, осталось подумать, как доказать строго.

ссылка

отвечен 10 Дек '19 18:14

изменен 10 Дек '19 18:21

Можно и так. Я делал по-другому.

(10 Дек '19 22:09) FEBUS

@FEBUS, ваше решение позволяет за 9 забегов выделить не только первую тройку, но и упорядочить ее?

(11 Дек '19 22:45) spades

@spades: Да. И доказать, что меньше нельзя.

(12 Дек '19 0:47) FEBUS

Это тоже просто доказывается - см. подсказки к задаче

(12 Дек '19 4:21) Urt

@Urt: я совсем забыл про то, что у Вас была задача о лошадях. Наверное, потому, что решения я не знал, и до сих пор не знаю. Может, расскажет кто, как тут оптимальность обосновывать?

(12 Дек '19 10:11) falcao
1

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

(12 Дек '19 10:57) spades

@spades, да, в таком виде она неверна. Там что-то подразумевалось дополнительно (типа "если существует, то существует") - удалил. Спасибо.

(12 Дек '19 12:24) Urt
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,018
×547
×501
×284

задан
9 Дек '19 21:47

показан
616 раз

обновлен
13 Дек '19 1:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru