Вчера попалась интересная задчка про 100 заключенных и 100 ящиках.
Условия задачи
1. Действующие лица: Есть 100 заключенных, пронумерованных от 1 до 100,
и отдельная комната, в которой стоят 100 закрытых ящиков (они также
пронумерованы от 1 до 100).
2. Подготовка: Надзиратель случайным образом раскладывает в каждый ящик
по одной карточке с номером заключенного (все номера от 1 до 100
уникальны и перемешаны).
3. Процесс: Заключенные по очереди заходят в комнату. Каждый из них
может открыть не более 50 ящиков, чтобы попытаться найти карточку со
своим собственным номером.
4. Важные ограничения:
∙ Когда заключенный выходит из комнаты, он обязан
закрыть за собой все ящики и оставить их ровно в том же виде, в каком
они были.
∙ Заключенные не могут общаться друг с другом после
начала эксперимента, оставлять подсказки, менять карточки местами или
как-то помечать ящики.
∙ Свою стратегию они могут обсудить только заранее, до
того как первый человек зайдет в комнату.
Главное условие победы (или поражения)
∙ Победа: Если абсолютно все 100 заключенных найдут свои номера, их всех
отпускают на свободу.
∙ Поражение: Если хотя бы один заключенный не сможет найти карточку со
своим номером, казнят абсолютно всех.
При случайном (независимом) угадывании шансы на выживание ничтожно малы
и равны (1/2)^100, что составляет примерно (фактически ноль). Однако
существует математическая стратегия, которая поднимает вероятность
общего успеха до ~31,18%
