В вашем распоряжении ипподром с пятью дорожками, а также 25 лошадей, каждая из которых может пробежать круг за определённое время (время круга у всех лошадей различается). К сожалению, у Вас нет секундомера, поэтому Вы можете только устраивать забеги из пяти участников и смотреть, в каком порядке они придут финишу.
За какое минимальное число забегов можно определить тройку призёров, т.е. три лошади, которые пробегают дистанцию быстрее остальных?
Решение
Выявить тройку призёров можно за 7 забегов.
Пронумеруем лошадей от 1 до 25. Проведём пять забегов для лошадей #1..#5, #6..#10, ... , #21..#25. Не ограничивая общности рассуждений, будем считать, что в своих забегах лошади приходили в порядке номеров, т.е. лошадь #1 выиграла первый забег, #6 - второй и так далее.
В шестом забеге будут участвовать победители первых пяти забегов, т.е. лошади #1, #6, #11, #16 и #21. Снова для простоты обозначений будем полагать, что лошади приходили к финишу в порядке возрастания номеров. Тогда лошадь #1 будет, очевидно, чемпионом.
Для того чтобы определить тройку призёров, потребуется седьмой забег. В нём будут принимать участие лошади #6 и #11 (т.е. второе и третье место шестого забега), лошади #2 и #3 (т.е. второе и третье места из первого забега чемпиона), а также лошадь #7 (т.е. второе место из первого забега лошади, пришедшей второй в шестом забеге). Лошадь, выигравшая седьмой забег становится вторым призёром, а лошадь, пришедшая второй - третьим призёром.
За какое минимальное число забегов можно определить тройку призёров, т.е. три лошади, которые пробегают дистанцию быстрее остальных?
Решение
Выявить тройку призёров можно за 7 забегов.
Пронумеруем лошадей от 1 до 25. Проведём пять забегов для лошадей #1..#5, #6..#10, ... , #21..#25. Не ограничивая общности рассуждений, будем считать, что в своих забегах лошади приходили в порядке номеров, т.е. лошадь #1 выиграла первый забег, #6 - второй и так далее.
В шестом забеге будут участвовать победители первых пяти забегов, т.е. лошади #1, #6, #11, #16 и #21. Снова для простоты обозначений будем полагать, что лошади приходили к финишу в порядке возрастания номеров. Тогда лошадь #1 будет, очевидно, чемпионом.
Для того чтобы определить тройку призёров, потребуется седьмой забег. В нём будут принимать участие лошади #6 и #11 (т.е. второе и третье место шестого забега), лошади #2 и #3 (т.е. второе и третье места из первого забега чемпиона), а также лошадь #7 (т.е. второе место из первого забега лошади, пришедшей второй в шестом забеге). Лошадь, выигравшая седьмой забег становится вторым призёром, а лошадь, пришедшая второй - третьим призёром.
Этот комментарий был удален автором.
ОтветитьУдалитьМожет оказаться так что лошадь пришедшая второй из первого забега, быстрее лошади пришедшей первой из второго забега
ОтветитьУдалитьЭто так. Именно поэтому и нужен седьмой забег, в котором эти две лошади побегут вместе. В наших обозначениях это лошади #2 и #6.
ОтветитьУдалитья думаю что можно за 4 забега. но здесь нужно немножко по другому организовать забеги.
ОтветитьУдалитьу нас есть ипподром (круглая) с пятью дорожками, мы можем разделит как бы на две части. старт лини будут 2, напротив друг друга, дистанция достаточно (половина ипподрома) и 2 группы не будут мешать друг друга. за один забег можно использовать сразу 10 лошадей. 5 с одной стороны а 5 с противоположной стороны. мы можем стоят в центре ипподрома и посмотреть кто из 10 лошадей пришел к лини старта первыми 3.
за две забега можно взят 6 лошадей из 20-и, можно еще забег для того чтобы определит 3 из остальных 5.
у нас есть уже 9 лошадей и надо определит 3. на этот раз с одной стороны будут 5 с другой 4, и за одного забега у нас первые 3 будут победителями...
Решение неверное. Не доказано, что это минимум.
ОтветитьУдалить