Немцы поймали 100 узников посадили в камеру и раздали всем бирки с номерами от 1 до 100.
В соседнюю камеру поместили 100 ящиков, в эти ящики случайным образом разложили числа от 1 до 100, каждое число по одному разу.
Потом они поставили следующие условия:
Забирают по очереди из камеры узника, отводят в камеру с ящиками и разрешают открыть любые 50 ящиков в любом порядке. Если узнику удается найти свой номер, то он выиграл. Узники назад в камеру не возвращаются, никаких пометок на ящиках не оставляют и вообще никакую информацию еще не игравшим узникам передать не могут. Злые немцы объявили, что отпустят всех узников, если все они без исключения выиграют, иначе всех расстреляют.
Вероятность выигрыша одного узника 50% и соответственно на первый взгяд вероятность выигрыша всех узников ничтожна мала - (1/2)^100. Но они все предварительно сидят в камере и могут заранее договориться и разработать стратегию, как и какие им открывать ящики. Каким образом можно повысить эту вероятность до более  ощутимых шансов, к примеру хотя бы 10% ?

Хм, какая тут стратегия? Или выиграл или не выиграл, 50 на 50.

"Каким образом можно повысить эту вероятность до более  ощутимых шансов, к примеру хотя бы 10% ?"

На первый взгляд, никак.

(1) Можно с легкостью привести стратегию, понижающую шансы до 0. Значит должна существовать стратегия, повышающая шансы...

(3) И что это за стратегия?

(3) Приведи.

Не открывать ни единый ящик? ) Кстати, хороший способ самоубийства.

(5) Все открывают одинаковые ящики

(7) Это ничего не меняет.

(8) Эта стратегия гарантирует, что 50 узников выиграет, а 50 проиграет, те гарантирует 100% что их расстреляют.

Если бы они открывали ящики по случайной стратегии - то их шансы (1/2)^100.
Если из случайных стратегий исключить "гарантированно проигрышные стратегии" - то их шансы повышаются

(7) и как это понижает шанчы?

(10) 50 ящиков останутся никем не открытыми. Значит 50 номеров из этих ящиков точно проиграют

а понял, ибо тут либо все либо никто

Важное условие, что номера в ящиках остаются одними и теми же, все узники играют на одном раскладе

(9) Следуя этой логике надо сделать так чтобы максимально открывать разные ящики.

первые 50 - первые 50, вторые 50 - вторые 50

>>Важное условие, что номера в ящиках остаются одними и теми же, все узники играют на одном раскладе
где о нем в сабже?

т.е каждый второй открывает то что не открывал предыдущий, без разницы какие

Четные открывают четные ящики, нечетные - нечетные..

(15),(18) Уже лучше - шансы, если я не ошибаюсь, (1/2)^99

(16) Это подразумевалось, т.к. там нет условия, что каждый раз немцы перекладывают числа из ящиков случайным образом

(19) а, не (1/2)^50

Ну, тогда первый открывает 50 ящиков - 1/2 на победу, второй 50 ящиков 1/2 на победу, остальные ждут

(22) Ящики каждый раз естественно закрываются и все узники играют на равных условиях, но только на одном раскладе

Подсказка. Узник может принять решение, какой следующий ящик открыть по ходу игры

ну слева направо первый, второй справа налево.

главное точку отсчета выбрать.

Разнообразить выбор ящиков.

Допустим узников всего два.

Вероятность выигрыша при случайном выборе: 1/4

Однако если они договорятся, что первый выбирает первый ящик, а второй второй. То вероятность выигрыша 1/2.

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

Можно считать, узники могут договориться, как нумеровать ящики и условно выставить их в ряд.

(28) +1. В задаче нет решения.

(27) Ага! Оказывается, что если открыть ящик под номером своей бирки (первый открывает первый ящик, второй - второй, итд), нядеясь найти там нужный номер - это уже значительно повышает шансы. А вот как ходить дальше, если номер в ящике оказался не твой?

(0) приведенная вероятность - максимально возможная, все стратегии при этих условиях её только понижают

(32) см (27)

Для 4-х

Вероятность выигрыша 1/16

Допустим стратегия выбирать ящики от своего номера.

Первый выбирает 1 и 2, вероятность 1/2

Заходит второй. Выбирает 2-й и 3-й.

Ситуацию что первый не угадал можно не рассматривать потому как тогда по фиг. Рассмотрим вероятность, что угадал.

