И снова узники

[VVV]

  Найти эту вероятность нетрудно.

[Ленка Фоменка]

  Найти эту вероятность нетрудно.

[zhekas]

  Найти эту вероятность нетрудно.

Найдём вероятность что в перестановке есть цикл длиной k>50. Посчитаем их количество

для этого выберем k элементов. Это можно сделать C_100^k=100!/(k!*(100-k)!) способами. Дальше
расставим эти k элементов в цикле их можно расставить (k-1)! способами ну и оставшиес (100-k) элементов расставляются (100-k)! способами. Итого количество таких перестановок

(100!/(k!*(100-k)!))*(k-1)!*(100-k)!=100!/k

тогда вероятность цикла длины k равна (100!/k)/100!=1/k

и осталось просуммировать по всем k>50 и вычесть из 1

[zhekas]

Интересно что при любом, даже достаточно большом количестве заключённых
у них всегда есть шанс больше 30%  на выживание

[Илья]

Разобрались!

[BIVES]

А как доказать, что нет лучшей стратегии?

[BIVES]

Интересно что при любом, даже достаточно большом количестве заключённых
у них всегда есть шанс больше 30%  на выживание

Более того, если n стремится к бесконечности, а открывать можно n/2 конвертов, то вероятность будет стремится к 1.

[zhekas]

Интересно что при любом, даже достаточно большом количестве заключённых
у них всегда есть шанс больше 30%  на выживание

Более того, если n стремится к бесконечности, а открывать можно n/2 конвертов, то вероятность будет стремится к 1.

нет не будет. С ростом n она вероятность будет уменьшаться а предел равен 1-ln2

[VVV]

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

[Илья]

А в условии стоило более четко отметить, что выбираются ящики по очереди.

Куда уж более четче:

Каждый из них имеет право открыть одну за другой 50 коробок из ста.

[moonlight]

Допустим что узники ни о какой стратегии не договариваются а открывают коробки наугад. В этом случае вероятность для каждого открыть нужную коробку 50/100=1/2. Вероятность того что все 100 узников откроют коробки со своим именем (1/2)¹⁰⁰ или около 0.8*10^-30. Теперь пусть узникам будет позволено в случае угадывания своей коробки оставлять эту коробку открытой. В этом случае вероятность всем угадать свои коробки будет (50/100)*(50/99)*...*(50/51)=50⁵⁰*50!/100! или меньше чем 3*10^-9 и это верхний предел для любой стратегии.
Оптимальная стратегия здесь была указана и состоит в том что 50 узников открывают 50 любых коробок(все одни и те же) а остальные 50 узников те коробки которые не открывались первыми. Не знаю легко ли это доказать но экспериментально это вполне подтверждается. В этом случае вероятность равна (50!)²/100! или 10^-29. И эта формула тоже здесь была. По сравнению со случайным выбором вероятность выросла более чем в 10 раз но все равно несколько меньше чем 31%.