Разгадка, в которую невозможно поверить: задача о 100 заключённых [Veritasium]
Вот сайт с шаурмой. Likes. Есть одна задачка с настолько неожиданным решением, что даже когда знаешь ответ, кажется, что он неверный. Думаешь, что посчитать такое невозможно. Чует, а сейчас мне мозг взорвешь. Если хочешь кучу комментариев и всех запутать, правильной дорогой идешь.
На эту тему уже есть ролики, но мне они кажутся либо некорректными, либо неполными. Поэтому в своем видео я решил дать максимально развернутое объяснение. Итак, задача. Допустим, у нас сотни заключённых. Они пронумерованы от 1 до 100. Листочки с этими номерами случайным образом прячут по коробкам в отдельной комнате. Заключённые заходят в комнату по одному и должны за 50 попыток найти коробку, в которой спрятан их номерок. После чего они выходят из комнаты, оставляя все так, как было до их прихода. Общаться с другими заключёнными нельзя.
Если каждый, попав в комнату, сумеет найти свой номер, то их всех отпустят. Но если хотя бы один не сумеет, то абсолютно всех ждет казнь. Перед тем как действо начнётся, заключённым разрешается обсудить стратегию, как же им следует поступить. Если открывать коробки в случайном порядке, то шанс найти свой номер у каждого будет 50 процентов. А значит, вероятность того, что справятся все 100 человек: 1/2 умножить на 1/2 умножить на 1/2 и так сто раз, или 1/2 в сотой степени.
Другими словами, ноль целых, 0, 0, 0, 0, 0, 0, 0, 0, всего 30 нулей, а потом 8. Для сравнения, вероятность успеха такого подхода ниже, чем у двух людей случайно подобрать одну и ту же песенку из всего песка на всех пляжах и во всех пустынях на планете. Но что, если существует стратегия, которая повысит шансы заключённых до 30 процентов? Стратегия, благодаря которой вероятность выйти на свободу увеличится на 30 порядков.
Это всё равно, что растянуть миллиметр до размера наблюдаемой вселенной. При этом договариваться они могут только заранее. Верны, и это точно возможно. Да, рассказывай! Тут нет никакого подвоха, просто для решения придется хорошенько погрузиться в математику. Так что же нужно будет делать заключённым? Если вы не знаете ответа, ставьте видео на паузу и попробуйте решить. Если не получается, не волнуйтесь, вы не одиноки. Даже автор загадки, информатик Питер Браммел Тирес, он сам не додумался до ответа. Решение подсказал его коллега.
Meet Our Sun опубликовал статью с этой задачей и в конце написал, что решение великодушно оставляет за читателями. Итак, рассказываю ответ. Представьте, вы заключённый. Зайдя в комнату, первое, что нужно сделать — открыть коробку, на которой написан ваш номер. Номерок внутри, скорее всего, будет другим, но это не страшно. Просто идите к коробке с найденным номером, посмотрите, что в ней — идите к коробке с номером, который был внутри, и так далее, пока не найдете записку с нужным числом.
Когда вы обнаружите свой номер, он получается отправит вас к той коробке, с которой вы начали, тем самым замыкая цикл номеров. И как только свой номер вы нашли, значит, в комнате вам делать больше нечего, можно выходить. Этот подход увеличивает вероятность того, что все 100 человек найдут свои номера, до 31 процента, а то и больше.
Сейчас говоришь в 3 случаях все найдут свой номер. Чу, как же это работает? Во-первых, обратите внимание, коробки можно рассматривать как звенья замкнутых цепочек. Самая короткая — эта коробка, в которой спрятан её же номер. Если заключённый номер один, открыв первую коробку, найдет листок с единицей, получается, коробка была частью цепи из одного звена. Звеньев цепочки может оказаться 2, например: 1 коробка отправит вас в 7, 7 — назад в 1.
Также возможны три звена, четыре или пять, сколько угодно вплоть до 100. Самая длинная последовательность включает в себя все 100 коробок, но, скорее всего, если раскладывать номера случайно, получится несколько циклов: одни короче, другие длиннее. Начиная с коробки под вашим номером, вы абсолютно точно оказываетесь в цикле, который закончится нужным вам числом. Найдёте вы его или нет зависит исключительно от того, сколько придется делать шагов. Если вам повезло, их не больше 50-ти — успех гарантирован. Но если 51 или больше, то ничего не получится.
Число коробок, который можно открыть, закончится раньше, чем вы найдете свой номер. Открывая первую коробку, вы оказываетесь на максимальном расстоянии от той, что вам нужно. Вам надо найти записку, которая приведет к этой первой коробке. И чтобы её отыскать, придётся пройти по всему циклу до самого конца. Если заключённые будут действовать по такому принципу, а в самом длинном цикле окажется 51 коробка, то проиграет не какой-то один заключённый, а каждый, чей номерок оказался в этой цепочке.
Они дойдут до предпоследней коробки, но на этом придётся остановиться. Вероятность того, что заключённые выйдут на свободу, равна вероятности того, что среди всех циклов не окажется ни одного длиннее 50 коробок. Я говорил, что это примерно один к трем. Но как тут посчитать? Давайте подумаем, сколько есть способов соединить сотню коробок в замкнутую цепь из 100 элементов.
Скажем, 1 отправляет к 2, 2 к 3, 3 к 4 и так далее до 100, которая возвращает нас к 1. Может получиться и более хаотично: коробка номер 5 отправит нас в 99, к 17 и так далее. Давайте последний будет номером 63 и от неё вернемся к коробке номер 5. Сколько же всего может быть вариантов в таких перестановках? Если коробок 101, мы можем открыть любую коробку и 100 во второй раз уж одно уже открыли любую из 99, следующее выбираем из 98 и так далее, пока не дойдем до последней, там выбора уже не будет. На последнее место встанет та коробка, которая осталась.
Итак, общее число комбинаций: это 100 умножить на 99, умножить на 98, на 97 и так далее до единицы. Иначе говоря, 100 факториал — это и есть число всех возможных цепочек из сотни коробок с записками. Но не стоит забывать, что в нашем случае мы говорим не о рядах чисел, а о цикле. И разные на первый взгляд последовательности могут оказаться одним и тем же. Например, два, три, четыре, пять — так до 100, и потом один — это то же самое, что один, два, три, четыре, пять — и так до 100.
Рядами мы можем записать сотню разных последовательностей. И просто начиная один и тот же цикл с разных мест, получается, что общее число циклов — это факториал 100 делить на 100. И какова вероятность того, что среди 100 случайно спрятанных записок окажется цикл в сотню коробок? Нужно взять общее число всех возможных циклов длины 100 — это 100 факториал, делить на 100 и разделить на количество всех возможных расположений номерков внутри коробок, то есть на 100 факториал.
У нас получится один к ста. Другими словами, с вероятностью в один процент случайно спрятанные по коробкам номерки образуют цикл длины 100. Этот результат можно обобщить: вероятность случайно получить цикл с 99, 199 и цикл из 98 коробок один к 98. Вероятность появления цепочки длиннее 50 вычисляем так: 1/51 плюс 1/52 плюс 1/53 и так далее. Складываем всё вместе и получаем шестьдесят девять сотых, 69 процентов вероятность проигрыша. 31 процент — вероятность успеха, то есть того, что циклов длиннее 50 не будет.
Все равно как-то не верится. Кажется, что это какая-то магия. С этой стратегией сотни заключенных больше шансов на победу, чем у двух человек, которые будут выбирать коробки случайно. Означает ли это, что теперь у каждого отдельного заключённого вероятность найти свой номерок стала выше? Нет, все те же 50 процентов. Заключённым по-прежнему разрешается открыть лишь половину коробок. Шансы остаются 50 на 50.
Вот только вероятность индивидуального успеха каждого участника теперь связана. Представим, что мы решили провести эксперимент тысячу раз. Если открывать коробки случайно, то чаще всего свой номер будут находить около 50 человек. Иногда их будет чуть больше, иногда чуть меньше. Но с нашей стратегией все заключённые найдут свои номера в 31 проценте случаев. А в 69 процентах нужную записку найдут менее 50 человек. Заключённые либо везёт всем сразу, либо неудачу терпит большинство.
Вот такой эффект у этой стратегии. А почему-то решил, что твой номер всегда будет в твоем цикле? Вот это я не понимаю. Это самый важный вопрос. Просто смотри, вполне может быть, что ты прошел весь цикл, но свой номер так и не нашел, потому что цикл не тот, и тебе придётся начинать новый. Этот момент смущает.
Вот она! Да-да-да, все задают один и тот же вопрос: с чего мы взяли, что начиная с коробки под твоим номером, ты гарантированно попадёшь в цикл, где есть бумажка с твоим номером? Давайте думать. Представьте, что мы нашли номерок 73. Это значит, что мы наверняка пойдём к коробке под номером 73. Получается, что записка и коробка с одним и тем же номером — это единый элемент. Словно деталька его. Все записки лежат по коробкам.
Вот я прячу записки в коробке случайным образом, и, как видите, мы физически не можем зайти в тупик. Нельзя открыть коробку и остановиться, ведь в каждой лежит номерок, который отправляет нас дальше. Напомню, что по условиям задачи все сто записок разложены по сотне коробок, то есть каждый номерок находится в какой-то коробке. Это значит, что каждый цикл неизбежно замкнется. Поэтому начиная с коробки под номером 73, я рано или поздно найду записку с номером 73, потому что так и только так я вернусь к 73 коробки и завершу цикл.
Что-то, ну, за начальник у них? Почему тюрьмой заведует какой-то математический разум с садистскими наклонностями? Кошмар! А что если какой-нибудь охранник проникся сочувствием к заключённым и заранее пробрался в комнату с коробками? Он может обеспечить им стопроцентный успех, поменяв записки всего в двух коробках. Среди 100 элементов может быть только один цикл длиннее 50. Его можно разбить пополам. Если поменять местами всего две записки, получится два цикла, каждая из которых короче 50.
А что если попался очень уж злобной охране, который разгадал план заключённых? Он может разложить записки так, чтобы наверняка получился цикл длиннее 50. Или что же тогда заключённые обречены? Удивительно, но нет. Чтобы исправить ситуацию, можно случайным образом изменить номера коробок, например, каждому номеру прибавить 5. Циклы образуются как за счет расположения записок, так и за счёт номеров на коробках. Изменить номера — по сути, это тоже самое, что перепрятать записки.
Расположение записок снова будет случайным, и вероятность успеха вновь станет примерно один к трём. А что случится, если увеличить число заключённых? Интересный факт: никто не знает, что будет, если взять больше людей. Вероятность стремится к пределу, упадёт до нуля. Чего ждать? Это мой друг Мэтт Паркер. Предположу, что на самом деле он имел ввиду, что мы ещё как знаем, что произойдёт в этом случае.
Возьмем тысячу человек. Каждому можно открыть 500 коробок. Кажется, что их шансы на успех гораздо меньше, но если посчитать, так же, как мы делали ранее, получится тридцать целых, 74 сотых процента — всего лишь на пол процента ниже, чем если заключенных 100. Возьмем миллион и посчитаем: тридцать целых, шестьсот восемьдесят пять тысячных процента. Для миллиарда вероятность почти та же. Правда, сам эксперимент займет куда больше времени.
Так вот, вероятность успеха заключённых действительно приближается к пределу. И каков же этот предел? Мы применяли формулу: 1 минус вероятность неудач — это 1/51 + 1/52 и далее до 1/100. Эту последовательность можно изобразить как сумму площадей прямоугольников. Проведем по их вершинам кривую — это график 1/x. Площадь под этой кривой от 50 до 100 будет примерно равна сумме площадей прямоугольников.
И чем ближе количество заключённых к бесконечности, тем меньше получается погрешность. Чтобы вычислить вероятность неудач, нам нужно всего лишь взять интеграл 1/x dx от 2 до n. Получится натуральный логарифм 2. Выходит, что вероятность успеха — один минус натуральный логарифм 2 — это около 30 целых, 7 десятых процента. В общем, неважно, сколько именно заключённых, вероятность успеха при использовании нашей стратегии всегда выше 30 процентов.
По ощущениям тут что-то не так. Сложно поверить, что 100 человек могут найти нужные записки, а теперь оказывается, что людей может быть и 1000, миллион, сколько угодно. Заключённые отыщут свои номера с вероятностью не меньше тридцати процентов. Красота этого подхода в том, как он связывает между собой шансы каждого человека. Вероятность найти свой номерок случайно — 50 процентов. Но если пользоваться нашей стратегией, то у всех, чьи номера оказались в одном цикле, вероятность успеха будет одинаковой.
Как только все записки разложены, вероятность закрепляется и равна либо ста процентам, либо нулю. С этой стратегией нельзя проиграть, не дотянув до победы буквально пару человек. Тут либо проигрывают из-за большинства, либо побеждают все. Переведено и озвучено студией Вверх Гайдар.