Стратегия игры (100 заключенных, вероятность выиграть)

[MGM]

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

Положительный ответ напрашивается сам собой. Есть почти очевидная стратегия, которая незначительно увеличивает вероятность два в минус сотой степени.
Но есть и другая, которая может сделать вероятность выигрыша порядка 30%.
Я эту стратегию знаю, и даже имею некоторые соображения, почему она работает, но рассудок отказывается в это верить.
Может кто знает простое объяснение феномена?

[Henrylee]

MGM писал(а):

Я эту стратегию знаю

Может изложите? А там и посмотрим.

[MGM]

Henrylee писал(а):

MGM писал(а):

Я эту стратегию знаю

Может изложите? А там и посмотрим.

Каждый начинает поиск с ящика соответсвующего своему номеру, а затем рекурсивно открывает ящик с номером обнаруженном в передыдущем. Что делать если обнаруженный чужой номер соответствует номеру ящика не знаю. По моему просто выйти из игры. Если кто знает поправьте.

[TOTAL]

MGM писал(а):

Если кто знает поправьте.

Чётко изложите условие задачи.

[PAV]

Не поленился и проверил для четырех заключенных. Из 24 возможных способов разместить шары с номерами по ящикам выигрывают 10, вероятность 0.41(6)

[Henrylee]

MGM писал(а):

Что делать если обнаруженный чужой номер соответствует номеру ящика не знаю. По моему просто выйти из игры. Если кто знает поправьте.

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

[TOTAL]

Если правильно понимаю условие, для 8 ящиков 36.5% выигрышей.
Для 100 ящиков 31.18278209%

[MGM]

TOTAL писал(а):

Если правильно понимаю условие, для 8 ящиков 36.5% выигрышей.
Для 100 ящиков 31.18278209%

а как это доказать? Статистические результаты я и сам видел. Соображение таково, что любую комбинацию из 100! можно привести к исходному порядку путём бинарных перестановок за менее чем 50 шагов (даже не гипотеза, а что-то вроде внутреннего голоса). Если использовать условные вероятности...., короче пока не знаю.

[TOTAL]

MGM писал(а):

TOTAL писал(а):

Если правильно понимаю условие, для 8 ящиков 36.5% выигрышей.
Для 100 ящиков 31.18278209%

а как это доказать?

$$P=1-\left( \frac{1}{51}+\frac{1}{52}+ \cdots + \frac{1}{100} \right) $$

[MGM]

TOTAL писал(а):

MGM писал(а):

TOTAL писал(а):

Если правильно понимаю условие, для 8 ящиков 36.5% выигрышей.
Для 100 ящиков 31.18278209%

а как это доказать?

$$P=1-\left( \frac{1}{51}+\frac{1}{52}+ \cdots + \frac{1}{100} \right) $$

Спасибо! Буду переваривать на своём полу дилетантском уровне.

Добавлено спустя 1 час 39 минут 12 секунд:

TOTAL писал(а):

$$P=1-\left( \frac{1}{51}+\frac{1}{52}+ \cdots + \frac{1}{100} \right) $$

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

[PAV]

TOTAL писал(а):

$$P=1-\left( \frac{1}{51}+\frac{1}{52}+ \cdots + \frac{1}{100} \right) $$

Я лично не понимаю, откуда эта формула и что она означает.

[TOTAL]

PAV писал(а):

TOTAL писал(а):

$$P=1-\left( \frac{1}{51}+\frac{1}{52}+ \cdots + \frac{1}{100} \right) $$

Я лично не понимаю, откуда эта формула и что она означает.

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

$$C_{100}^{51} \cdot 50! \cdot 49! + C_{100}^{52} \cdot 51! \cdot 48! + \cdots + C_{100}^{100} \cdot 99! \cdot 0!$$

[ewert]

А какая будет вероятность, если им разрешат вскрывать только 20 ящиков (или, наоборот, только 80 -- лень думать)?

[TOTAL]

ewert писал(а):

А какая будет вероятность, если им разрешат вскрывать только 20 ящиков (или, наоборот, только 80 -- лень думать)?

Если 80 ящиков, то сумма просто укоротится. А вот если 20 ящиков, то подсчет усложняется до лень думать.

[ewert]

Ну это странно. Я ведь на что намекал. В какой момент (т.е. на каком к-ве ящиков) формула перестаёт работать и почему?