Наверно уже пора написать решение задачи от [id463377|Дениса Пешехонова]
Опишу подход, который дает возможность справиться с этой задачей за 7 заездов.
Первый шаг практически все сделали верно: надо просто случайным образом разбить лошадей на пятерки и просоревновать.
Из каждой пятерки можно сразу исключить по паре самых нерезвых, это оставит 15 претендентов на попадание в тройку (ведь есть ненулевая вероятность, что все самые быстрые лошади оказались в одном заезде).
Шестым заездом, как снова предлагали 90% из присылавших решение, надо погнать победитетей первых пяти. Не просто же так их пятеро.
А вот дальше уже не все справились с интерпретацией результатов этого заезда.
Какую информацию мы из него получим:
-Лошадь пришедшую пятой можно из претендентов исключить, причем вместе с вторым и третьим призерами из её первого заезда - осталось 12 лошадей.
- То же самое можно сделать с лошадью, занявшей четвертое место. И с двумя ее конкурентами из ее первого заезда. - останется 9 лошадей.
-Лошадь, пришедшую третьей, исключить нельзя, зато можно исключить второго и третьего призера из ее зазда - они точно в тройку не попадают - остается 7 лошадей.
- Лошадь, пришедшую второй, конечно, тоже нельзя исключать. И второго призера из ее заезда тоже нельзя - он все еще может быть третьей по скорости лошадью из всех. А вот третьего призера из ее первого заезда можно, потому что как минимум три лошади впереди неё уже есть - это оставляет нас лицом к лицу (к мордам) с 6 претендентами на 3 места самых быстрых лошадей.
Наверно вы уже поняли, куда все идет. Победитель забега победителей - самый быстрый и крутой. Про него мы уже все знаем.
Остается пять других лошадей, которым придется устроить заезд, и мы можем себе это позволить. Две лучших лошади седьмого заезда получат второй и третий мандат самых быстрых лошадей соотвественно.
К сожалению, мы не знаем, как доказать, что быстрее предлагаемого решения отобрать трех самых быстрых лошадей нельзя. Более того: мы не знаем, является ли это решение единственным, позволяющим решить поставленную задачу за семь заездов. Способа сделать это быстрее, чем за семь заездов, мы тоже не знаем. Вот такие вот мы.
#zoda4a
Опишу подход, который дает возможность справиться с этой задачей за 7 заездов.
Первый шаг практически все сделали верно: надо просто случайным образом разбить лошадей на пятерки и просоревновать.
Из каждой пятерки можно сразу исключить по паре самых нерезвых, это оставит 15 претендентов на попадание в тройку (ведь есть ненулевая вероятность, что все самые быстрые лошади оказались в одном заезде).
Шестым заездом, как снова предлагали 90% из присылавших решение, надо погнать победитетей первых пяти. Не просто же так их пятеро.
А вот дальше уже не все справились с интерпретацией результатов этого заезда.
Какую информацию мы из него получим:
-Лошадь пришедшую пятой можно из претендентов исключить, причем вместе с вторым и третьим призерами из её первого заезда - осталось 12 лошадей.
- То же самое можно сделать с лошадью, занявшей четвертое место. И с двумя ее конкурентами из ее первого заезда. - останется 9 лошадей.
-Лошадь, пришедшую третьей, исключить нельзя, зато можно исключить второго и третьего призера из ее зазда - они точно в тройку не попадают - остается 7 лошадей.
- Лошадь, пришедшую второй, конечно, тоже нельзя исключать. И второго призера из ее заезда тоже нельзя - он все еще может быть третьей по скорости лошадью из всех. А вот третьего призера из ее первого заезда можно, потому что как минимум три лошади впереди неё уже есть - это оставляет нас лицом к лицу (к мордам) с 6 претендентами на 3 места самых быстрых лошадей.
Наверно вы уже поняли, куда все идет. Победитель забега победителей - самый быстрый и крутой. Про него мы уже все знаем.
Остается пять других лошадей, которым придется устроить заезд, и мы можем себе это позволить. Две лучших лошади седьмого заезда получат второй и третий мандат самых быстрых лошадей соотвественно.
К сожалению, мы не знаем, как доказать, что быстрее предлагаемого решения отобрать трех самых быстрых лошадей нельзя. Более того: мы не знаем, является ли это решение единственным, позволяющим решить поставленную задачу за семь заездов. Способа сделать это быстрее, чем за семь заездов, мы тоже не знаем. Вот такие вот мы.
#zoda4a
Probably it is time to write a solution to the problem from [id463377 | Denis Peshekhonov]
I will describe an approach that makes it possible to cope with this task in 7 races.
The first step was practically done right: you just need to randomly split horses into fives and compete.
From each five, you can immediately exclude a pair of the most not sober, it will leave 15 applicants for getting into the top three (after all, there is a non-zero probability that all the fastest horses ended up in the same race).
With the sixth heat, as 90% of those who sent the decision were again offered, it is necessary to chase the winners of the first five. Not just as five of them.
But then not all have coped with the interpretation of the results of this race.
What information will we get from it:
-The horse that came in fifth can be excluded from the applicants, and along with the second and third winners from her first race - 12 horses left.
- The same can be done with the horse that finished fourth. And with her two competitors from her first race. - 9 horses will remain.
- A third horse cannot be excluded, but the second and third prize-winners can be excluded from their arrival - they don’t get into the top three - 7 horses remain.
- The horse that came second, of course, also can not be excluded. And the second prize-winner from her arrival is also impossible - he can still be the third fastest horse of all. But the third prize-winner from her first race is possible, because at least three horses in front of her are already there - this leaves us face to face (with muzzles) with 6 applicants for 3 places of the fastest horses.
I guess you already understand where everything goes. The winner of the race winners - the fastest and coolest. We already know everything about him.
There are five other horses that will have to arrange a race, and we can afford it. The two best horses of the seventh race will receive the second and third mandate of the fastest horses, respectively.
Unfortunately, we do not know how to prove that it is impossible to select the three fastest horses faster than the proposed solution. Moreover: we do not know whether this solution is the only one that allows solving the set task in seven races. The way to do it faster than seven races, we also do not know. Here we are.
# zoda4a
I will describe an approach that makes it possible to cope with this task in 7 races.
The first step was practically done right: you just need to randomly split horses into fives and compete.
From each five, you can immediately exclude a pair of the most not sober, it will leave 15 applicants for getting into the top three (after all, there is a non-zero probability that all the fastest horses ended up in the same race).
With the sixth heat, as 90% of those who sent the decision were again offered, it is necessary to chase the winners of the first five. Not just as five of them.
But then not all have coped with the interpretation of the results of this race.
What information will we get from it:
-The horse that came in fifth can be excluded from the applicants, and along with the second and third winners from her first race - 12 horses left.
- The same can be done with the horse that finished fourth. And with her two competitors from her first race. - 9 horses will remain.
- A third horse cannot be excluded, but the second and third prize-winners can be excluded from their arrival - they don’t get into the top three - 7 horses remain.
- The horse that came second, of course, also can not be excluded. And the second prize-winner from her arrival is also impossible - he can still be the third fastest horse of all. But the third prize-winner from her first race is possible, because at least three horses in front of her are already there - this leaves us face to face (with muzzles) with 6 applicants for 3 places of the fastest horses.
I guess you already understand where everything goes. The winner of the race winners - the fastest and coolest. We already know everything about him.
There are five other horses that will have to arrange a race, and we can afford it. The two best horses of the seventh race will receive the second and third mandate of the fastest horses, respectively.
Unfortunately, we do not know how to prove that it is impossible to select the three fastest horses faster than the proposed solution. Moreover: we do not know whether this solution is the only one that allows solving the set task in seven races. The way to do it faster than seven races, we also do not know. Here we are.
# zoda4a
У записи 15 лайков,
0 репостов,
913 просмотров.
0 репостов,
913 просмотров.
Эту запись оставил(а) на своей стене Андрей Городецкий
