Задачка.
Царь собрал своих мудрецов (100 шт.) и говорит:
— Я решил вас испытать. Пусть каждый напишет на бумажке своё имя. Бумажки мы положим в 100 одинаковых коробочек и закроем в комнате. Каждый по очереди должен войти в комнату и открыть не более половины всех коробочек. Если хоть один не найдёт своё имя в открытых им коробочках, то всем кирдык.
Общаться во время испытания нельзя, только если договориться заранее. Комната после каждого захода возвращается в исходное состояние, так что сообщение не передать.
Какую стратегию должны использовать мудрецы, чтобы выжить с максимальной вероятностью?

GD Star Rating
loading...

52 Responses to Задача про мудрецов

  1. XoDad:

    Пользоваться одинаковыми именами

  2. LeCrazy:

    Это была бы задачка для хакерской блогы.

  3. Ytresq:

    По–моему, прикольнее её давать сразу с ответом — он на первый взгляд поразительный и невозможный, но подсказок по решению не даёт.

  4. LeCrazy:

    Ну, могу подсказать, что искомая вероятность — чуть больше 1/3, и от количества мудрецов это не зависит.

  5. Neegne:

    По–моему задача со скрытым условием. Хочу деталей — порядок размещения коробочек и листочков в них произвольный?

  6. LeCrazy:

    Да, берут одинаковые коробочки, произвольно расставляют.

  7. Hempa:

    какой интересный тимбилдинг)))

  8. Neegne:

    А они могут врать относительно своих имен? То есть записать не свое имя?

  9. LeCrazy:

    Не думаю, что это бы им помогло, но, в любом случае, тут всё честно. Может даже, это не они пишут, а сразу приходят на всё готовое. Но имена друг друга они знают и могут предварительно придумать стратегию.

  10. LeCrazy:

    Да, ещё вот что. Решение требует знания одного математического обстоятельства.
    С этой точки зрения она в разы сложнее, чем известная задача про сто гномов и колпачки.

  11. Hempa:

    мудрецы с одинаковыми именами должны открывать одинаковые коробочки.

  12. LeCrazy:

    а если всех мудрецов зовут по–разному?

  13. AkMoon:

    аксиома выбора?

  14. Ni001:

    Не очень понятно условие: их отпустят, если хотя бы один найдет свое имя, или только если все найдут свои имена?

  15. Neegne:

    только если все.

  16. LeCrazy:

    Если каждый, открыв не более половины коробочек, найдёт своё имя.

  17. AkMoon:

    а коробочки в произвольном, неменяющимся порядке разложены?

  18. Ni001:

    Тогда второй вопрос: если открыв коробочки мудрец не найдет свое имя, их казнят сразу, или сначала поведут в комнату всех оставшихся?

  19. LeCrazy:

    А смысл вести, если уже всё?

  20. XoDad:

    нет, еще дадут покурить напоследок

  21. Ni001:

    Ну чисто теоретически это информация мудрецам о том, что их товарищи нашли свои имена. Хотя с другой стороны мудрецы в любом случае должны исходить из того, что предыдущие нашли(если кто–то уже провалился, выбирай не выбирай ты уже труп).

  22. Neegne:

    Солгасен. Я так полагаю, что они должны сформулировать систему по которой будут выбирать свои 50 коробочек для проверки. Таким образом сам факт того что их еще не казнили после каждого опыта дает дополнительную информацию о том, чтобы исключать при последующем поиске определенные коробочки.

  23. Ni001:

    смысла нет — они должны исходить при выборе из того, что предыдущие не провалились. Потому что провал предыдущих означает провал всего дела.

  24. Ni001:

    Можно попробовать порешать в общем виде для n мудрецов.
    n=2 p=1/ первый выбирает одну, второй выбирает другую, если первому повезло, то второму гарантированно попадется его имя, первому повезет с вероятностью 1/2)
    n=3 p=1/ первый выбирает одну, второй––вторую, третий––третью. Первому повезет с вероятностью 1/3, второму с вероятностью 1/2, если повезло первому. Если повезло первым двум, то третьему гарантированно достанется его имя.

    n=4 p=?

  25. XoDad:

    пользуясь случаем, передаю привет из коробки…

    для одного мудреца это опыт как с монеткой — вероятность 1/2
    по идее, эксперименты независимые… думай, голова..

  26. ReMonkey:

    Двоичное дерево вероятностейц надо строить.

  27. LeCrazy:

    на всякий случай: можно открыть не одну коробочку, а половину всех.

  28. Neegne:

    Нет, давайте так.
    n= первый выбирает первые 2, второй выбирает 2 со второй, третий выбирает вторые 2, четвертый выбирает последнюю и первую. А что это нам даст? )))

  29. Ni001:

    ну так при n=2 и n=3 половина всех это 1 🙂

  30. ReMonkey:

    И надо учесть, что из игры с отсутствием информации в какой–то момент переходит в игру с полной информацией.

  31. Neegne:

    Ну да.. только вот функция выбора комбинаций неочевидна.

  32. XoDad:

    как классическая задача с выбором машины за тремя дверями.

  33. Ni001:

    первый выбирает первые две. Перед вторым выбор: выбрать те же две, выбрать одну открытую и одну неоткрытую, выбрать две неоткрытые.
    две открытые: вероятность что повезет 1/3
    одна открытая, одна неоткрытая: вероятность 1/2
    две неоткрытые: вероятность 2/3

    Если я где–то с расчетом не ошиблась.

  34. Ni001:

    Будем считать что второй выбрал две неоткрытые(с максимальной вероятностью).

    Тогда у третьего выбор:
    1. две открытые первым: вероятность 1/2
    2. две открытые вторым: вероятность 1/2
    3. открытую первым и открытую вторым: вероятность 1/2

    Так как ему все равно, какую коробку открывать, он дожен открыть ее так чтобы дать максимум информации четвертому.
    Если он откроет две первые или две вторые и ему повезет, то четвертый будет точно знать что его имя в другой группе коробок. Если же он откроет первую и третью, то перед четвертым будет выбор из таких возможностей расположения имен.

    1432
    3142
    4132

    Четвертый не сможет открыть две коробки так чтобы покрыть все варианты => третий должен выбрать либо первую+вторую, либо третью+четвертую.

    Тогда мудрецы спасутся с вероятностью 1/2*2/3*1/2=1/6.

  35. Ni001:

    Напрашивается решение что мудрецы делятся на две группы. Первая группа всегда открывает первую половину дверей, вторая––вторую.

  36. Noev:

    Монти Холл смотрит с интересом 🙂

  37. XoDad:

    У меня такая же мысль возникла, но вот только вероятность зависит от количества мудрецов и убывает как степень.

  38. Peels:

    Отличная задачка!

  39. XoDad:

    итак, решение — половина ответа

  40. LeCrazy:

    О, тоже неплохая формулировка.
    Кто туда ещё не смотрел, там по ссылке довольно толстая подсказка. Могу дать чуть потоньше:

    Мудрец не обязательно открывает все коробочки сразу. Более того, он не знает заранее, какие в точности коробочки он будет открывать.

  41. Noev:

    Я бы сказал, что по ссылке находится прямой ответ на вопрос в задаче, без математического обоснования только. Также привожится имя одного парня, который должен помочь получить это математическое обоснование.

    Чего же я то такой тупой, что вместе со всем этим не могу вывести это гребаное обоснование! я идиот! убейте меня, кто–нибудь! 🙁

  42. Peels:

    Если ты о Монти Холле, то он в этой задаче совсем не при чем.

  43. Noev:

    Нет, я в контексте обсуждения аналогичной задачи из твоей ветки подумал, что решение основывается на парадоксе Бертранда. Но сейчас понимаю, что он тоже тут не при чем.

  44. KiMatematik:

    я правльно понял — предыдущий мудрец может оставлять сообщение следующему открытостью\закрытостью коробок?

  45. Noev:

    Вся выборка коробок делится на совокупность замкнутых неперескающихся циклов. Если первый философ выживает, это означает, что начиная с первой коробки он попал в цикл, который включает в себя как миниму одну коробку и как максимум всех коробок. Тогда все остальные, начиная не с начальных точек предыдущих философов т.е. не с начал циклов образованных предыдущими философами, либо попадают в замкнутые циклы, открытые предыдущими философами, либо образуют свои собственные, в которых всегда менее половины коробок. Попадение в один из замкнутых циклов означает 100% шанс на выживание, образование свеого собственного, при условии не пересечения с другими циклами всегда дает шанс на выживание больше 50%, так как точно известно, что невозможно открывать коробки из другого цикла, в которых коробка с именем текущего философа не входит.
    В самом худшем случае следующий филосов (из первой половины) будет иметь шансы на выживание:
    N/((N–K)*2), где K — количество коробок, открытое до него (принимая во внимание тот факт, что все философы до него находили свой номер в первой же шкатулке).
    Далее опять бессилие, никак не могу формализовать все варианты, черт побери.

  46. LeCrazy:

    вопрос такой: с какой коробки должен начинать каждый философ, и как должен открывать потом?

  47. Emen:

    это мне чем–то алгоритмы сортировки напоминает.

  48. Noev:

    Ответ уже есть, его дал автор этой эе загадки в своей теме. Мне никак не удается вывести формулу, которая строго бы доказывала, что вероятность для такого алгоритма будет > 0.25 хотябы.
    Вообще уже логика подсказывает, что надо брать 100! всех возможных перстановок и вертеть разные совокупности циклов, прикладывая вероятности выживания философов при каждом варианте перестановки, но это как то сложно получается чтоли..

  49. LeCrazy:

    Дело в том, что затея увенчается успехом в том и только в том случае, если в перестановке не окажется цикла длиной более 50. Нужно пересчитать все такие перестановки, тут уже комбинаторные формулы.

Добавить комментарий