Тогда или это был первый ящик или второй. Если первый ящик, то вероятность выбрать правильный. 2/3 если это был второй вероятность 1/3  

Блин че то я торможу. Какая тут вероятность будет?

(27) тут количество некорректно, надо тогда рассматривать минимум 4 узника

Для 4-х

Вероятность выигрыша 1/16

Допустим стратегия выбирать ящики от своего номера.

Первый выбирает 1 и 2, вероятность 1/2

Заходит второй. Выбирает 3-й и 4-й.

Ситуацию что первый не угадал можно не рассматривать потому как тогда по фиг. Рассмотрим вероятность, что угадал.

Тогда вероятность выбрать правильный 2/3

3-й опять выбирает 1 и 2

С одной стороны мы знаем что один из ящиков точно не верный, с другой стороны мы предполагаем что первый и второй выбрал правильно тогда вероятность 1/2

Если исходить из того что и этот попал вероятность того, что последний выбрав 3 и 4 угадает  - 1

Т.е. вероятности типа 2/4*2/3*1/2*1/1= 4/24=1/6

(36) Короче надо прогу попробовать написать с моделями

(36) >> Ситуацию что первый не угадал можно не рассматривать потому как тогда по фиг.

Нельзя так делать

(36) это стратегия похожа на стратегию (15)
Это все равно, что пытаться вытащить 50 первых фишек из мешка со 100 фишками.
точная формула ((n/2)!^2)/n!, в (21) не учел, что фишки выбывают и шансы падают

Для n=4 вероятность как раз и будет 2!*2!/4! = 4/24 = 1/6

Но для 4 фишек есть стратегия на 25%

надо еще учитывать вероятность, что при отсутствии договоренности узник не будет метаться выбирать в случайном порядке, а просто по -порядку ближайшие от входа

а таких будет большинство

да и вообще, задача сама по себе бессмысленна и аморальна

Первый выбирает по порядку с 1 по 50.
Второй выбирает по порядку с 2 по 51.
...
Пятьдесят первый выбирает с 51 по 100.
Пятьдесят второй выбирает с 52 по 100 и потом 1.
...
Пятьдесят седьмой выбирает с 57 по 100 и потом с 1 по 6.
...
Сотый выбирает 100 и потом с 1 по 99.

(43) http://almutabi.livejournal.com/1144.html

А можно так: если узник нашёл свой номер - оставляет ящик открытым?

Какова вероятность того, что выйдя на улицу, вы встретите динозавра?
1/2 хотите сказать?
Тут рассчитывать нужно.

+(46) Тогда следующему надо угадать из 99, если он находит свой, то оставляет открытым и третий ищет среди 98.

(48) написано же:
Узники назад в камеру не возвращаются, никаких пометок на ящиках не оставляют и вообще никакую информацию еще не игравшим узникам передать не могут.

Имхо нет решения, особенно при "Злые немцы объявили, что отпустят всех узников, если все они без исключения выиграют, иначе всех расстреляют."
т.е. нужна не 10%, а 100% вероятность

(50) Решение не в том чтобы гарантированно спастись, а в том, чтобы повысить вероятность этого.

Немецкий кот Шредингера.

(49) Я не говорил про возврат назад. Оставить ящик открытым <> оставлять пометки на ящиках.

Переставлять ящики можно?

Если можно, то первый найденный номер ставит на №1; второй начинает с №2; а третий - с №3 и т.д.

(0)Хм, думается вероятность = 0, ибо все ровно расстреляют :)

(54) Кстати, перестановка под запрет не попадает.
Так что методом пузырька отсортировал 50 ящиков по возрастанию. Если нашел свой ящик, забрал его с собой - тоже не считается передачей информации.

Каждый узник начинает выбор со своего номера ящика (предварительно узники договорились о системе отсчета номеров ящиков и, что перебор ящиков осуществляется последовательно). Каждый узник, если его не расстреляли, начинает поиск со своего номера, при этом он знает что в предыдущих (n-1) ящиках уже смотрели точно, а кроме того могли смотреть и во всех ящиках вплоть до (n-1+50). Это наверно сократит как-то выбор нужных ящиков, хотя хз...

(54) Нет, переставлять нельзя. Это способ передать информацию

(58) Это не способ передать информацию, т.к. нельзя точно сформулировать, какая информация передается.

Но ящики могут быть приварены к полу :)

