Задачка про 25 лошадей

Задела меня простенькая задачка про 25 лошадей участвующих в скачках. Предлагаю увидеть решение и ответ подкатом.
Условие задачи: в скачках участвуют 25 лошадей. В одной скачке может участвовать максимум 5. Условие ограничено тем, что любая выбранная лошадь X в любом забеге скачет с одинаковой скоростью. Время и скорость лошадей засекать нельзя, можно лишь сравнить кто быстрее или медленнее (Vx Найти: минимальное количество забегов, после которых определиться тройка призеров, т.е. 1-е, 2-е и 3-е место среди всех 25 лошадей. Ответ: 7 забегов! Нарисуем пять груп, с номерами лошадей по-порядку: Проведем 5 забегов в пяти группах. На рисунке это 1, 6, 11, 16, 21 лошадь. Для простоты отображения будем считать что лошади на рисунке расположены по убыванию их скоростей после забегов. Почему мы исключили 4-ю и 5-ю группу? Потому что если призеры этих групп оказались медленнее 3-го места в общем зачете, то остальные и подавно! Теперь разберем почему мы исключили номер 12-й и ниже следующие за ним номера. Если 12-й номер медленнее 11, то он никак не может быть в тройке призеров, а тем более номера ниже. Пойдем дальше. Почему мы оставили в «потенциальных» 7 номер? Потому что он может претендовать на 3-е место в общем зачете! Мы же не знаем наверняка, что он медленнее 11-го номера, они никогда в одной группе не участвовали. Почему же мы исключили 8-й номер? Потому, что претендент на 3-е место в общем зачете может быть только один. С первой группой проводим аналогичные рассуждения. Мы оставили номера 2 и 3, потому как они являются потенциальными претендентами на 2 и 3-е место в общем зачете. И последний 7-й забег. Выставляем в него все потенциальные номера обозначенные красным (2, 3, 6, 7, 11), кроме 1-го, выявляя таким образом 2 и 3-е место в общем зачете. 1-е место абсолютного чемпиона было выявлено еще в 6-й скачке. Решение получилось «в лоб» так сказать. Если у кого появится строгая математическая модель было бы интересно посмотреть. Каким минимальным числом заездов из 25 лошадей можно выбрать 3 самых быстрых? В каждом заезде может участвовать не больше 5 лошадей. Условия заезда каждый раз разные, поэтому сравнивать абсолютное время, за которое каждая лошадь прошла дистанцию, нельзя — можно сравнивать только относительно друг друга, кто кого победил, кто кому проиграл. Но относительная скорость — стабильна, так что если лошадь А быстрее лошади Б, то в любом соревновании А опередит Б. Задачи :: Лошадиные бега 1. Очевидно, минимальное число заездов N>5, так как увидеть каждую из 25 лошадей в деле невозможно менее чем при пяти забегах, при условии, что в забеге участвует максимум 5 лошадей. А гарантированное определение трёх лучших очевидно требует ещё 2. Если более быстрая лошадь всегда победит более медленную, значит лошадь побеждающая другую лошадь гарантировано победит всех ею побеждённых. 3. Исходя из предыдущего пункта можно с уверенностью сказать, что кратчайший способ определить лучших лошадей — сравнивать лошадей победивших множество других лошадей. Значит, турнир должен пройти в несколько туров. 4. Не факт, что лошадь B побеждённая в туре 1 лошадью A, проиграет лошади С из другой пятёрки проигравшей лошади А во втором туре. Ведь две самых быстрых лошади могут попасть в первом туре. 5. Значит, сравнивать лошадей, проигравших в каком-либо из туров, с любыми другими лошадями до определения самой быстрой из всех, в большинстве случаев лишь добавит число забегов. Ведь не зная самой быстрой, нам придётся, например, сравнивать каждую из пришедших второй с каждой, которая пришла первой в любом другом забеге того же тура. 6. Из пункта №5 следует, что кратчайший путь решения задачи — решение через определение быстрейшей лошади. Чего нельзя добиться менее чем за 6 забегов. Пять отборочных и шестой забег победителей. Следовательно, N>6. ↓↓ 0 ↑↑ Гидон (0 / 19) 2016-04-08 15:47 «« #9 »» Ответить Мне кажется, что здесь надо идти от обратного и просто убирать самых медленных. ↓↓ 0 ↑↑ Михаил Михайлов (0 / 5) 2016-09-10 16:35 «« #11 »» Ответить Я проиллюстрирую ответ Гидона выше, потому что согласен с ним, но он слишком затуманил свой ответ. 1. Проводим 5 заездов, каждый раз с новой пятеркой. Теперь составляем квадратную таблицу 5х5: в первую строку выпишем участников 6-го заезда слева направо по убыванию результата: ABCDE В первую очередь ясно, что A — абсолютно лучшая лошадь всего турнира, но с этим пока делать нечего. ABC ABC Есть 25 лошадей, надо определить 3 самых быстрых если собираетесь решать через группировку по группам (25/5) попробуйте решить сгруппировав всех самых быстрых лошадей в одну группу 1 комментарий Простой 1 комментарий Те лошади, коорые в каждом забеге заняли 4-е и 5-е места — явно не призовые, их можно снимать с соревнований. Теперь устроим шестой забег среди призёров каждой пятёрки. Те лошади, которые заняли в шестом забеге 4-е и 5-е место — явно не призовые. И все их пятёрки — тоже не призовые, ибо ещё хуже. Значит, их всех можно снимать с соревнований. Дальше я как-то не соображу — тут проще читать ссылку, которую дал Сергей Соколов. Но я надеюсь, я разъяснил решение задачи — особенно важным педагогически я вижу список вариантов в начале ответа. Решения вопроса 1 [неправильное решение сходу] Задача отбросить 22 лошади. За один забег из 5 отбрасываются 2 самые медленные. Хотя в решении под спойлером говорят, можно за 7 интересно -) art style, не, он дело говорит ) Классный чел, кстати. Сергей Соколов, чел то классный. но вот в его задаче проблема. он их «сортирует» без таймера это невозможно. т.к. мы не можем определить время за которое бегут лошади. и он отсеивает в первой группе сразу двух. а что если в эту группу попало 5 самых быстрых ? art style, art style @arttstyle Автор вопроса 1. допустим. это самый быстрый в конкретной группе из рандомных лошадей. там могут бежать лошади как и за 1 сек так и 10сек. art style, 1-й из топа – в любом случае быстрее вообще всех. Остаётся найти 2-е и 3-е места. art style @arttstyle Автор вопроса Сергей Соколов, мы не можем определить самого первого топа потому что нет таймера. мы лишь получили 15 победителей в 5 группах из рандомных лошадей. art style @arttstyle Автор вопроса Сергей Соколов, мне кажется в задаче вся загвоздка в таймере. его нет. поэтому мы можем только визуально определять победителей 1.2.3 но не сравнивать их между собой Условие задачи: в скачках участвуют 25 лошадей. В одной скачке может участвовать максимум 5 лошадей. Условие ограничено тем, что любая выбранная лошадь X в любом забеге скачет с одинаковой скоростью. Время и скорость лошадей засекать нельзя, можно лишь сравнить кто быстрее или медленнее (Vx Найти: минимальное количество забегов, после которых определиться тройка призеров, т.е. 1-е, 2-е и 3-е место среди всех 25 лошадей. Итак, для начала разделим всех лошадей на 5 групп по 5 лошадей, и проведем забеги в каждой группе. Получится 5 забегов. В 6-ом забеге пускаем всех, кто победил в своем забеге. Таким образом мы определили лидера забега, это лошадь с номером 1, второе место лошадь с номером 6 и третье место лошадь с номером 11. Итак, теперь нарисуем картинку, чтобы показать как правильно выбрать лошадей для 7-го забега. Итак, у нас получаются лидеры на 2 и 3 место, условно возьмем, чтобы было проще, что это номера — 2, 3, 6, 7, 11 (выделены фиолетовым цветом). Мы уже определили в 6-м забеге, что 1-й номер лидер, поэтому он нам не нужен для следующего забега. Почему мы исключили 4-ю и 5-ю группу? Потому что, если призеры этих групп оказались медленнее 3-го места в общем зачете (это номер 11), то остальные и подавно! Теперь разберем почему мы исключили номер 12-й и ниже следующие за ним номера. Потому, что 11-й номер сейчас борется за 3 место, а если 12-й медленнее, то ему и остальным из этой группы нечего делать в этом забеге. Тоже самое и с номерами 8, 9, 10, мы убрали их, так как номера 2 и 3 сражаются за 2 и 3 место. Таким образом получается, что в 7 забеге у нас борются за 2 и 3 место лошади с номерами 2, 3, 6, 7, 11. Ответ: чтобы узнать какие 3 лошади самые быстрые из 25 лошадей, при условии, что в одной скачке может участвовать максимум 5 лошадей. Условие ограничено тем, что любая выбранная лошадь X в любом забеге скачет с одинаковой скоростью. Время и скорость лошадей засекать нельзя, можно лишь сравнить кто быстрее или медленнее, потребуется 7 забегов.
В следующем забеге ставим лошадей, победивших в своей группе.
Итого мы провели уже 6-й забег.
Нарисуем последнюю картинку и разберем ее: 100. Лошадиные бега
Обсуждение
↓↓ 0 ↑↑ eruditor.ru (118 / 229) 2015-10-25 15:15 »»
↓↓ −5 ↑↑ Gelon (-10 / 2) 2015-11-30 18:49 «« #2 »» Ответить
↓↓ −5 ↑↑ Gelon (-10 / 2) 2015-11-30 18:50 «« #3 »» Ответить
↓↓ 0 ↑↑ Сергей (0 / 3) 2016-01-24 03:07 «« #4 »» Ответить
↓↓ +5 ↑↑ Сергей (0 / 3) 2016-01-24 03:40 «« #5 »» Ответить
↓↓ 0 ↑↑ Вова (0 / 1) 2016-02-27 20:45 «« #8 »» Ответить
↓↓ 0 ↑↑ костя (0 / 4) 2016-02-21 12:10 «« #6 »» Ответить
↓↓ 0 ↑↑ костя (0 / 4) 2016-02-21 14:21 «« #7 »» Ответить
большего числа заездов.
↓↓ 0 ↑↑ Роман (0 / 1) 2016-09-08 10:07 «« #10 »» Ответить
2. Проводим 6-й заезд, в котором участвую только победители первых пяти.
Под каждым из них запишем участников первых пяти забегов, в которых участвовал «житель» данного столбца, по убыванию сверху вниз.
Получаем:
ABCDE
FGHIJ
KLMNO
PQRST
UVWXY
Можно представлять себе, что под буквами скрываются различные числа, и в первой строке они расположены по убыванию, как и в любом столбце, а по другим строкам и тем более диагоналям информации нет. Если писать это на листе бумаги, то удобно расставлять знаки «больше» в соответствующих местах.
Рассмотрим, например, лошадь D. Лучше нее лошади A, B, C. Значит, она не в тройке! Все лошади в ее столбце медленнее ее. То же верно и для лошадей в столбце E. То есть правые два столбца можно не рассматривать. Немного подумав, не рассматриваем и две нижние строки, оставляя табличку 3х3:
FGH
KLM
Рассмотрим теперь лошадь H — в одном из первых 5 забегов мы узнали, что C — быстрее ее, тогда как A и B — быстрее С. Значит, H — тоже не в тройке. Аналогичными рассуждениями отбросим L и M.
FG
K
Осталось шесть лошадей, из которых одна — достоверно самая быстрая. Проводим седьмой забег среди остальных лошадей B, C, F, G, K. Две лучших из них, очевидно, занимают, соответственно, вторую и третью строки общего рейтинга.Задача от Google про 25 лошадей?
замерять время мы не можем поэтому только визуально зафиксировать кто 1,2 и 3. соответственно сортировать между собой тоже не можем т.к. нет таймера, только визуально определить победителей в конкретной группе до 5 лошадей
бежать за раз могут до 5
бегут с одинаковой силой и за одинаковое время в каждом забеге
какое минимальное количество забегов нужно чтобы найти самых быстрых?
Та лошадь, которая заняла первое место — очевидно, самая быстрая. Её можно снимать с соревнований — с ней всё ясно.
Та лошадь, которая в 6-м забеге пришла второй — в общем списке м.б. или второй (варианты 1,2,4 из списка выше), или третьей (вариант 3), или вообще не призовой (четвёртой и далее — вариант 5).
Понадобится 22 / 2 = 11 забегов.
Ответ написан более трёх лет назад
Нравится 1 25 комментариев
art style @arttstyle Автор вопроса
https://youtu.be/IMlrNbK4JGI?t=774
смотрю математика и чето меня его решение вообще не утраивает, но автор называет его «верным»
art style @arttstyle Автор вопроса
1. взяли из каждой строки 1 самого быстрого;
2. сравнили этих 5 лучших между собой. 4 и 5 точно медленнее, а значит, и все в их строках ещё медленнее.
2.это работает только для первых 10.
а дальше как он вычеркивает?
он не знает за сколько пробежали остальные лошади в первой и второй группе. может быть в первой группе все три самые быстрые лошади? или например 3 место в общем зачете быстрее чем 4 лошади из 2 группы или медленнее ?
Именно так: может «в первой группе все три самые быстрые лошади».
Поэтому берём из неё и 2 и 3.
Из 2-й группы 2 и 3 могут быть 1й и 2й, берём их.
Из 3-й только у топчика есть шанс.
Вот и сформировалась пятёрка для 7-го заезда:
2 и 3 из группа А, 1 и 2 из группы Б. 1-й из группы В.Задача- определить самую быструю лошадь
