Задача про зеков и лампочку.Пусть среди заключённых есть один с мозгами, развитыми чуть лучше чем у среднего громилы, например Энди Дюфрейн.
Энди будет рассуждать так…
У нас есть триггер (лампочка) он же ячейка памяти на один бит.
Понятно, что с одним триггером у нас нихрена не получится. Подумаем, что мы имеем ещё?
Во-первых, зеки, хоть и тупые, но некоторые тривиальные логические операции они выполнять могут. Например, запомнить, который раз его заводят в комнату с лампочкой. То есть каждый зек в состоянии выполнить роль триггера. А это уже что-то. Имеем ещё N однобитных ячеек.
Во-вторых, каждый громила в состоянии сосчитать от 1 до N, а это значит, что мы имеем «сумматор» или «сдвиговый регистр» на N бит.
Сумматор нам нужен всего один. Хорошо бы им был сам Энди, но тут мы упираемся в злокозненность начальника тюрьмы Нортона, который, точно, не отправит Энди первым в комнату с лампочкой.
К счастью, мы точно знаем, когда начнётся испытание и знаем, что на каждого испытуемого отводится один день.
Собственно, алгоритм...
Пусть первым (это узкое место рассуждений – он должен быть уверен, что он первый) в камеру попадает Рыжий. Он должен стать «сумматором». Если в камере лампочка горит, то он должен её выключить и добавить единицу к сумматору (вернувшись в камеру нарисовать чёрточку на стене).
Следующие участники должны сделать следующее:
Если он заходит и лампочка не горит и при этом он сам её ещё ни разу её не включал, то он её включает. Если же он уже включал лампочку, то не делает ничего.
Если же лампочка горит, то он тоже ничего делать не должен. Сигнал должен дойти до Рыжего.
Рыжий дожидается своей очереди и если видит горящую лампочку, то её выключает, а на стене своей камеры рисует вторую чёрточку.
Так может продолжаться долго. Сначала у Рыжего чёрточки на стене будут появляться почти при каждом посещении камеры. Потом реже и реже. Всё зависит от злонамеренности Нортона, который может хоть целый месяц ежедневно запускать в камеру какого-нибудь несчастного Брукса.
А всё это время Рыжий после каждого посещения камеры с лампочкой пересчитывает чёрточки на стене своей камеры. Когда их станет ровно столько, сколько зеков было в начале испытания, он может уверенно заявить, что в камере с лампочкой побывали все.
Развлечение это очень долгое. При честности Нортона (случайный выбор заключённых) число циклов будет в районе N и в каждом цикле примерно N испытаний. При десяти заключённых на это потребуется 3+ месяца, а при 100 заключённых уйдёт примерно под 30 лет.
Ещё Дюфрейн может поломать всю малину, проковыряв туннель, прикрытый постером с Ритой Хейворд, и свалить из тюрьмы подставив всех остальных.
Добавлено: [time]03 Декабря 2023, 13:16:24[/time]
Как я понимаю, ключевой момент "раз в день". То есть первый чувак точно знает, что он первый.
На самом деле это не важно.
Это важно. Я же говорю про начальные условия.
Либо изначально лампочка включена (этого нет в задаче), тогда сумматором может стать Энди Дюфрейн (например), в противном случае сумматором становится первый из зашедших в камеру с лампочкой. Но он должен быть уверен, что он первый.
Короче - надо знать начальное состояние лампочки (включена/выключена), про которое в задаче ничего нет.
Добавлено: 04 Декабря 2023, 17:51:35
Сейчас почитал формулировку этой задачи в википедии.
Там русским по белому написано, что изначально лампочка
ВЫКЛЮЧЕНА!!!
Тогда решение однозначное. Сумматором тогда можно назначить конкретного человека, например, Энди Дюффрейна.
В формулировке Anton Share указания на начальное состояние лампочки
НЕТ!Я, блин, целый вечер голову ломал
