1. Не знаю, можно ли считать подобный выход гарантированным, если нельзя гарантировать время выполнения.
Пусть есть n заключенных. Им надо выбрать одного главного.
Поведение обычного (не главного) заключенного:
Если выключатель выключен и этот заключенный ни разу его не включал, то он его включает. Если выключатель включен, либо заключенный уже включал его до этого, то ничего не делает.
Поведение главного:
При заходе в комнату смотрит, включен ли выключатель. Если выключен, ничего не делает. Если включен, то он его выключает и записывает себе, что в комнату зашел один новый заключенный.
В тот момент, когда он поймет, что заходили все n-1 заключенных, он говорит что все были.
Записан