100 заключённых

По условию задачи в тюрьме находится 100 заключенных, каждый из которых имеет личный номер от 1 до 100. Тюремщик решает дать заключенным шанс на освобождение и предлагает пройти придуманное им испытание. Если все заключенные справятся, то они свободны, если хотя бы один провалится — всем увеличат срок в двое

Тюремщик идет в секретную комнату и подготавливает 100 коробок с крышками.
Коробки пронумерованы от 1 до 100

В каждую коробку он кладет табличку с нумерацией от 1 до 100. в произвольном порядке и закрывает крышкой

Заключенные не видят, как тюремщик выполняет все эти действия.

Соревнование начинается: тюремщик отводит каждого заключенного по одному в комнату с коробками и говорит, что он должен найти коробку, в которой будет находиться табличка с номером заключенного. Каждому разрешается открыть до 50-ти коробок из 100;
Если заключённый находит свой номер его отводят в другое помещение и с оставшимися он общается не может. Коробки опять закрывают и ведут следующего

если каждый из заключенных найдет свой номер, то заключенных отпустят, если хотя бы один из них не найдет свой номер за 50 попыток, то всем продлят срок

Вопрос как им победить?
------------------------------------------------------------------------------------------------------------

И второй вариант: с условием что разрешается пометить коробку в которой лежит номер заключённого который прошёл испытание.

Заключённые могут обсудить стратегию и выбрать, кто пойдет в комнату, и в какой последовательности.

0

Кандидат стратегии - открыть коробку 88, затем открыть коробку с номером таблички из коробки 88.
Вероятность выигрыша равен вероятности что 88 участвует в цепочке длины L <= 2.

Добавлено через 3 часа 49 минут
Моделирование вышеописанного кандидата стратегии дает вероятность близкую к 2.143% для 100М перетасовок.
Моделирование простой "взять любые два" дает вероятность 1.996% для 100М перетасовок.

Разница существенная. Есть ли стратегия которая лучше чем "посмотреть в ящике 88, затем в ящике с номером из ящика 88"?
Или хотя бы статистически равна, если не лучше.

Моя попытка аналититического подсчета.
Для "взять любые два" - 1/100 что окажется в первой, плюс 99/100 * 1/99 = 1/100 что окажется во второй, т.е. 2%
Для "взять две цепочкой" - 1/100 что окажется в первой, плюс 99/100*{вероятность цепочки из ровно двух}

Цепочку длины 2 с участием числа 88 можно сформировать 99 способами, и оставшиеся 98 карт перемешать 98! способами.
Вероятность цепочки длины 2 с участием числа 88: 99*98!/100! = 1/100 ... ?

Что-то я не так считаю. Должно получиться заметно больше чем 1/99

Добавлено через 4 минуты
mathmichel, вы здорово разбираетесь в комбинаторике, можете помочь?

Добавлено через 14 минут
Моделирование для трех, четырех и пяти открытых ящиков дают вероятность 3.166%, 4.198% и 5.205% соответственно.

0

QueryMonkey,
так вероятность от ого что ты откроешь 2 коробки цепочкой или просто выберешь 2, будет 2/100 2%

0

dimank666,

Моделирование программой даёт иной результат.

С теорией двух шагов я пока не разобрался

Добавлено через 20 минут
Вроде теория даёт 2.01%, это сильно отличается от наблюдаемых 2.14% в моем эксперименте.

Вероятность цепочки длиной ровно два, содержащей 88, это

99*98! / (100! - 99!) = 1/99.

Всего 1/100+1/99 = 2.01(01)

0

Я взял миллион перемешанных случайным образом коробок с карточками,
и посчитал за сколько шагов находится число 88 методом цепочки, и методом "брать первые N с начала".

Получилось что метод цепочки немного обгоняет метод "по порядку", т.е. требует меньше шагов.

Миниатюры

 

0

Я сам себя запутал, надеюсь что не других.

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

