Заключенные и переключатель
АлгоритмыВ тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу, и предложил следующие условия: «В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON/OFF (верх/низ). Вас будут в произвольном порядке по одному приводить в эту комнату и через несколько минут уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен сказать, что в комнате побывали все заключенные. Если он окажется прав — всех отпустят, если ошибется — вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные и что каждого из вас будут приводить туда снова и снова неограниченное число раз». После этого заключенным разрешили собраться и обсудить стратегию, потом развели по камерам. Что им нужно делать, чтобы гарантированно выйти на свободу?
Начальное положение переключателя не известно.
188 комментариев