Форум умных людей

В тюрьме находятся 100 заключённых, и король - любитель головоломок, решил помиловать их всех, если они выполнят одно задание.
В зале на длинном столе стоят 100 одинаковых коробок, выстроенных в ряд. В каждой из
них находится уникальное имя одного из 100 узников - причём имя каждого
из них находится в одной из этих коробок. Заключенных поочередно запускают в
зал. Каждый из них имеет право открыть одну за другой 50 коробок из ста.
Если хотя бы один из них не найдёт своего имени, все они будут казнены;
если же каждому удастся найти своё имя - всех выпустят на свободу.
Узники не имеют права и возможности  общаться друг с другом после
выхода из комнаты; никаких пометок в комнате делать нельзя;
перекладывать имена в коробках нельзя. Вообщем, каждый узник находит комнату в
точно том же состоянии, что и предыдущий. Единственная возможность
пообщаться - ДО испытания.
Придумайте стратегию, при которой вероятность выжить у узников будет максимальной. Какова эта вероятность?

Первые 50 открывают первые 50 коробок, остальные - последние 50 коробок.
Вероятность - (http://mathurl.com/3hco45y.png)

Нет, есть стратегия лучше.
Да и вероятность посчитана не правильно.

вероятность того что в первых 50 коробках находятся первые 50 узников равна

(50!)^2/(100!)
что меньше чем (1/2)^50

Я предлагаю такую стратегию:
1 ый открывает коробки  1-50
2 ой открывает коробки 51-100
3 ий открывает  коробки  1-50
4 ый открывает первые 51-100
...
99 ый открывает коробки  1-50
100 ый открывает коробки  51-100
Вероятность выжить
0.5⁵⁰*50!/(99*97*95*...*5*3*1)

фактически это тоже самое что предложил Umnik

и вероятность выжить равна (50!)^2/(100!)
что гораздо меньше (1/2)^50

как-то очень маловато

тоесть они просто обрекают себя на верную гибель

неправильно так как по вашей логике получится, что вероятность того, что в первых 100 коробках находятся первые 100 узников равна
(100!)^2/(100!)>1

правильно
(50!)/(100!)

это ваша логика

хорошо тогда найди вероятность, что первые 70 заключенных в первых 70 коробках

(70!)*(30!)/(100!)

понял был не прав

Блин, я условие неправильно прочитал :)
Поэтому и ошибся так сильно.

Подсказка:
Показать скрытый текст

Если считать что заключённые пронумерованы от 1 до 100
ящики пронумерованы от 1 до 100
и в ящиках лежат номера заключенных то
пронумерованные ящики с числами внутри это ничто иное как перестановка.
Если им повезёт и данная перестановка не имеет цикла длина которого больше 50 то они могут спастись. Действовать тогда надо так:

заключённый с номером i подходит к ящику с номером i смотрит на номер внутри ящика. Пусть будет j. Соответственно он идёт к ящику j  и так пока не найдёт свой номер или не истекут попытки

Дело за малым найти вероятно того что в перестановке нет цикла длина которого больше 50

А как посчитать вероятность? :-[

  Найти эту вероятность нетрудно.
(http://mathurl.com/3v7dd4r.png)

:roll: :roll: :roll:

Найдём вероятность что в перестановке есть цикл длиной 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

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

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

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

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

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

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

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

Допустим что узники ни о какой стратегии не договариваются а открывают коробки наугад. В этом случае вероятность для каждого открыть нужную коробку 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%.
 :D