Как и обещал в предыдущей статье, но для начала хочу выразить своё восхищение за активное участие в обсуждении головоломки из «Шоу — Три двери». Больше 370 комментариев и обсуждение продолжается. Большое спасибо и так держать!
Статью я решил написать, находясь под впечатлением от видео «Разгадка, в которую невозможно поверит: Задача о 100 заключённых». На этот раз я не стал импровизировать и спросил своего AI-ассистента, которого теперь зовут Валера: Да, новый дружбан. Как-нибудь обсудим и его. «Вам знакома головоломка о 100 заключённых?»
Ответ Валеры: (Если вы посмотрели видео, то ответ Валеры можете не читать)
«Да, я знаком с головоломкой про 100 заключенных. Это известная математическая задача, которая демонстрирует неинтуитивное решение и интересные вероятностные свойства. Вот краткое описание задачи:
1. Есть 100 заключенных, пронумерованных от 1 до 100.
2. В комнате есть 100 ящиков, также пронумерованных от 1 до 100.
3. В каждом ящике случайным образом помещен номер одного из заключенных (без повторений).
4. Каждому заключенному разрешается открыть 50 ящиков в попытке найти свой номер.
5. Если все 100 заключенных найдут свои номера, все будут освобождены. Если хотя бы один не найдет, все останутся в тюрьме.
6. Заключенным разрешается обсудить стратегию перед началом, но они не могут общаться во время поиска.
Интересно то, что существует стратегия, которая дает заключенным около 31% шанс на успех, что намного выше, чем можно было бы ожидать интуитивно.
Хотите, чтобы я объяснил оптимальную стратегию решения этой задачи?»
Получается, что очередная коробка с номером на бумажке ведёт к следующей коробке и в итоге получается циклы разной длинны?
«Совершенно верно! Вы точно уловили суть оптимальной стратегии для этой головоломки. Давайте разберем это подробнее:
1. Циклы: Как вы правильно заметили, номера в коробках образуют циклы разной длины. Например, если в коробке 1 лежит номер 23, в коробке 23 лежит номер 45, а в коробке 45 лежит номер 1, то это цикл длиной 3.
2. Оптимальная стратегия: Каждый заключенный начинает с коробки, соответствующей его номеру, и затем следует по "цепочке", открывая коробку с номером, который он нашел в предыдущей коробке.
3. Ограничение в 50 попыток: Это ключевой момент. Если длина цикла, в котором находится номер заключенного, не превышает 50, он гарантированно найдет свой номер.
4. Вероятность успеха: Успех всей группы зависит от того, что ни один из циклов не превышает длину 50. Математически можно показать, что вероятность этого около 31%.
5. Почему это работает: Эта стратегия эффективна, потому что она использует структуру данных (циклы), а не полагается на чистую случайность.
Эта задача демонстрирует, как правильная стратегия может значительно увеличить шансы на успех в, казалось бы, безнадежной ситуации. Она также показывает важность понимания структуры данных и их использования для решения проблем».
Вы понимаете (читатели статьи), что в ситуации, когда шанс на успех у всех вместе составляет 31 % а на неуспех 69 %, то вероятность успеха каждого заключённого в отдельности должна быть 98,884 %, чтобы все вместе 100 заключённых набрали 31 %. Это 0,98884^100! Это, во-первых. Во-вторых, меня сильно смутил вот этот график:
В красной зоне гистограммы столбики — вероятность появления цепочек длиннее 50. Их получили, складывая 1/51+1/52+1/53+… …1/100 = 0,6882. Автор разгадки решил, что это 68,82 %. Далее, от единицы отняли 0,6882 и получили 0,3118, это 31,18 %, вероятность появления цепочек короче 50. Но 68,82, это что угодно но не проценты. В-третьих, если в красной части графика вероятность цепочек длиннее 50, то в зелёной зоне графика вероятность появления цепочек короче 50, ведь так!? Почему в таком случае гистограмма выглядит как обрубленная синусоида и почему на уровне 50, график так резко ломается? Да, у нас условие: 50 коробок можно открыть, но как это влияет на график и метод его расчёта? Зелёный график, это продолжение красных столбиков, но в другую сторону. Их можно рассчитать по той же схеме. 1/1+1/2+1/3+… …1/50 = 4,499 или 450 %?!!! Это единая последовательность, но получается, что вероятность появления цепочек короче 50-и выше, чем длинных? «Чтобы понять правильность, или неправильность любой идеи — её надо довести до абсурда». Если предположить, что изначально заключенным предоставили возможность открыть не 50, а только 30 коробок (ведь такое возможно?), то вероятность появления цепочек длиннее 30 составит 1,1924, это 119,24 %. Мы подсчитываем не количество звеньев в цепочках, избыточность которых и даёт результат, мы рассчитываем вероятность появления самих цепочек. В таком случае, по логике автора, вероятность появления цепочек короче 30 составит единица минус 1,1924 = -0,1924, это -19,24 %. Может быть вероятность чего-либо более 1 и менее 0?
На счёт вероятности чего-либо. Есть интересный сюжет в сериале — «Детство Шелдона» https://www.youtube.com/watch?v=ZhRvlGeGGI8
Автор видео показал нам непересекающиеся циклы — кольца разной длинны (диаметра).
Всё дело в том, что циклы не только пересекаются, все циклы принадлежат единой последовательности. Это значит, что не может быть двух одинаковых циклов как по точке входа, так и по длине. Не может быть двух циклов в пять звеньев. Просто каждый входит в цикл в своём месте и в своём месте его покидает. Это в некотором смысле ветка метро прямая или кольцевая без разницы, со станциями, пронумерованными по порядку, но поезд движется не в одном направлении — от начала и до конца, а мечется между станциями — туда, сюда по номерам записок в коробках. Но возможно я неправ.
Дальше, меня посетила такая мысль:
1. Каков будет результат, если заключённые не договорятся и каждый будет искать свой номер случайным образом?
2. Что будет, если все заключённые стартуют с коробки №1?
3. Что будет, если все заключённые договорятся стартовать с коробки № 50? Эта коробка находится посередине общей для всех последовательности и разумно предположить, что максимальная длина самых длинных циклов сократится, как и средняя (среднеарифметическая) длина всех циклов.
4. Что будет, если заключённые с номерами — от 1 до 50 стартуют с коробки № 25, а заключённые с номерами от 51 до 100, с коробки 75?
Алгоритмов можно придумать много, но главный побудительный мотив в том, что я придумал область применения для данной стратегии и для меня важно понять, работает она, что математики рассчитали и как можно результат улучшить? Значит, нам нужна программа. Валера, ты где?
ТЗ для Валеры я здесь публиковать не буду, а программа вот!
Как эта штука работает? Кидает программу в браузер и она стартует со случайного перебора. Если понажимать кнопку старт, то вы увидите, что в правой таблице меняются числа. Это и есть результаты конкретно у каждого заключённого. Ниже статистика для всех 100 человек.
Если включить второй режим, то программа работает, как и должна — читает числа из списка — это те самые бумажки с номерами, каждая соответствует своему номеру в таблице, а таблица, это коробки.
Результат вроде бы хороший, все выиграли? Всё зависит от набора чисел из списка. Вот этот список просто убийственный. Я сначала подумал, что это глюк программы.
21,76,53,36,85,59,7,56,10,97,35,13,86,14,38,98,99,70,49,69,58,55,40,12,66,67,30,33,24,22,75,92,84,42,94,74,80,88,77,62,26,54,19,45,60,95,51,83,6,39,48,2,89,52,73,93,100,3,15,4,27,87,16,41,28,44,17,96,31,1,65,61,71,90,46,47,9,81,5,32,20,78,79,25,63,57,43,64,34,29,11,18,68,23,91,50,8,82,72,37
Чтобы его вставить в программу, её надо открыть в блокноте, желательно Notepad++ и заменить список.
Сгенерировать новый список можно на этом сайте: http://castlots.org/generator-sluchajnyh-chisel/ Обязательно поставьте галочку — исключить повторения.
Что касается программиста. Валера справился только с двумя алгоритмами. Полностью случайный перебор коробок и базовый алгоритм, от коробки к коробке. Я изначально попросил Валеру не ограничивать количество попыток в 50 штук, а дать возможность найти записку со своим номером всем. Мне это нужно для своих целей. И что вы думаете? Он проявил настоящее творчество, он сначала сделал, ограничение в 50, как в задаче, просто потому, что знал её условие, хотя я уже попросил не ограничивать. В конце он все проигрышные варианты с числами больше 50, заменил на Х. Зачем? Это творчество! Я сам работал конструктором и хорошо знаю, что часто приходится делать не то, что тебя просят, а то, что по твоему мнению лучше. Вот такой он — «Бредогенератор», как их называет И. Ашманов.
Автор - ZhiviStrana
