Территория Web 1.0 / Brainteasers

Сто заключенных и стакан

Вечером в общей камере оказалось сто заключенных.

Наутро их разведут по отдельным камерам, а дальше каждый день случайным образом будут выбирать одного из них и приводить в специальную камеру со стаканом, который может находиться в одном из двух положений: "донышком вверх" или "донышком вниз".
При попадании в камеру, заключенный может:

Пронаблюдать положение стакана.
Изменить положение стакана (перевернуть его).
Сказать фразу "тут все были".
После произнесения этой фразы, при условии, что к этому моменту каждый заключенный хоть раз побывал в камере, двери тюрьмы открываются. Если же условие не соблюдается, всех заключенных казнят.

Заключенные должны придумать, как же им действовать, чтобы в какой-то момент оказаться на свободе. Решение не должно быть вероятностным, то есть после произнесения фразы "тут все были" они должны выжить и выйти с вероятностью 1.

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

Подсказка
Ответ

13.12.2009