Загадка, в которую невозможно поверить, даже если знаешь ответ [Veritasium]

Есть одна задачка с настолько неожиданным решением, что даже когда знаешь ответ, кажется, что он неверный.

Думаешь, что посчитать такое невозможно.

Чую ты сейчас мне мозг взорвешь.

Если хочешь кучу комментариев и всех запутать, правильной дорогой идешь.

На эту тему уже есть ролики, но мне они кажутся либо некорректными, либо неполными.

Поэтому в своем видео я решил дать максимально развернутое объяснение.

Итак, задача.

Допустим, у нас сотня заключенных.

Они пронумерованы от одного до ста.

Листочки с этими номерами случайным образом прячут по коробкам в отдельной комнате.

Заключенные заходят в комнату по одному и должны за 50 попыток найти коробку, в которой спрятан их номерок.

После чего они выходят из комнаты, оставляя все так, как было до их прихода.

Общаться с другими заключенными им нельзя.

Если каждый, попав в комнату, сумеет найти свой номер, то их всех отпустят.

Но если хотя бы один не сумеет...

то абсолютно всех ждет казнь.

Перед тем, как действо начнется, заключенным разрешается обсудить стратегию.

Как же им следует поступить?

Если открывать коробки в случайном порядке, то шанс найти свой номер у каждого будет 50%.

А значит, вероятность того, что справятся все 100 человек, одна вторая умножить на одну вторую, умножить на одну вторую, и так 100 раз.

Или одна вторая в сотой степени.

Другими словами, 0,00000000, всего 30 нулей, а потом 8.

Для сравнения, вероятность успеха такого подхода ниже, чем у двух людей случайно подобрать одну и ту же песчинку из всего песка на всех пляжах и во всех пустынях на планете.

Но что если существует стратегия, которая повысит шансы заключенных до 30%?

Стратегия, благодаря которой вероятность выйти на свободу увеличится на 30 порядков.

Это всё равно, что растянуть миллиметр до размера наблюдаемой Вселенной.

При этом договариваться они могут только заранее?

Верно.

И это точно возможно?

Да.

Рассказывай.

Тут нет никакого подвоха.

Просто для решения придется хорошенько погрузиться в математику.

Так что же нужно будет делать заключенным?

Если вы не знаете ответа, ставьте видео на паузу и попробуйте решить.

Если не получается, не волнуйтесь, вы не одиноки.

Даже автор загадки, информатик Питер Бро Милтерсон, сам не додумался до ответа.

Решение подсказал его коллега.

Милтерсон опубликовал статью с этой задачей, а в конце написал, что решение великодушно оставляет за читателями.

Итак, рассказываю ответ.

Представьте, вы заключённый.

Зайдя в комнату, первой нужно открыть коробку, на которой написан ваш номер.

Номерок внутри, скорее всего, будет другой.

Но это не страшно.

Просто идите к коробке с найденным номером.

Посмотрите, что в ней, и идите к коробке с номером, который был внутри.

И так далее, пока не найдете записку с нужным числом.

Когда вы обнаружите свой номер, он, получается, отправит вас к той коробке, с которой вы начали, тем самым замыкая цикл номеров и коробок.

Свой номер вы нашли, а значит, в комнате вам делать больше нечего, можно выходить.

Этот подход увеличивает вероятность того, что все 100 человек найдут свои номера до 31%.

Ты про всех сейчас говоришь?

В третий случай все найдут свой номер.

Чё?

Как же это работает?

Во-первых, обратите внимание, коробки можно рассматривать как звенья замкнутых цепочек.

Самая короткая – это коробка, в которой спрятан ее же номер.

Если заключенный номер один, открыв первую коробку, найдет листок с единицей, получается, коробка была частью цепи из одного звена.

Звенья в цепочке может оказаться два, например, первая коробка отправит вас к седьмой, а седьмая назад к первой.

Также возможны три звена, четыре или пять, сколько угодно, вплоть до ста.

Самая длинная последовательность включает в себя все сто коробок.

Но, скорее всего, если раскладывать номера случайно, получится несколько циклов.

Одни короче, другие длиннее.

Начиная с коробки под вашим номером, вы абсолютно точно оказываетесь в цикле, который закончится нужным вам числом.

Найдете вы его или нет, зависит исключительно от того, сколько придется делать шагов.

Если вам повезло, и их не больше 50, успех гарантирован.

Но если 51 или больше, то ничего не получится.

Число коробок, которые можно открыть, закончится раньше, чем вы найдете свой номер.

