Добрый день, товарищи, дамы и господа!

Задача не новая, и, возможно, вы уже с ней знакомы. Но, всё же, кто ещё не знает, попытайтесь придумать решение.

(текст задачи взят из википедии, но есть и другие интерпретации)
Начальник тюрьмы предлагает ста узникам, приговорённым к смертной казни, последний шанс. Узники пронумерованы от 1 до 100, а комната содержит шкаф со 100 ящиками. Начальник случайным образом помещает в каждый ящик по одному из номеров от 1 до 100, во все ящики — разные номера. Узники по очереди входят в комнату. Каждый узник может открыть и проверить 50 ящиков в любом порядке. После каждого узника ящики снова закрываются, а все номера остаются в ящиках. Если каждый из узников найдёт в одном из ящиков свой номер, то все узники будут помилованы; если хотя бы один узник не найдёт свой номер, все узники будут казнены. Прежде чем первый узник войдёт в комнату, узники могут обсудить стратегию, но не могут общаться после этого момента. Какова лучшая для узников стратегия?

Если все узники будут выбирать ящики случайным образом, то вероятность победы примерно 0,0000000000000000000000000000008

(1) Навалять начальнику по щам.100 против одного это серьезно.

ну тут прикол в том, что если прайзонер нашел свой номер, то игра продолжается.
А если не нашел, то финита.
Таким образом даже простейший сдвиг рулит и увеличивает шансы.
т.е. первый проверяет 1-50
Второй 2-51 и т.п.

(3) а смысл? Надо же найти свой номер, а после начала игры уже нельзя передать информацию назад, следующим узникам, т.е. вероятность 1-го = 50%, второго тоже 50%. И так 0.5^100 = все умрут

ну навскидку что-то типа первый проверяет: 1-50 Если выжил, значит в первых 50 уже один номер вскрыт.
Второй: 51-100, если выжил, значит во вторых 50 уже один номер вскрыт.
Далее идет половинное деление
третий: 1-25, 51-75
четвертый: 26-50, 76-100
Ну и далее каждый из этих интервалов делится пополам.
Думаю, это макс выигрышная стратегия, но это на интуиции

(4) смысл найти стратегию, где шансы больше, чем ноль.
Потому что если каждый будет проверять 1-50, гарантированно всех казнят.

(0) А перекладывать номерки можно?

(5) Узники не знаю ничего друг о друге, ни о судьбе предыдущих, ни о проверенных ящиках и номерах.

Здесь полная безнадёга. Вероятнее всего все умрут. Вопрос только, можно ли как-то снизить вероятность всеобщей смерти.

Первый же узник с высокой вероятностью не найдёт свой номер и всех казнят.

(0) Каждый, как минимум должен открывать шкаф со своим номером. Чую в этом загвоздка, но не знаю как обосновать :-)
(7) Узника знают о судьбе предыдущих. Если предыдущий нашел свой номер, то они еще живут.

допустим узник номер 50 нашел свой номер в диапазоне с 1ого по 50 ящик или с 50 по 99, что это нам даёт ? типа не надо эти ящики открывать, так как вероятность найти в них меньше?

Задачу можно сократить до двух ящиков и одной попытки.

(11) и до двух узников? не, тогда вероятность всегда будет 0,25

(9) "Узника знают о судьбе предыдущих." - И что это им даёт? Вероятность того, что открыв 50 ящиков из 100, ты найдёшь там свой номер - ровно 50%. И так у каждого узника.

(9) А если там нет твоего номера, то следующим открывать тот ящик, чей номер нашёл. Если так будет делать каждый, то вероятности могут немного накопиться.

(12) Почему до двух? До одного узника и двух ящиков.

(14) А как они узнают, какой был ящик?
"Прежде чем первый узник войдёт в комнату, узники могут обсудить стратегию, но не могут общаться после этого момента."

(13) Надо эти события сделать зависимыми, тогда не будет 0.5^100. Если первый выжил, то у второго должно быть чуть больше шансов.

(16) Они же знают свои номера. У каждого своя предопределённая цепочка открываемых ящиков. Она не случайная, значит вероятность будет не 0.5^100.

(14) кстати да, прикол.

(14) Это верный ответ. Вы сами дошли до этого?
Вероятность победы при этом будет примерно 0,31

(20) Вах! А чего так много? Я просто хотел убрать случайность в выборе ящика. Только я не понимаю, как так сильно накопилась вероятность

(18) если первым открыть ящик со своим номером, а потом следовать по цепочке - открывать следующим ящик, номер которого лежит в открытом, то  у каждого не просто предопределенная цепочка ящиков, а цепочка, рано или поздно приводящая к своему ящику.
Осталось только посчитать, какова вероятность того, что длина цепочки будет больше 50.
Попутно отмечу - такая цепочка может быть только одна,  все остальные цепочки в этом случае будут меньше 50.

(21) вот вероятность такой цепочки (длиной больше 50) и определяет общую вероятность победы  в 32%

Ах, вот оно что. Длина цепочки... И цепочка длиннее 50 единственная. Ну вот.