Если и переставлять нельзя - то думаю, что все остальные стратегии могут решить единственную задачу - чтобы все ящики проверены равное количество раз; и с этой позиции варианты "1-50;2-51;3-52;4-53..." , "1-50;51-100;1-50;51-100" , "чет/нечет" и прочие одинаковы и повышают шанс до 1/2^50.

(60)1/2^50 Это не 10%

(61) угу, я как раз об этом же

А в случае перестановки - шансы возрастают почти до небес :) первый расставляет все 50 ящиков на свои места по порядку; второй также, начиная с №2. В конце концов сотый уверенно открывает свой 100й ящик, будучи уверенным на 100%.

(62) Согласен. По идеи должно быть чтобы первые трое угадали свои ящики тогда вероятность будет 1/8=12.5% Эти трое занимаются перестановкой ящиков.

Первый упорядочивает ящики 1-50, второй 51-100. Каждый следующий гарантированно находит свой ящик. Общий шанс на успех 25%

Можно рассмотреть задачу и при разрешенных перестановках. В этом случае шансы можно повысить до 50%.
Первый открывает 50 первых ящиков и ставит на свои места. Шансы, что он нашел ящик №1 и соответственно поставил на свое место = 50%.
Какую тогда стратегию надо применить 2-му, чтобы гарантированно найти ящик №2 ?

Допустим он открывает №2 и находит там №2 (первый помог) - хорошо.
А если он открыл №2 и там другое число, что тогда?

Короче ответ такой: каждому узнику надо открыть свой номер. Если выпал свой - профит. Если выпал чужой - следующим открываем номер ящика, который выпал при открытии первого. И так далее по цепочке.
Вероятность додумайте сами

(66) 1/2^50 :)

1й. Номер у него 1. Открыл 1й - выпал 2. Открыл 2 - выпал 3. Открыл 3 - выпал 4. .. Открыл 50й - выпал 1.

2й. Почти повторит маршрут первого :)

(65)с перестановками будет 0.99*0.5 1й сортирует 50 первых по возрастанию второй открывает 2й ящик а затем 51-99й и сортирует их.

Точнее, лучшая стратегия такая. Первый узник упорядочивает ящики 1-50, его шанс на нахождение своего ящика 50%. Второй узник сначала двоичным поиском ищет свой ящик в первых 50, на это тратит в худшем случае 6 просмотров, затем упорядочивает ящики начиная с 51. Его шанс на успех 94% (или около того). У каждого следующего узника шанс на успех еще выше, приближаясь к 100%. Общий шанс на успех, по прикидке, 35-40%.

+(69) Чего-то я в арифметике напутал. У первого шанс 50%, у второго 94%, у остальных 100% (они 6 просмотров тратят на упорядоченные ящики 1-50, еще 6 на упорядоченные ящики 51-94, и еще 6 на оставшиеся ящики). Итого общий шанс на успех 47%.

по теме:
изначально у каждого шанс почти 71% найти свой номер
для того, чтобы иметь ощутимые шансы на успех - 10%, нужно приблизиться к 98% нахождения своего номера - это фактически нереально.
разница между 50% и 70% - пятнадцать порядков, хотя и шанс остается ничтожным

(69)зачем двоичный поиск если вторым пойдет узник с номером 2?
ящик номер 2 и 51-99 (упорядочить таким образом первые 50 и номера 51-99), вероятность 98/99, а вот далее уже двоичный поиск в (1-50),(51-99)и ящик номер 100
итого общий шанс на успех 98/198

(66) Короче читай (44) :))

все открывают 50 ящиков с одинаковым набором номеров. Гарантированно, что 50 совпадет, а значит вероятность ровно 50%. Ведь речь идет именно о максимальной вероятности, а не шанса выжить.

(0) А узники могут построить "сотртировочную машину"?
Т.е. 50 узников открывают сначала 50 первых ящиков. Если там есть бирка с номером "1", то узник ее несет в крайнюю левую позицию. Иначе открываем 50 вторых ящиков

Думаю, 50 узников за 50 движений отсортируют этот массив и добьются победы )

Не, вероятность не будет 50%.

(73) в (44) Совершенно другой алгоритм чем в (66)
поясняю на пальцах

Допустим первый открывает 1 ящик и видит там 5
потом открывет 5 ящик вид 2
открывает 2 видит 49
открывает 49 видит 16
....
через n ходов
...
открывает 5 ящик - видит 1 .

Если n<=50 то 1 выиграл

приходит второй - открывает ящик 2 - а там 49
открывает 49 а там 16
..
итд. через n ходов
...
открывает 5 видит 1
открывет 1 видит 2 - выиграл


