Еще одна сравнительно старая, но не очень известная задача.
Есть 100 узников. На 100 листах бумаги написалии их имена - одно имя на одном листе, каждое имя по одному разу. Затем эти листки положили в 100 абсолютно одинаковых коробок по одному листу в коробку, и поставили эти коробки в ряд. На следующий день узников по одному будут впускать в комнату, после чего узник будет иметь право открыть 50 коробок из 100. Если узник найдет свое имя, то все коробки закроют, и впускают следующего узника. Если же узник за 50 попыток не найдет свое имя, всех 100 узников казнят. При этом во время всего этого процесса у узников не будет никакого шанса общаться друг с другом, и сейчас у них последняя ночь, чтобы выработать стратегию.
Можете ли вы придумать стратегию, которая позволит узникам завтра с шансом не меньше 30% уйти живыми и невредимыми?
Есть 100 узников. На 100 листах бумаги написалии их имена - одно имя на одном листе, каждое имя по одному разу. Затем эти листки положили в 100 абсолютно одинаковых коробок по одному листу в коробку, и поставили эти коробки в ряд. На следующий день узников по одному будут впускать в комнату, после чего узник будет иметь право открыть 50 коробок из 100. Если узник найдет свое имя, то все коробки закроют, и впускают следующего узника. Если же узник за 50 попыток не найдет свое имя, всех 100 узников казнят. При этом во время всего этого процесса у узников не будет никакого шанса общаться друг с другом, и сейчас у них последняя ночь, чтобы выработать стратегию.
Можете ли вы придумать стратегию, которая позволит узникам завтра с шансом не меньше 30% уйти живыми и невредимыми?
Если узников всего 2. То они договариваются, что первый откроет первую коробку. Тогда если дошел ход до второго, то надо открывать вторую и вероятность выжить 50%.
Если узников 4, то первый открывает коробки 1 и тот номер, который был в первой коробке.
Второй открывает первую коробку и первую из неизвестных (2, если в первой коробке не 2; в противном случае 3).
Третий открывает первую коробку, однозначно понимает что открыли 1 и 2 узники и выбирает первую из оставшихся
Четвертый открывает первую коробку, однозначно понимает что открыли 1, 2 и 3 узники и выбирает оставшуюся.
Вероятность выжить (1/4 * 1+ 3/4 * 1/3) * ( 1/4 * 1/3 + 1/4*1 + 2/4 * 1/2) * ( 1/4 * 1/2 + 1/4 * 1/2 + 2/4 * 1) * 1 = 1/2 * 7/12 * 3/4 = 21.9%
Маловато конечно, но на этом источник мысли иссяк.
\sum_{k = 51}^{100} P(есть цикл длины k) = \sum_{k = 51}^{100} (C_100^k * (k - 1)! * (100 - k)!) / (100!) = \sum_{k = 51}^{100} 1/k ~ ln 2. Все, никакого тебе комплана.