Задача о ста узниках
maximsidorovАлгоритм «100 заключённых»
Пример реализации и моделирования стратегии выживания заключённых в задаче "100 заключённых" на языке программирования Julia.
Введение
Алгоритм «100 заключённых» — это известная головоломка из теории вероятностей и комбинаторики. Она демонстрирует парадоксальную ситуацию, в которой использование определённой стратегии значительно повышает шансы на успех (по сравнению со случайным подбором), хотя интуитивно кажется, что это невозможно.
Суть задачи:
У нас есть 100 заключённых, пронумерованных от 1 до 100, и 100 ящиков, также пронумерованных от 1 до 100, в каждом спрятана карточка с номером одного из заключённых (по одной карточке на каждого). Задача — обеспечить, чтобы все заключённые смогли найти свою собственную карточку, открыв не более чем 50 ящиков каждый.
Победа считается достигнутой тогда, когда все 100 человек находят свои карточки.
Возможны две стратегии: случайная и оптимальная:
- Случайная: каждый заключённый выбирает 50 ящиков случайным образом;
- Оптимальная ("циклический метод"): каждый начинает с ящика со своим номером и дальше переходит к ящику с номером той карточки, которую нашёл ранее.
Цель примера — продемонстрировать разницу между этими двумя подходами с помощью большого числа численных экспериментов.
Для использования внешних библиотек в Julia необходимо их предварительно установить:
import Pkg; Pkg.add("Random") # Библиотека для генерации случайных данных
Pkg.add("Formatting") # Библиотека для форматирования вывода
После этого подключаем нужные модули
using Random # Модуль для перемешивания массивов (shuffle!), получения случайных выборок (randperm)
using Formatting # Функциональность для красивого форматирования вывода (например, format(...))
Функция randomplay
Эта функция проводит большое количество симуляций, где заключённые используют случайную стратегию: они открывают 50 ящиков без какой-либо логики.
"""
randomplay(n::Int64, numprisoners::Int64=100)
Выполняет указанное число (n) симуляций ситуации задачи '100 заключенных',
используя СЛУЧАЙНУЮ стратегию поиска. Каждый заключённый открывает 50 случайных ящиков.
Возвращает процент случаев (из n попыток), когда все 100 заключённых нашли свои карточки.
"""
function randomplay(n::Int64, numprisoners::Int64=100)
pardoned = 0 # Счётчик успешных симуляций
for i in 1:n # Запускаем цикл по всем симуляциям
indrawer = collect(1:numprisoners) # Создаем список карточек внутри ящиков [1, 2, ..., 100]
shuffle!(indrawer) # Перемешиваем карточки (имитируем случайное распределение)
found_all = true # Предполагаем, что все найдут свои карточки
for prisoner in 1:numprisoners # Проходимся по каждому заключённому
found = false # Изначально считаем, что этот заключённый не нашёл карточку
# Выбираем 50 случайных номеров ящиков:
for reveal in randperm(numprisoners)[1:div(numprisoners, 2)]
if indrawer[reveal] == prisoner # Найдена карточка с нужным номером
found = true
break # Заключённый успешно закончил поиск
end
end
if !found # Если текущий заключённый НЕ нашёл, то ВСЯ группа проиграла
found_all = false
break # Больше играть нет смысла
end
end
if found_all # Если все справились, увеличиваем счётчик побед
pardoned += 1
end
end
return 100.0 * pardoned / n # Преобразовываем долю в процент
end
Функция optimalplay
Функция выполняет моделирование того же процесса, но уже использует оптимальную стратегию, основанную на циклическом переходе по номерам ящиков, соответствующих найденным значениям в них.
"""
optimalplay(n::Int64, numprisoners::Int64=100)
Выполняет указанное число (n) симуляций ситуации задачи '100 заключенных',
используя ОПТИМАЛЬНУЮ стратегию: каждый заключённый начинает с ящика своего номера и продолжает двигаться
по последовательности, где следующий номер берётся из найденной карточки.
Возвращает процент случаев (из n попыток), когда все 100 заключённых нашли свои карточки.
"""
function optimalplay(n::Int64, numprisoners::Int64=100)
pardoned = 0 # Счетчик успешных игр
for i in 1:n
indrawer = collect(1:numprisoners) # Инициализируем массив с номерами карточек
shuffle!(indrawer) # Раскладываем их случаем образом
found_all = true # Исходное допущение: все успешно
for prisoner in 1:numprisoners # Перебор заключённых
reveal = prisoner # Стартовый шаг: открываем ящик с номером самого заключенного
found = false
# Открываем до 50 коробок
for j in 1:div(numprisoners, 2)
card = indrawer[reveal] # Смотрим содержимое текущего ящика
if card == prisoner # Если там лежит искомая карточка – успех!
found = true
break
else
reveal = card # Переходим к ящику с тем номером, который мы только что увидели
end
end
if !found # Если кто-то провалился – вся группа теряет
found_all = false
break
end
end
if found_all # Если никто не ошибся – группа прошла проверку
pardoned += 1
end
end
return 100.0 * pardoned / n # Процент успешных игр
end
Моделирование и анализ результатов
const N = 100_000 # Число повторений моделирования (можно изменять)
println("Simulation count: $N") # Сообщение о количестве симуляций
println("Random play wins: ",
format(randomplay(N), precision=3), # Результат случайной стратегии с форматированным выводом
"% of simulations.")
println("Optimal play wins: ",
format(optimalplay(N), precision=3), # Результат оптимальной стратегии
"% of simulations.")
Мы рассмотрели два разных подхода к решению задачи “100 заключённых”:
-
случайный (неэффективный),
-
оптимальный (основанный на анализе циклов в перестановках).
Через большое число численных экспериментов (в нашем случае — сто тысяч) было наглядно показано, как отличаются вероятности выигрыша:
-
При полностью случайном поиске выигрыш маловероятен (около 0%);
-
При использовании циклической стратегии выигрыш возможен примерно в ~30–35% случаев.
Именно такой расчет позволяет понять важность математической оптимизации даже в таких "на первый взгляд хаотичных" системах. Эта задача служит прекрасной иллюстрацией теории графов и вероятностных стратегий.
Пример разработан с использованием материалов Rosetta Code