Разберём задачу про радужных единорожек из этого поста. Задача — одна из версий известной задачи о 100 узниках и лампочке. Их довольно много, сложность зависит от исходных условий. Наши — весьма мягкие. 😃

Сначала кажется, что одна лампочка-радуга — это слишком маленький и простой носитель, чтобы хотя бы кто-то мог узнать информацию обо всех единорожках. Но на самом деле даже её будет достаточно, чтобы все единорожки спаслись. Им нужно придерживаться такого алгоритма:

1. Единорожку, которого привели в пещеру с радугой в первый день, будем называть «счётчиком». В своё первое посещение он должен выключить радугу (или не трогать, если она уже выключена), а в уме запомнить число 1.
2. Все остальные единорожки будут называться «наблюдатели». Они не могут выключать радугу. Когда наблюдатель заходит в пещеру, сначала он должен проверить, горит ли радуга. Если горит, то он ничего не делает. Если не горит, то он должен включить её, но только в том случае, если раньше не включал. То есть наблюдатель должен включить радугу лишь один раз, а при последующих заходах в пещеру — просто любоваться ею.
3. Каждый раз, когда счётчик заходит в пещеру, он должен посмотреть, горит ли радуга. Если радуга горит, то этот единорожка выключает её и прибавляет к числу, которое запомнил в прошлый раз, единицу.
4. Когда число, которое помнит счётчик, становится равно 777, он говорит, что все побывали в пещере, и злой волшебник, скрипя зубами, отпускает бедных единорожек на свободу.

А теперь давайте разберемся, как это работает!
Если каждый день выбирается случайный единорожек для похода в пещеру, то может случиться, что кто-то из них дооооолго туда не попадёт, а другие уже побывают несколько раз. Но единорожки бессмертны, а условие гарантировало нам, что все они в какой-то момент окажутся в пещере, так что нужно просто дождаться. Время — не проблема. 😊

Каждый раз после первого, когда «счётчик» заходит в комнату и видит горящую радугу, это значит, что ее кто-то зажёг — ведь когда он уходил в прошлый раз, радуга не горела! Но кто же мог зажечь радугу? Только один из тех, кто раньше этого не делал. Когда счетчик дойдет до числа 777, это будет означать, все остальные 776 единорожек точно побывали в пещере хотя бы по одному разу. А значит, условие злого волшебника выполнено. Да здравствуют единорожки!