т.е. если выиграл первый узник, то и выиграют все, кто в его цепочке.

перестановка ящиков разобъется на независимые цепочки.

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

(77) и какова вероятность?

Возьмем первую цепочку.
Верочтность того, что она закончится на 1 ходу 1/100, или то, что она продолжиться 99/100
Вероятность того, что после второго хода она продолжиться на 3-й ход равна 98/99
Вероятность того, что после третьего хода она продолжиться на 4-й ход равна 97/98

т.е. вероятность того, что ее длина больше 50 равна
99/100*98/99*97/99...*50/51 = 50/100 = 50%

вероятность = колво перестановок длина < 50 / колво всех перестановок из 100 элементов

(79) это только у первого и это равно как и наугад. А остальные?

(72) У меня расчет для общего случая, когда узники выбираются в случайном порядке. В условии не сказано однозначно, что узники пойдут в порядке своих номеров.

(0) вероятность увеличить значительно нельзя

предположим была разработана некоторая стратегия:
тогда в результате мы имеем первый ящик открывало х1 чел, 2-ой - х2 и т.д.
вероятность что первый ящик открыл тот кому нужно х1/100, 2-ой - х2/100 и т.д
x1+x2+...+x100=5000
а вероятность что все откроют нужный ящик x1*x2*..*x100/100^100
т.е. чтобы получить максимальную вероятность надо получить максимальное произведение х1 .. х100, максимальное произведение получиться если сумма будет равно распределена, т.е. х1=х2=...=5000/100
т.е. каждый ящик будет открыт 50 раз
и вероятность получается (1/2)^100
на самом деле вероятность будет несколько выше т.к. зная что первый ящик открыл тот кому нужно, вероятность правильного открытия второго ящика будет чуть больше чем 50/100  (х2/100 в расчетах), а именно 2501/5000, следующего 2502/5000, но в целом очевидно, что довести вероятность даже до 1% не реально

(83) никто не заставляет узников заранее выбирать стратегию с фиксированным распределением открывания ящиков x1 x2 x3...x100
см. алгоритм в (66)

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

(0) Asirius, уточни плз:
1. Можно ли переставлять ящики.
2. Возможно ли что ящики уже расставлены в каком-то порядке?
3. Можно ли оставлять ящики открытыми?
4. Если узник нашел свой ящик, то его сессия заканчивается, или он дальше может открывать ящики?

Первое, что приходит на ум, это сначала открыть ящик с номером своей бирки, потом открывать на n-ом шаге ящик под номером, который был в ящике с номером n-1. А вот что открывать, если в ящике n-1 номер самого ящика? И что это дает?

(85) Считай что номера написаны мелом на дне ящика, а ящики прибетонированы к полу.

(87) "А вот что открывать, если в ящике n-1 номер самого ящика? " - это либо первый ящик и его номер совпадает с искомым. Либо это не возможно, поскольку номер текущего ящика ВСЕГДА в предыдущем ящике..
(66) Маджонг какой-то. В большинстве случаев нерешаемо будет.

(89) точно, ну вот стратегия для всех, какая-никакая, но о которой можно договориться предварительно и не требует смены по ходу открытия

(86)
1. Нет
2. Как пронумеровать ящики узники могут договориться (например по принципу ближайший ко входу, справа на лево). Можно считать, что они условно выставлены в ряд.
3. Нет
4. Это не важно, т.к. он уже выиграл а открывая-закрывая другие ящики он ничего не изменит, т.к. ничего другим передать не может

(80) Подсчитал точную вероятность для (66)
Это 1-1/51-1/52-1/53-...-1/100 что примерно 0.33

Сначала изучаем
ru.wikipedia.org/wiki/%CF%E5%F0%E5%F1%F2%E0%ED%EE%E2%EA%E0

любая перестановка - произведение циклов.
1. всего перестановок n!
2. количество циклов длинны k равяется n!/((n-k)!*k)
3. Количество перестановок, в котором есть цикл длины k равняется количеству циклов длины k * количеству перестановок длинны n-k. Те. равно n!/((n-k)!*k) * (n-k)! = n!/k

Проигрывают перестановки, в которых есть циклы длинны 51,52, 53...100
Таких перестановок всего 100!*(1/51+1/52+...1/100)
Всего перестановок 100!
Значить вероятность проигрыша 1/51+1/52+...1/100

(92) а теперь дело за малым - показать что этот результат наилучший