| 9:53a |
Задачка
Для оживления коммьюнити вот еще одна задачка:
имеется тюрьма, в которой сидят по одиночным
камерам N заключенных. В тюрьме так же есть
комната с двумя рубильниками, у каждого
рубильника два положения (вкл/выкл), начальное
положение рубильников неизвестно.
Начальство тюрьмы собирает заключенных вместе
и говорит: я буду в некотором произвольном (не
обязательно случайном!) порядке водить каждого
из вас в комнату с рубильниками. При заходе в
комнату вы будете обязаны переключить ровно
один из рубильников (по вашему выбору). Как
только кто-то из вас при заходе в комнату определит
(по состоянию рубильников и собственной памяти),
что все ЗК уже в комнате побывали и скажет мне
об этом, то я вас отпущу. Сказать мне об этом
можно только один раз. Я гарантирую, что каждого
из вас будут водить в комнату достаточное
количество раз, чтобы определение присутствия
всех ЗК было возможным. Водить я буду вас по
одному и вы не сможете общаться между собой.
Я даю вам время сейчас всем вместе обсудить
стратегию.
Задача в том, чтобы придумать эту выигрышную
стратегию.
PS: Условие "достаточного количества вызовов" и
произвольности порядка вызова можно сформулировать
так: при стремлении к бесконечности общего числа
вызовов в комнату, число вызовов каждого конкретного
ЗК также стремится к бесконечности некоторым
произвольным (не обязательно случайным!) образом.
PPS: Комменты скринятся. |