Заключённые и телефоны-1

Задача. 50 заключённых будут рассажены по звуконепроницаемым одиночным камерам, из которых нельзя выходить. В каждой камере установлено два телефона: чёрный и белый. Как только заключённых рассадят по камерам, начальник тюрьмы позвонит в случайную камеру на чёрный телефон и спросит, на телефон какого цвета позвонить следующему заключённому. Получив ответ, тюремщик снова выбирает случайным образом камеру (равновероятно, то есть в одну камеру могут позвонить несколько раз подряд) и звонит в неё на телефон того цвета, который указал предыдущий заключённый.

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

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

Тюремщик звонит с переменным интервалом и неравномерно, поэтому время между двумя звонками всегда разное, и способа измерения времени не существует. Заключённые обладают хорошей памятью, то есть каждый помнит, на какой телефон сколько раз ему звонили. О какой стратегии необходимо договориться заключённым, чтобы выйти из тюрьмы через максимально короткое время?

About Andreï Kostyrka

Науколюб, грамматический нацист, антитеист. Пишу стихотворения, сочиняю музыку, верстаю книги, занимаюсь эконометрикой и настраиваю фортепиано.
Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *