19 декабря 2011, 19:43

Задачка на смышленость =)

Есть табунчик 25 коней.
Задача: при помощи минимально возможного количества заездов, в каждом из которых может принимать участие до 5 коней отобрать троих самых быстрых животных.

задача мозг трейдинг комбинаторика логика юмор

Головин Евгений

Москва

168

1 531

с 19 сентября 2011

22 Комментария

XoXoL-T
19 декабря 2011, 19:53
Условия конкретизируйте… Коней отобранных в предыдущих заездах можно включать в последующие заезды ???
Вообще, задачка чисто на динамическое программирование… Сейчас не скажу какими уравнениями описывается и каким алгоритмом решается… Но, точно из этого раздела…
0
- Головин Евгений
  19 декабря 2011, 21:29
  XoXoL-T, да
  0
Антон Кротов
19 декабря 2011, 19:53
Прикольно :)
9 получается
0
- Антон Кротов
  19 декабря 2011, 20:58
  Что-то подумал, поразмыслил… В 7 можно уложиться.
  0
  - Головин Евгений
    19 декабря 2011, 21:30
    Антон Кротов, как в 7 я тоже знаю…
    но это самый красивый способ пока достигнутый
    0
- Головин Евгений
  19 декабря 2011, 21:29
  Антон Кротов, много :)
  0
serg
19 декабря 2011, 19:58
5 заездов, чо.
Время замерять никто не запрещал вроде?
0
- Головин Евгений
  19 декабря 2011, 21:29
  serg, время замерять низя конечно)
  0
Александр Крупскийсергеев
19 декабря 2011, 20:03
6 заездов
0
Tony Lemon
19 декабря 2011, 20:10
6 будет
0
- Головин Евгений
  19 декабря 2011, 21:30
  Redbox, как опишите?!
  0
  - Tony Lemon
    19 декабря 2011, 21:36
    Eugene_UKFU, в каждом забеге по 5 коней, отсюда 5 забегов, с каждого забега берем первую лошадь (самую быструю). Делаем шестой забег и выявляем первые три самые быстрые лошади.
    0
    - serg
      19 декабря 2011, 21:49
      Redbox, ну прям… и че будет если 3 сильнейших случайно попадут в 1ю пятерку?
      +1
    - Головин Евгений
      19 декабря 2011, 21:52
      Redbox, а что если при организации первого забега выйдет так что 3 самые быстрые из всех окажутся в одной из пятерок?
      тогда 2 самых быстрых реально мы отбросим.
      0
Tony Lemon
19 декабря 2011, 21:53
это принцип применяется в спорте, взять тот же футбол или гонки. везде могут быть случайности, но самый короткий этот путь.
0
Головин Евгений
19 декабря 2011, 22:04
естественно он короткий, но неверный.
Когда играют ЧМ так команды по 4 делятся, а что если там англичане немцы французы и бразильцы например?
Ясен перь что двое вышедших из группы лузеров могут быть хуже вылетевших из такой.
Я потому фут и не смотрю… :)
0
- serg
  19 декабря 2011, 22:18
  Eugene_UKFU, а вы вообще уверены, что за 6 задача решается?
  0
  - Головин Евгений
    19 декабря 2011, 22:32
    serg, нет не уверен, но надо же доказать, что не решается.
    0
    - serg
      19 декабря 2011, 23:41
      Eugene_UKFU,
      в любом случае нужно протестировать всех коней хотя бы 1 раз.
      3 пути решения:
      1) начать с независимых испытаний (как у alexv1975) — невозможно так как после 5го испытания не существует способа всего лишь одним испытанием выявить трех победителей
      2) разбить на 2 или больше независимых групп и проводить зависимые испытания внутри них — бесполезно, так как группы независимы невозможно гарантировать что все сильнейшие не останутся внутри одной группы.
      3) остается 1 путь — все испытания должны быть зависимы — то есть в каждом испытании должен участвовать конь, ранее участвовавший в другом испытании. При этом единственно возможный способ испытать всех коней за 6 заездов — это брать в каждый последующий заезд только одного коня из предыдущих заездов.
      4) из того, что сравнивать между собой независимо протестированных коней невозможно следует что после каждого заезда должны быть ясны 3 сильнейших на текущий момент. Поэтому, если найдется хотя бы один способ разделения коней таким образом, что 3 сильнейших не будут ясны, то это будет означать что за 6 заездов протестировать невозможно.
      
      После 1го заезда все ясно
      Легко показывается, что если во втором заезде участвует любая из 5 лошадей 1го заезда (+4 случайных непротестированных), то возможен расклад, при котором 3 сильнейших после второго заезда неопределены.
      Вроде ничего не перепутал :)
      +1
      - Головин Евгений
        20 декабря 2011, 11:36
        serg, вполне обстоятельно, думаю что 7 это реально лучший вариант.
        0
alexv1975
19 декабря 2011, 22:28
7м: 5 забегов, 1 забег победителей + еще 1 забег на проверку (номера 2,3 из забега победителей + номера 2,3 из забега лошади победительницы, номер 2 из забега лошади, пришедшей 2й в забеге победителей).
+1
- Головин Евгений
  19 декабря 2011, 22:33
  alexv1975, супер!
  0