Проверяем решение задачи о 100 заключенных в D

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

Задача о 100 заключенных очень простая и придумана в 2003 году специалистом в области информатики Питером Мильтерсеном. Сама задача формулируется так:

В тюрьме есть 100 заключенных приговоренных к смерти. В качестве последнего шанса избежать своей участи, надзиратель всем заключенным предлагает сыграть в игру. Каждый заключенный одет в тюремную робу и на ней есть номер заключенного, от 1 до 100. Каждому заключенному разрешается войти в комнату в которой стоят ящики, пронумерованные как и заключенные, также от 1 до 100. В каждом ящике лежит одна бумажка со случайным числом от 1 до 100. Заключенному разрешается войти в комнату, и открыть не более 50 ящиков, и потом не нарушая порядка следования бумажек, закрыть все ящики (т.е. вернуть комнату в исходное состояние). Задача заключенного: используя оговоренное число попыток найти бумажку со своим номером, после чего заключенный покидает комнату и не может общаться с участниками подобной игры. Но при этом заключенные могут договориться между собой перед началом игры, а также ничего не могут поменять после похода в комнату.
Надзиратель пообещал заключенным, что если все из них найдут свои номера, то всех отпустят, но если хотя бы один из заключенных своего номера не найдет, то казнят всех.
Как следует поступить, чтобы максимально увеличить шансы на успех всех заключенных?

Описание задачи

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

Смотрите сами, если заключенным никто не помогает (к примеру нет своего в охране) и при этом надзиратель сам не жульничает, то вероятность успеха одного заключенного — 1/2 (либо ящик с нужной бумажкой нашли, либо нет), а всего участников — 100, и попытки одного участника не зависят от попыток остальных, вероятность же добиться успеха у всех заключенных является произведением вероятности успеха каждого отдельного взятого участника, т.е. вероятность успеха равна (1/2)¹⁰⁰ или примерно 0,0000000000000000000000000000008. Из-за такой малой вероятности ситуация кажется безнадежной.

Но, что если мы вам скажем, что есть способ, буквально следуя которому можно поднять вероятность успеха до величины свыше 30%?

Вы, наверное, нам не поверите, но способ до смешного прост. Всем заключенным перед входом следует договориться о том, что каждый из них будет следовать такой стратегии: после входа в комнату, заключенный откроет ровно ту коробку, номер которой указан на его робе. Скорее всего, открыв коробку, заключенный увидит бумажку на которой указан не его номер, однако, если номер действительно не тот, то заключенному следует открыть коробку, номер которой оказался на бумажке. Если заключенный открыл ящик с бумажкой не «своего номера», то он продолжает дальше, также открывая следующей коробку с номером на бумажке. Повторяя это циклически, либо до нахождения нужного номера, либо до окончания количества попыток заключенный заканчивает игру.

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

Но это действительно так! И именно в этом мы предлагаем убедиться на практике, но прежде рекомендуем оценить видео от Дерека Малера с канала Veritasium, переведенное студией Vert Dider, чтобы оценить всю прелесть решения и его объяснения.

А что мы будем делать?

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

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

import std.algorithm;
import std.random;
import std.range;
import std.stdio;


// количество заключенных в тюрьме
enum NUMBER_OF_PRISONERS = 100;
// количество ящиков с записками
enum NUMBER_OF_BOXES     = 100;
// максимальное количество попыток
enum NUMBER_OF_TRIALS    = 50;

Теперь создадим комнату с размещенными коробками или ящиками (нас тут интересуют только ящики) и обеспечим автоматическое распределение случайным образом бумажек. Сами числа на бумажках будем хранить в обычном статическом массиве, а номер коробки будет совпадать с номером элемента массива минус один:

// Ящики с записками, на которых записаны номера
class Boxes
{
	private {
		ubyte[NUMBER_OF_BOXES] _boxes;
	}

	this()
	{
		auto rng = Random(unpredictableSeed);
		
		_boxes = iota(ubyte(1), ubyte(NUMBER_OF_PRISONERS + 1))
			.array
			.randomShuffle(rng)
			.array[0..NUMBER_OF_PRISONERS];
	}

	// возвращает весь набор ящиков с записками
	auto boxes()
	{
		return _boxes;
	}

	alias boxes this;
}

Теперь создадим образцового заключенного, которого снабдим еще и алгоритмом с оптимальной стратегией, которую мы уже описали ранее:

// Заключенный
class Prisoner
{
	private {
		// Номер заключенного
		ubyte _number;
		// Удалось ли обнаружить номер ?
		bool _success;
	}

	this(ubyte number)
	{
		_number = number;
	}

