Это очень известная задача, и решение легко найти. Сам я не знаю, смог бы её решить или нет, потому что даже не пытался. Но даже готовое решение нужно осмыслить.
В общем, в тюрьме находится 100 заключённых. Им объявлено, что начиная с завтрашнего дня каждый день одного из заключённых будут приводить в комнату с лампой. Лампа будет или включена, или выключена. Заключённый может на свой выбор: включить/выключить лампу, или ничего не трогать.
В любой день любой заключённый может сообщить охране: Всё, все 100 человек уже побывали в этой комнате. Если это действительно так, то всех заключённых освободят, иначе расстреляют.
Порядок, в котором заключённых будут приводить в комнату, не определён. Заключённые не знают, кого, когда и сколько раз водили в комнату. Они не могут обмениваться между собой никакой информацией.
У них есть только один вечер, чтобы договориться между собой о плане действий, а завтра начнётся первый день эксперимента.
Поначалу условие задачи повергает в шок. Отсутствует критически важная информация. Лампа может быть включена (1) или выключена (0), значит если её использовать как счётчик, то можно сохранить информацию только об одном визите. Как досчитать лампой до 100?
Если в задаче нет необходимой информации, это значит, что она спрятана в каком-то другом месте. В данном случае ресурсом являются заключённые и один из них может работать счётчиком. А другие заключённые могут хранить состояние 1/0 как "был в комнате/не был в комнате".
Смотрите: сначала была одна лампа, а теперь есть лампа, счётчик и 100 1-битных переменных. Это уже гораздо больше данных.
Так как общаться друг с другом заключённые не могут, весь обмен данными должен происходить через лампу. А лампа может сигнализировать только о двух состояних. Какие состояния это должны быть?
- Счётчик свободен (включена)
- Счётчик занят (выключена)
Давайте посмотрим: если заключённый заходит в комнату в первый раз и видит включённую лампу, значит, счётчик готов считать. Он выключает её, переводя в состояние "счётчик занят". Все заключённые, которые зайдут после него, не будут трогать лампу, а будут ждать, когда счётчик освободится.
Как только счётчик опять попадает в комнату и видит выключенную лампу, он видит, что посещение было. Он запоминает +1 посещение и включает лампу, давая всем остальным понять, что свободен, и можно регистрироваться дальше.
Теперь следующий, кто войдёт в комнату и увидит, что лампа горит, сможет зарегистрировать своё посещение. При этом мы исключаем тех, кто однажды уже регистрировался: они уже посчитаны, и сколько бы их ни приводили в комнату, они больше ничего не должны делать. Это вообще мишура для отвода глаз, т.к. они могли бы просто не приходить. Но раз их водят, то они просто ничего не делают, никак не влияя на подсчёт.
Тот, кто ещё не регистрировался, но увидел выключенную лампу, также не может ничего сделать: счётчик занят, и пока он не будет готов, все остальные будут посещать эту комнату сколько угодно раз, ничего не делая.
Итак, план такой:
- В первый день тот, кого вызовут, становится счётчиком. Он считает сам себя, и также включает лампу, если она выключена. Так он дает сигнал, что готов считать.
- Во второй и далее дни счётчик может попасть в комнату повторно. Если он видит, что лампа не горит (кто-то был здесь и выключил её), то он считает +1 и опять включает её.
- Во второй и далее дни все, кроме счётчика, поступают так: Если этот заключённый уже выключал лампу или лампа не горит, то он ничего не делает. Если лампа горит, то он выключает её, тем самым регистрируя своё посещение.
4. Когда счётчик накапливает 100 посещений, он может сказать об этом охране.
Решение задачи достаточно прямолинейное. Что удивительно, есть и другие решения, которые отличаются по сложности. Давайте ради интереса выясним, сколько минимально времени нужно заключённым, чтобы освободиться.
Во-первых, счётчику, чтобы досчитать до 100, нужно побывать в комнате минимум 100 раз. В самом идеальном варианте в комнату попадает счётчик, включает лампу, затем туда попадает один из заключённых, выключает лампу, затем опять счётчик и т.д. То есть нужно минимум 200 дней, чтобы все заключенные побывали по разу в комнате и счётчик их посчитал.
В худшем случае время может быть очень большим. Например, после счётчика в комнату водят и водят заключённых, а счётчика так и не водят. Тогда, чтобы сосчитать всего одного заключённого, ему придётся ждать и сотни и тысячи дней. В этом случае верхний предел нам неизвестен.
Если не ожидать от начальства тюрьмы каких-то специальных подлостей, то можно предположить, что заключённых просто выбирают случайным образом. Тогда у каждого заключённого будет вероятность 1/100, что его вызовут в каждый из дней. Значит, в среднем счётчик может попадать в комнату 1 раз в 100 дней, и чтобы сосчитать всех, ему понадобится примерно 100*100 дней, или 27 лет.
Вся подборка задач:
