Вы, а вместе с вами еще 99 человек — узники, приговоренные к смертной казни. Начальник тюрьмы дает вам всем шанс избежать своей участи, но для этого нужно сыграть в необычную игру. Каждый заключенный, включая вас, пронумерован от 1 до 100. Есть закрытая комната с сотней ящиков, в которых в случайном порядке распределены дощечки с числами от 1 до 100. Узники входят в комнату по очереди, каждый из них может открыть ровно половину всех ящиков, 50 штук. Если в одном из них окажется дощечка с номером заключенного, то тот проходит дальше, а в комнату, приведенную к изначальному состоянию, заводят следующего узника. В чем же подвох? Свой номер должен найти каждый из 100 человек. Если же хоть один не найдет дощечку со своим номером, печальный конец ожидает всю сотню. Что же делать? По какой стратегии проверять ящики, если передать информацию следующему узнику никак нельзя?
Заключенные обсуждают свою стратегию перед тем, как один из них зайдет в комнату с ящиками
Человек, знакомый с концепцией подобных задачек, решит, что либо в условиях есть подвох, либо судьба заключенных воистину незавидна. Нетрудно посчитать, что будет, если каждый из них решит открывать ящики наугад. Первый найдет свою дощечку с вероятностью в 50%, как и второй, как и третий. Но вот совокупно их шансы будут стремительно падать: от 50% к 25%, затем к 12,5%, затем к 6,25%… Вероятность того, что каждый из 100 заключенных, открыв в случайном порядке половину ящиков, найдет там свой номер, равна примерно 0,0000000000000000000000000000008. Пугающее количество нулей после запятой, не так ли? Проще сказать, что это почти невозможно.
Однако в этой задаче нет подвоха. Нет хитрости, на которую просто нужно вовремя «обратить внимание». Зато есть стратегия, которая обеспечит узников хоть каким-то реальным шансом на общее выживание. Более того: если использовать ее, спасение уже не будет таким далеким и призрачным. Ведь шансы всех заключенных найти свой номер станут равны… 31%. Неплохо в сравнении с 30 нулями после запятой? Если таким же образом растянуть миллиметр, то он станет больше наблюдаемой Вселенной. Но что же это за стратегия? Прежде чем читать дальше, попробуйте прикинуть так и эдак. Узники договариваются о стратегии только один раз, после этого общаться они никак не смогут.
Для начала сразу отсечем «хитрое» решение проблемы. Есть одна лазейка, которую можно было бы использовать при определенных условиях. Заключенный, заходящий в комнату, может заранее договориться, что будет открывать строго первые 50 ящиков, и искать среди них не только свой номер, но и номер следующего заключенного. Если он там будет — заключенный не выйдет из комнаты долгое-долгое время, чтобы явно указать другим, что нашел дощечку с номером товарища. Если же номера следующего узника не будет в первых 50 ящиках, то заключенный выйдет сразу. Это решение опирается на два ненадежных фактора: оно предполагает, что узники заранее знают порядок, в котором их будут запускать в комнату, и что они могут сидеть там бесконечно долго, подсказывая союзникам. Зато вероятность выживания группы становится равной 50%.
Хитрость, впрочем, легко пресечь. А математическое решение задачи не требует уловок. И звучит оно так, приготовьтесь. Зайдя в комнату, узник должен сначала условно пронумеровать ящики. Именно ящики, не дощечки, лежащие в них. Затем заключенный должен открыть ящик с номером, соответствующим его собственному. Например, узник 50 открывает 50-й ящик. В ящике будет лежать дощечка со случайным номером от 1 до 100. Предположим, 30. Это число указывает на ящик, который заключенному нужно открыть следом. В 30-м ящике будет дощечка 48, в 48-м ящике будет дощечка 24… И т.д., и т.д., пока узник наконец не найдет свою собственную дощечку, замыкая условный «круг» из чисел.
Узник открывает ящики по очереди до тех пор, пока не найдет свою дощечку
Все. Это и есть решение. Если каждый из заключенных будет ему следовать, то их шанс выжить станет равен 31%. Но… Как это происходит? Почему такая простая вещь, как порядок открывания ящиков, может настолько серьезно повлиять на вероятности?
Что ж, попробуем разобраться в этом. Дело в том, что «соединяя» таким образом коробки и номерки, в них лежащие, мы создаем несколько замкнутых цепочек. Самая короткая возможная цепочка состоит из одной коробки — в ней лежит ее собственный номер. Цепочка побольше будет состоять из десяти чисел, указывающих друг на друга. Или 20. Или 33. Или 100, всех 100, хотя при случайной раскладке это маловероятно. Самое главное в этом не то, сколько конкретно в цепочке коробок с дощечками. Главное, что если цепочка не состоит из более чем 50 коробок… то все заключенные, входящие в цепочку, смогут найти свой номер.
Коробки и дощечки образуют замкнутые цепочки разной длины
Когда заключенный начинает свой «путь» от коробки со своим номером, он как будто оказывается в самом конце цепи, которая должна привести его к началу, к победе и свободе. Если коробок в цепи окажется 51, то ему не хватит буквально одного шага. Как не хватило бы и другой полусотне узников. Значит, теперь нам важна не случайная вероятность открывания коробок, а вероятность того, что при случайном распределении дощечек по коробкам они не образуют цепь из 51 числа или более.
Какова эта вероятность? Это довольно легко посчитать. Шанс того, что коробки и дощечки образуют цепь из 100, равен 1/100. Шанс того, что они образуют цепь из 99, равен 1/99. И т.д. Складываем дроби: 1/100 + 1/99 + 1/98… И так — вплоть до 1/51. В итоге получаем шанс примерно в 69%. Заметили? Если вычесть из 100% получившиеся 69%, то выйдет 31%. Тот самый 31% на общее выживание узников. Идея этой стратегии в том, что мы связываем успех разных заключенных в один общий. Либо мы следуем по циклу и находим дощечки… либо крах терпят все.
Источник фото на главной и на странице: Софья Тэвдой для «Научной России»