Открывая первую коробку, вы оказываетесь на максимальном расстоянии от той, что вам нужна.

Вам надо найти записку, которая приведет к этой первой коробке.

И чтобы ее отыскать, придется пройти по всему циклу до самого конца.

Если заключенные будут действовать по такому принципу, а в самом длинном цикле окажется 51 коробка, то проиграет не какой-то один заключенный, а каждый, чей номерок оказался в этой цепочке.

Они дойдут до предпоследней коробки, но на этом придется остановиться.

Вероятность того, что заключенные выйдут на свободу, равна вероятности того, что среди всех циклов не окажется ни одного длиннее 50 коробок.

Я говорил, что это примерно 1 к 3.

Но как тут посчитать?

Давайте подумаем, сколько есть способов соединить сотню коробок в замкнутую цепочку из 100 элементов.

Скажем, первая отправляет ко второй, вторая к третьей, третья к четвертой и так далее до сотой, которая возвращает нас к первой.

Может получиться и более хаотично.

Коробка номер 5 отправит нас к 99, к 17 и так далее.

Давайте последняя будет номером 63.

И от нее вернемся к коробке номер 5.

Сколько же всего может быть вариантов таких перестановок, если коробок 100?

Первой мы можем открыть любую коробку из сотни.

Второй, раз уж одну уже открыли, любую из 99.

Следующую выбираем из 98.

И так далее, пока не дойдем до последней.

Там выбора уже не будет.

На последнее место встанет та коробка, которая осталась.

Итак, общее число комбинаций — это 100 умножить на 99, умножить на 98, на 97 и так далее до единицы.

Иначе говоря, 100 факториал.

Это и есть число всех возможных цепочек из сотни коробок с записками.

Но не стоит забывать, что в нашем случае мы говорим не о рядах чисел, а о циклах.

И разные, на первый взгляд, последовательности могут оказаться одним и тем же.

Например, 2, 3, 4, 5, так до 100, и потом 1.

Это то же самое, что 1, 2, 3, 4, 5, и так до 100.

Рядами мы можем записать сотню разных последовательностей, просто начиная один и тот же цикл с разных мест.

Получается, что общее число циклов — это факториал 100 делить на 100.

А какова вероятность того, что среди 100 случайно спрятанных записок окажется цикл в сотню коробок?

Нужно взять общее число всех возможных циклов длины 100, это 100 факториал делить на 100, и разделить на количество всех возможных расположений номерков внутри коробок, то есть на 100 факториал.

У нас получится 1 к 100.

Другими словами, с вероятностью в 1% случайно спрятанные по коробкам номерки образуют цикл длины 100.

Этот результат можно обобщить.

Вероятность случайно получить цикл из 99 – 1 к 99.

Цикл из девяносто восьми коробок один к девяносто восьми.

Вероятность появления цепочки длиннее пятидесяти вычисляем так.

Одна пятьдесят первая плюс одна пятьдесят вторая плюс одна пятьдесят третья и так далее.

Складываем все вместе и получаем шестьдесят девять сотых.

Шестьдесят девять процентов – вероятность проигрыша, а тридцать один процент – вероятность успеха, то есть того, что циклов длиннее пятидесяти не будет.

Все равно как-то не верится.

Кажется, что это какая-то магия.

С этой стратегией у сотни заключенных больше шансов на победу, чем у двух человек, которые будут выбирать коробки случайно.

Означает ли это, что теперь у каждого отдельного заключенного вероятность найти свой номерок стала выше?

Нет, все те же 50%.

Заключенным по-прежнему разрешается открыть лишь половину коробок.

Шансы остаются 50 на 50.

Вот только вероятность индивидуального успеха каждого участника теперь связаны.

Представим, что мы решили провести эксперимент тысячу раз.

Если открывать коробки случайно, то чаще всего свой номер будут находить около 50 человек.

Иногда их будет чуть больше, иногда чуть меньше, но с нашей стратегией все заключенные найдут свои номера в 31% случаев, а в 69% нужную записку отыщут менее 50 человек.

Заключенным либо везет всем сразу, либо неудачу терпит большинство.

Вот такой эффект у этой стратегии.

А почему ты решил, что твой номер всегда будет в твоём цикле?

Вот это?

Я не понимаю.

Это самый важный вопрос.

Просто смотри.

Вполне может быть, что ты прошёл весь цикл, но свой номер так и не нашёл.

Потому что цикл не тот.

И тебе придется начинать новый.

Этот момент смущает.

Вот.

Вот оно, да-да-да-да-да.