Если листы случайным образом разметить в ящики, то будут образованы цепочки номеров.
Например, узник1 открывает ящик1, в котором лежит лист2. Далее он открывает Ящик2, в котором лежит Лист3. Далее он открывает Ящик3, в котором лежит лист1. Ура
Получилась замкнутая цепочка 2-3-1. Все номера в ящиках буду принадлежать таким цепочкам.
Самая короткая цепочка если в ящике лежит лист с тем же номером.
Выходит, при такой стратегии, проигрыш будет только в том случае, если образуется цепочка более 50 номеров. А вероятность такого равна примерно 0,31

Подробный разбор от Veritasium
https://www.youtube.com/watch?v=wWQ9YdreY9c

Кстати, тюремщику можно было бы очень легко бороться с этой стратегией - достаточно в каждый ящик положить номер следующего ящика, ну а в последний ящик - номер первого.
Тогда цепочка будет только одна, длина ее равна 100 и каждый заключенный, чтобы открыть свой номер, должен пройти по цепочке 100 итераций. Но в условии - тюремщик случайным образом размещает номера в ящиках, так что увы, тюремщику облом.

(0) "не могут общаться после этого момента. Какова лучшая для узников стратегия?"

Что подразумевается под общением?
Общение без слов тоже запрещено или нет? Никаким способом нельзя передать информацию последующим?

(26) А кто сказал, что нельзя случайно разместить номера именно так? " в каждый ящик положить номер следующего ящика, ну а в последний ящик - номер первого."? :)))

Сейчас я вам новую задачку дам.
Задачка 5-го класса про хоровод мальчиков и девочек

(27)+ Суть в запоминании номеров пройденной цепочки узником и передаче следующему (допустим они идут по порядку) есть ли там его номер.
И если узник быстро нашел свой номер, он может потратить часть оставшихся от 50 попыток на прохождение цепочки следующего узника и передать ему с какого ящика начинать для продолжения.
В итоге можно окучить и >50 цепочки

(28) Очень низкая вероятность

Имхо должно быть условие что можно переложить хотя бы один номер(поменять местами два).

И в конце каждый заключенный должен сказать где его номер.

Тогда можно какуюто сортировку массива за 50 шагов выполнить.

Если бы был тюремщик в сговоре с узниками, то ему достаточно было бы переложить всего 2 листа местами, и разорвать цепочку более 50 листов на 2 цепочки. И тем самым увеличить шансы на победу до 100%

(33) Не факт. Могут быть такие расклады что разрыв одной цепочки более 50 приведет к увеличению другой сверх 50
Например две цепочки всего 51 и 49, в этом случае перекладывание двух листиков запросто поменяет на 49 и 51

(34) речь про то, что перекладывать нужно только в рамках цепочки из овер 50
Тогда она разорвется на две

(35) +1

А представьте подстава. В 25 ящике лежит номер на 24, в 24 на 23, и т.д. до 1. В первом лежит номер 25. В 50 лежит номер 49, в 49 .... в 26 номер 50. Получаются круги.
А если еще и совпадет что вообще все номера парами лежит (в 1 номер 2, а во втором номер 1, и так все числа). То боюсь не выживут ребята.

(37) выживут
если он идет к ящику со своим номером, то в цепочке гарантированно есть его номер.
главное чтобы длина цепочки не превышала 50

(38) А, понял.:-)

Вы тут что, прорабатываете новый эпизод игры в кальмара, или готовитесь потестить на практике? оО

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

(40) Этого не забудьте в первую сотню, дофига догадливый.

Речь идет о стратегии !

Так, если заключенные решат что надо выбирать, допустим, только четные это будет 50%. Если первые 25 и последние 25, тоже вероятность 50%.
Т.е. любая такая формула которую выбрали вначале на всю игру дает только 50%. 50% получается сложением 50 попыток каждая из которых это 1%.

Но ! Есть еще одна стратегия.
Первая попытка это 1% (выбор 1 из 100).
На второй попытке обязательно нужно поменять предыдущий запланированный выбор! Так как он был 1 из 100. А теперь это 1 из 99 и вероятность уже 1,01010101%
На третьей попытке тоже меняем предыдущий запланированный выбор. Теперь это 1 из 98 и вероятность уже 1,020408163%
и т.д.

При такой стратегии вероятность выигрыша составит 68,81721793%

(43) >Речь идет о стратегии !

Собрались однажды лесные мыши, чтобы решить как жить дальше. Совсем им невмоготу. Все звери их обижают, все их едят, а они маленькие и беззащитные отпор дать не могут. Одна самая умная мышка предложила: «А давайте обратимся к Мудрой Сове! Она подскажет нам что делать!»

Обрадовались мышки и побежали к Мудрой Сове. Прибегают и спрашивают: «Мудрая Сова, как нам быть? Все нас обижают в лесу. Мы маленькие и беззащитные. Что нам делать?» И ответила им Мудрая Сова: «Чтобы вас не обижали, вам надо стать ёжиками! Ёжики тоже маленькие, как и вы, но колючие и их никто не трогает».

Возликовали мышки: «Ура, мы станем ежиками! Никто не будет нас трогать!» Побежали к себе пританцовывая от радости. Но по пути самая умная мышка остановилась и спросила сородичей: «Стойте, а как нам стать ёжиками?»

Пришлось возвращаться к Мудрой Сове. «Мудрая Сова, — сказали мыши, — а как нам стать ёжиками?»

— Ребята, идите на фиг, — ответила Мудрая Сова. И добавила: — Мое дело стратегия!

© c3.14жжено