Тюремщик предлагает 100 узникам сыграть в следующую игру. В одной из комнат он поставит в ряд 100 коробок и случайным образом распределит по коробкам бумажки с именами узников (имена всех 100 узников различны, каждое имя попадёт ровно в одну из коробок).
Узники будут по одному заходить в комнату под присмотром тюремщика. После этого узник получает 50 попыток для того, чтобы найти в одной из коробок своё имя. Это означает, что он открывает любую коробку, читает имя на бумажке, кладёт бумажку обратно, закрывает коробку, выбирает следующую и так далее. После этого, независимо от результата, он возвращается к себе в камеру.
Если все узники найдут свои имена, тюремщик выпустит их на свободу, иначе они продолжат отбывать свои сроки. Узники могут собраться все вместе перед началом испытания и обсудить свою стратегию. После этого их разведут по камерам, и они больше не смогут общаться друг с другом вплоть до конца испытания.
Оставлять какие бы то ни было знаки в комнате с коробками нельзя, тюремщик строго за этим следит. Можно даже считать, что тюремщик подготовил 100 идентичных комнат с коробками (с одинаковым распределением бумажек по коробкам).
Если каждый узник будет выбирать очередную коробку случайным образом, он найдёт своё имя с вероятностью 1/2. Вероятность того, что все 100 узников найдут своё имя, равна 1/(2^100), т.е. ничтожно мала. Могут ли они увеличить вероятность выигрыша, выбрав правильную стратегию?
Решение
Для удобства обозначим узников A_1, A_2,..,A_{100}, а их имена заменим номерами 1,2,..,100
В поисках идей для решения, рассмотрим случай, когда узников всего четверо. Выбирая коробки случайным образом, они выиграют с вероятностью 1/16. Что будет, если они договорятся, что первые два узника проверяют первые две коробки, а третий и четвёртый - последние две? Очевидно, что если A_1 и A_2 найдут свои номера, то и A_3 и A_4 обязательно найдут свои номера, и узники выиграют.
Вероятность того, что номер 1 окажется в первых двух коробках, равна 1/2. Если номер 1 уже в одной из них, то вероятность того, что номер 2 окажется тоже среди первых двух коробок, равна 1/3, а общая вероятность выигрыша получается равна 1/2*1/3 = 1/6, что лучше, чем 1/16.
Разовьём эту идею дальше. Пусть теперь каждый узник руководствуется той информацией, которую он получил при открытии предыдущих коробок. К примеру, пусть узник A_i первой открывает коробку i. Если он нашёл в ней номер k \neq i, он открывает коробку k, и так далее.
Предположим, например, что узников 8, а номера распределены по коробкам следующим образом: (3,5,6,4,7,1,8,2). Эта перестановка разбивается на циклы (3,6,1), (5,7,8,2), (4). Наличие цикла означает, что, начав открывать коробки с одной из коробок из этого цикла, мы рано или поздно вернёмся к ней.
В нашем примере узники выигрывают, так как длина ни одного из циклов не превышает 4. Мы можем утверждать, что если 100 узников следуют нашему алгоритму, то они будут выигрывать тогда и только тогда, когда в попавшейся им случайной перестановке не будет циклов длиннее 50.
Вычислим вероятность того, что в случайной перестановке номеров 1,2,..,2n не окажется циклов длиннее n.
Всего существует (2n)! перестановок 2n номеров. Для того, чтобы получить цикл длиной k>n, мы должны выбрать k номеров, выстроить их в цикл, оставшиеся 2n-k номеров распределить по свободным позициям произвольным образом. Имея k номеров, мы можем выстроить их в цикл длины k ровно (k-1)! способами. Следовательно, количество перестановок с циклом длиной k>n равноC_{2n}^{k}(k-1)!(2n-k)! = \frac{(2n)!}{k!(2n-k)!}(k-1)!(2n-k)! = \frac{(2n)!}{k}Отсюда следует, что вероятность получить цикл длины k>n равна 1/k, а общая вероятность того, что в перестановке окажется цикл длиной больше n равна \sum_{k=n+1}^{2n}{1/k}.
Следовательно, вероятность выигрыша 100 узников оказывается равна1 - (1/51 + 1/52 + ... + 1/100) \approx 0.3118 = 31.18\% Для полноты картины посчитаем предел вероятности выигрыша узников при n, стремящемся к бесконечности. Поскольку я совершенно не помню мат. анализ первого курса, придётся сделать небольшой финт ушами. Запишем: \sum_{k=n+1}^{2n}{\frac{1}{k}} = \frac{1}{n+1}+...+\frac{1}{2n} = =(1 + \frac{1}{2}+...+\frac{1}{2n}) - (1 + \frac{1}{2}+...+\frac{1}{n}) = H_{2n} - H_n Здесь H_n - гармонические числа. Если верить Википедии, то частичные суммы гармонического ряда и натуральный логарифм связаны соотношением \lim_{n \to \infty}{(H_n - \ln{n})} = \gamma,где \gamma - постоянная Эйлера-Маскерони. Поэтому \lim_{n \to \infty}(H_{2n}-H_n) = \ln{2n} - \ln{n} = \ln2 Таким образом, при больших n вероятность выигрыша узников равна 1 - \ln2 \approx 0.3069 Другими словами, при любом числе узников они выигрывают с вероятностью чуть большей, чем 30\%, причём указанная стратегия выбора коробок является оптимальной. Посмотреть строгое доказательство оптимальности можно здесь.
Узники будут по одному заходить в комнату под присмотром тюремщика. После этого узник получает 50 попыток для того, чтобы найти в одной из коробок своё имя. Это означает, что он открывает любую коробку, читает имя на бумажке, кладёт бумажку обратно, закрывает коробку, выбирает следующую и так далее. После этого, независимо от результата, он возвращается к себе в камеру.
Если все узники найдут свои имена, тюремщик выпустит их на свободу, иначе они продолжат отбывать свои сроки. Узники могут собраться все вместе перед началом испытания и обсудить свою стратегию. После этого их разведут по камерам, и они больше не смогут общаться друг с другом вплоть до конца испытания.
Оставлять какие бы то ни было знаки в комнате с коробками нельзя, тюремщик строго за этим следит. Можно даже считать, что тюремщик подготовил 100 идентичных комнат с коробками (с одинаковым распределением бумажек по коробкам).
Если каждый узник будет выбирать очередную коробку случайным образом, он найдёт своё имя с вероятностью 1/2. Вероятность того, что все 100 узников найдут своё имя, равна 1/(2^100), т.е. ничтожно мала. Могут ли они увеличить вероятность выигрыша, выбрав правильную стратегию?
Решение
Для удобства обозначим узников A_1, A_2,..,A_{100}, а их имена заменим номерами 1,2,..,100
В поисках идей для решения, рассмотрим случай, когда узников всего четверо. Выбирая коробки случайным образом, они выиграют с вероятностью 1/16. Что будет, если они договорятся, что первые два узника проверяют первые две коробки, а третий и четвёртый - последние две? Очевидно, что если A_1 и A_2 найдут свои номера, то и A_3 и A_4 обязательно найдут свои номера, и узники выиграют.
Вероятность того, что номер 1 окажется в первых двух коробках, равна 1/2. Если номер 1 уже в одной из них, то вероятность того, что номер 2 окажется тоже среди первых двух коробок, равна 1/3, а общая вероятность выигрыша получается равна 1/2*1/3 = 1/6, что лучше, чем 1/16.
Разовьём эту идею дальше. Пусть теперь каждый узник руководствуется той информацией, которую он получил при открытии предыдущих коробок. К примеру, пусть узник A_i первой открывает коробку i. Если он нашёл в ней номер k \neq i, он открывает коробку k, и так далее.
Предположим, например, что узников 8, а номера распределены по коробкам следующим образом: (3,5,6,4,7,1,8,2). Эта перестановка разбивается на циклы (3,6,1), (5,7,8,2), (4). Наличие цикла означает, что, начав открывать коробки с одной из коробок из этого цикла, мы рано или поздно вернёмся к ней.
В нашем примере узники выигрывают, так как длина ни одного из циклов не превышает 4. Мы можем утверждать, что если 100 узников следуют нашему алгоритму, то они будут выигрывать тогда и только тогда, когда в попавшейся им случайной перестановке не будет циклов длиннее 50.
Вычислим вероятность того, что в случайной перестановке номеров 1,2,..,2n не окажется циклов длиннее n.
Всего существует (2n)! перестановок 2n номеров. Для того, чтобы получить цикл длиной k>n, мы должны выбрать k номеров, выстроить их в цикл, оставшиеся 2n-k номеров распределить по свободным позициям произвольным образом. Имея k номеров, мы можем выстроить их в цикл длины k ровно (k-1)! способами. Следовательно, количество перестановок с циклом длиной k>n равноC_{2n}^{k}(k-1)!(2n-k)! = \frac{(2n)!}{k!(2n-k)!}(k-1)!(2n-k)! = \frac{(2n)!}{k}Отсюда следует, что вероятность получить цикл длины k>n равна 1/k, а общая вероятность того, что в перестановке окажется цикл длиной больше n равна \sum_{k=n+1}^{2n}{1/k}.
Следовательно, вероятность выигрыша 100 узников оказывается равна1 - (1/51 + 1/52 + ... + 1/100) \approx 0.3118 = 31.18\% Для полноты картины посчитаем предел вероятности выигрыша узников при n, стремящемся к бесконечности. Поскольку я совершенно не помню мат. анализ первого курса, придётся сделать небольшой финт ушами. Запишем: \sum_{k=n+1}^{2n}{\frac{1}{k}} = \frac{1}{n+1}+...+\frac{1}{2n} = =(1 + \frac{1}{2}+...+\frac{1}{2n}) - (1 + \frac{1}{2}+...+\frac{1}{n}) = H_{2n} - H_n Здесь H_n - гармонические числа. Если верить Википедии, то частичные суммы гармонического ряда и натуральный логарифм связаны соотношением \lim_{n \to \infty}{(H_n - \ln{n})} = \gamma,где \gamma - постоянная Эйлера-Маскерони. Поэтому \lim_{n \to \infty}(H_{2n}-H_n) = \ln{2n} - \ln{n} = \ln2 Таким образом, при больших n вероятность выигрыша узников равна 1 - \ln2 \approx 0.3069 Другими словами, при любом числе узников они выигрывают с вероятностью чуть большей, чем 30\%, причём указанная стратегия выбора коробок является оптимальной. Посмотреть строгое доказательство оптимальности можно здесь.
Комментариев нет:
Отправить комментарий