У меня по-прежнему не получается посчитать вероятность что два первых узника пройдут испытание пользуясь цепочкой.
Это будет что-то между 0.31 и 0.5.
Для одного - 0.5
для двух - ?
..
для ста: 0.3118

0

Сообщение от QueryMonkey У меня по-прежнему не получается посчитать вероятность что два первых узника пройдут испытание пользуясь цепочкой. Это будет что-то между 0.31 и 0.5. Для одного - 0.5 для двух - ? .. для ста: 0.3118

вероятность что 1 пройдет 50%
для двух она уже составляет 0,5*0,5=0,25%
для трёх она будет 0,5*0,5*0,5= 0,125%
и так далее

0

dimank666,

Для сотни ведь не 0.5^100, а 0.31 пользуясь стратегией цепочки.
Значит и для первых двух не менее 0.31.

0

Сообщение от QueryMonkey Значит и для первых двух не менее 0.31.

для стратегии цепочек уже не столь важно сколько народу

Добавлено через 12 минут

Сообщение от QueryMonkey Значит и для первых двух не менее 0.31.

тут тебе надо вычислить количество цепочек свыше 50
1/51+1/52+1/53 ..... 1/100 =0,69

Добавлено через 7 минут

Сообщение от QueryMonkey Значит и для первых двух не менее 0.31.

тут смотря как рассуждать
если всего два заключённых
первый выберет стратегию цепочек а второй стратегию наугад то будет 1/2*1/2=25% вероятности что они оба найдут.

0

Сообщение от dimank666 для стратегии цепочек уже не столь важно сколько народу

Я бы сказал - абсолютно не важно. Но не вполне абсолютно) Важно только для случая, когда есть цепочка длиной более 50. А если такой цепочки нет - абсолютно не важно.

0

dimank666,

Речь конечно про первых двух, которые оба пользуются цепочкой.

Присутствие в раскладке цепочки длиннее 50 не сводит вероятность к нулю для первых двух.

Например, если есть цепочка длиной 60, то для двух любых (или для двух первых) вероятность пройти испытание 0.4²=0.16,
хотя вероятность что 41 или более пройдут испытание равна нулю.

Добавлено через 1 минуту
Для первых двух ответ где-то в районе 0.4, а вот точную формулу вывести пока не могу.

0

Попробую ответить на мой вопрос для N=10 и пяти попыток.

Шанс, что самая длинная цепочка превысит 5 равны 1/6+1/7+1/8+1/9+1/10 = 0.645635
T.e. с вероятностью p* = 35.4365% все узники пройдут испытание, используя алгоритм цепочки.

Для двух узников, вероятность равна p* плюс вероятности что они оба не попали в цепочку длины > 5.
Если в коробках присутствует цепочка длины 6, то вероятность что оба не попали в нее равна 3*4 / (9*10), или 2/15
Если цепочка длины 7, то 2*3/90 = 1/15
Если цепочка длины 8, то 1*2/90 = 1/45
Если цепочка длины 9 или 10, то вероятность 0.

Искомая вероятность для двух P2 = P* + 1/6*2/15 + 1/7*1/15 + 1/8*1/45 = 0.388889

Проверим что метод работает для одного узника, должно дать 0.5:
цепочка 6: 4/10
цепочка 7: 3/10
цепочка 8: 2/10
цепочка 9: 1/10
цепочка 10: 0

P1 = P* + 1/6*4/10 + 1/7*3/10 + 1/8*2/10 + 1/9*1/10 = 0.4999999

Да, сходится. С точностью моего округления совпало.

Ответ для задачи с 10 узниками:
для одного узника 0.5, независимо от стратегии.
для двух - 0.388889, пользуясь методом цепочки
для всех: 0.354365, пользуясь цепочкой

Интересно разница между P2 и P* всего около трех процентов. Это говорит что если первые два прошли, то почти наверняка и остальные пройдут. Эту закономерность подметил I can в четвертом сообщении этой темы.

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

1