Вот такую задачу мне вчера загадали в МФТИ:

Имеется 100 пожизненно заключенных. Администрация тюрьмы собирает всех их вместе и дает возможность всем им выйти из заключения. Условия:
Заключеные в течение неограниченного срока проводятся администрацией через одиночную камеру. Порядок пребывания в камере произвольный (в частности, в следующий раз туда может быть отправлен тот же человек). В камере можно только включить и выключить лампочку. Писать на стенах, частично выкручивать лампочку, ... невозможно. Светит ли лампочка видно только из этой камеры. Надзиратели лампочку не трогают (не включают и не выключают).
Если кто-то из заключенных скажет «в этой камере побывали все заключенные», и это правда, то всех заключенных выпускают. Если не правда — всех расстреливают.
Пока еще все заключенные вместе, они могут посовещаться и выбрать алгоритм(ы) поведения.

неизвесно ни состояние лампочки сейчас, ни сроки пребывания в камере
нужна 100% уверенность в том, что заключенных не расстреляют, однако вовсе не требуется, чтобы заключенные освободились *сразу*, как только все пройдут через камеру

Я еле-еле до ответа дошла х) С одной подсказкой х)