Тюремщик предлагает 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\%$, причём указанная стратегия выбора коробок является оптимальной. Посмотреть строгое доказательство оптимальности можно здесь.
Комментариев нет:
Отправить комментарий