Все задают один и тот же вопрос.

С чего мы взяли, что начиная с коробки под твоим номером, ты гарантированно попадешь в цикл, где есть бумажка с твоим номером?

Давайте думать.

Представьте, что мы нашли номерок 73.

Это значит, что мы наверняка пойдем к коробке под номером 73.

Получается, что записка и коробка с одним и тем же номером — это единый элемент, словно деталька Лего.

Все записки лежат по коробкам.

Вот я прячу записки в коробке случайным образом, и, как видите, мы физически не можем зайти в тупик.

Нельзя открыть коробку и остановиться, ведь в каждой лежит номерок, который отправляет нас дальше.

Напомню, что по условиям задачи все 100 записок разложены по сотне коробок, то есть каждый номерок находится в какой-то коробке.

Это значит, что каждый цикл неизбежно замкнется.

Поэтому, начиная с коробки под номером 73, я рано или поздно найду записку с номером 73, потому что так и только так я вернусь к 73-й коробке и завершу цикл.

Что там за начальник у них?

Почему тюрьмой заведует какой-то математический разум с садистскими наклонностями?

Кошмар.

А что, если какой-нибудь охранник проникся сочувствием к заключенным и заранее пробрался в комнату с коробками?

Он может обеспечить им стопроцентный успех, поменяв записки всего в двух коробках.

Среди 100 элементов может быть только один цикл длиннее 50.

Его можно разбить пополам, если поменять местами всего две записки.

Получится два цикла, каждый из которых короче 50.

А что если попался очень уж злобный охранник, который разгадал план заключенных?

Он может разложить записки так, чтобы наверняка получился цикл длиннее 50.

И что же, тогда заключенные обречены?

Удивительно, но нет.

Чтобы исправить ситуацию, можно случайным образом изменить номера коробок.

Например, каждому номеру прибавить 5.

Циклы образуются как за счет расположения записок, так и за счет номеров на коробках.

Изменить номера коробок — это, по сути, то же самое, что перепрятать записки.

Расположение записок снова будет случайным, и вероятность успеха вновь станет примерно 1 к 3.

А что случится, если увеличить число заключенных?

Интересный факт.

Никто не знает, что будет, если взять больше людей.

Вероятностью стремиться к пределу?

Упадет до нуля?

Чего ждать?

Это мой друг Мэтт Паркер.

Предположу, что на самом деле он имел в виду, что мы еще как знаем, что произойдет в этом случае.

Возьмем тысячу человек, каждому можно открыть 500 коробок.

Кажется, что их шансы на успех гораздо меньше, но если посчитать так же, как мы делали ранее, получится 30,74%.

Всего лишь на полпроцента ниже, чем если заключенных 100.

Возьмем миллион и посчитаем 30,685%.

Для миллиарда вероятность почти та же, правда, сам эксперимент займет куда больше времени.

Так вот, вероятность успеха заключенных действительно приближается к пределу.

И каков же этот предел?

Мы применяли формулу 1 минус вероятность неудачи.

Это 1,51 плюс 1,52 и далее до 0,01.

Эту последовательность можно изобразить как сумму площадей прямоугольников.

Проведем по их вершинам кривую.

Это график 1 делить на х.

Площадь по этой кривой от 50 до 100 будет примерно равна сумме площадей прямоугольников.

И чем ближе количество заключенных к бесконечности, тем меньше получается погрешность.

Чтобы вычислить вероятность неудачи, нам нужно всего лишь взять интеграл 1 на х от n по 2n.

Получится натуральный логарифм двух.

Выходит, что вероятность успеха — единица минус натуральный логарифм двух.

Это около 30,7%.

В общем, неважно, сколько именно заключенных, вероятность успеха при использовании нашей стратегии всегда выше 30%.

По ощущениям, тут что-то не так.

Сложно поверить, что 100 человек могут найти нужные записки.

А теперь оказывается, что людей может быть и тысяча, и миллион, сколько угодно заключенных отыщут свои номера с вероятностью не меньше 30%.

Красота этого подхода в том, как он связывает между собой шансы каждого человека.

Вероятность найти свой номерок случайно — 50%.

Но если пользоваться нашей стратегией, то у всех, чьи номера оказались в одном цикле, вероятность успеха будет одинаковой.

Как только все записки разложены, вероятность закрепляется и равна либо 100%, либо 0%.

С этой стратегией нельзя проиграть, не дотянув до победы буквально пару человек.

Тут либо проигрывают из-за большинства, либо побеждают все.

Переведено и озвучено студией VRT Daider.