	// Найти ящик по оптимальной стратегии
	bool findOwnNumber(ref Boxes boxes)
	{
		auto index = _number - 1;

		foreach (i; 0..NUMBER_OF_TRIALS)
		{
			auto e = boxes[index];

			if (e == _number)
			{
				_success = true;
				break;
			}

			index = e - 1;
		}

		return _success;
	}
}

Здесь мы создаем класс в котором две скрытые переменные: номер заключенного и логическая переменная, обозначающая добился ли он успеха в поиске. Метод findOwnNumber работает следуя алгоритму просмотра коробок: и начинается просмотр с номера, который был у заключенного, и проходит далее по всему массиву ящиков, переходя к каждый раз к коробке, номер которой оказывается на бумажке. И это продолжается до успеха или до исчерпания попыток.

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

// Вычислить сколько заключенных нашли свои номера
auto numberOfSuccessfulTrials()
{
	auto boxes = new Boxes;
	auto ps = iota(ubyte(1), ubyte(NUMBER_OF_PRISONERS + 1)).map!(a => new Prisoner(a));
	auto M = 0;

	foreach (p; ps)
	{
		if (p.findOwnNumber(boxes))
		{
			M++;
		}
	}

	return M;
}

Проводим масштабирование на целую серию из N испытаний:

// Провести несколько розыгрышей среди заключенных
auto trialRounds(uint N)
{
	auto M = 0;

	foreach (p; 0..N)
	{
		if (numberOfSuccessfulTrials == NUMBER_OF_PRISONERS)
		{
			M++;
		}
	}

	return M;
}

И теперь остается произвести сам вычислительный эксперимент на крупной выборке, взяв например, за основу 1000 попыток заключенных и посмотрев в скольких случаях они добивались успеха, и рассчитав вероятность из этих показателей:

void main()
{
	auto N = 1_000;
	auto M = trialRounds(N);

	writefln(`M = %d, N = %d, P {M | N} = %f`, M, N, float(M) / float(N));
}

Наш результат:

M = 323, N = 1000, P {M | N} = 0.323000

Весь код эксперимента:

import std.algorithm;
import std.random;
import std.range;
import std.stdio;


// количество заключенных в тюрьме
enum NUMBER_OF_PRISONERS = 100;
// количество ящиков с записками
enum NUMBER_OF_BOXES     = 100;
// максимальное количество попыток
enum NUMBER_OF_TRIALS    = 50;

// Ящики с записками, на которых записаны номера
class Boxes
{
	private {
		ubyte[NUMBER_OF_BOXES] _boxes;
	}

	this()
	{
		auto rng = Random(unpredictableSeed);
		
		_boxes = iota(ubyte(1), ubyte(NUMBER_OF_PRISONERS + 1))
			.array
			.randomShuffle(rng)
			.array[0..NUMBER_OF_PRISONERS];
	}

	// возвращает весь набор ящиков с записками
	auto boxes()
	{
		return _boxes;
	}

	alias boxes this;
}


// Заключенный
class Prisoner
{
	private {
		// Номер заключенного
		ubyte _number;
		// Удалось ли обнаружить номер ?
		bool _success;
	}

	this(ubyte number)
	{
		_number = number;
	}

	// Найти ящик по оптимальной стратегии
	bool findOwnNumber(ref Boxes boxes)
	{
		auto index = _number - 1;

		foreach (i; 0..NUMBER_OF_TRIALS)
		{
			auto e = boxes[index];

			if (e == _number)
			{
				_success = true;
				break;
			}

			index = e - 1;
		}

		return _success;
	}
}


// Вычислить сколько заключенных нашли свои номера
auto numberOfSuccessfulTrials()
{
	auto boxes = new Boxes;
	auto ps = iota(ubyte(1), ubyte(NUMBER_OF_PRISONERS + 1)).map!(a => new Prisoner(a));
	auto M = 0;

	foreach (p; ps)
	{
		if (p.findOwnNumber(boxes))
		{
			M++;
		}
	}

	return M;
}


// Провести несколько розыгрышей среди заключенных
auto trialRounds(uint N)
{
	auto M = 0;

	foreach (p; 0..N)
	{
		if (numberOfSuccessfulTrials == NUMBER_OF_PRISONERS)
		{
			M++;
		}
	}

	return M;
}


void main()
{
	auto N = 1_000;
	auto M = trialRounds(N);

	writefln(`M = %d, N = %d, P {M | N} = %f`, M, N, float(M) / float(N));
}

Как видите, нашим заключенным удалось добиться успеха в 32% случаев! Это выглядит невероятно, и если вас заинтересовала задача про 100 заключенных, то исчерпывающую информацию можно найти в видео от Veritasium или в статье Википедии.