Pull to refresh

Реши задачку, используя один бит памяти!

Reading time 1 min
Views 4.7K
image
Задача, подобная этой на использование совместных ресурсов:
1-го сентября 100 бессмертных эльфийских воркутинских зэков постоили на торжественную линейку и предложили им ускорить процесс своего освобождения. Итак, в тюрьме есть камера с висящей лампочкой. Лампочку можно включить или выключить. Каждый день, начиная с 1-го сентября тюремщик будет запускать одного заключённого в эту камеру. В этот момент зэк сможет увидеть, горит ли лампочка.
У каждого заключенного тюремщик будет спрашивать: «А все ли твои товарищи тут были хотя бы раз?» Если зэк отвечает «нет», игра продолжается.
Если зэк отвечает «да» и это правда — всех выпускают на волю в тундру. Если же это неправда — высшая мера наказания для всех.
Тюремщики могут выбирать заключенных вразброс и с повторениями. Заключенные сидят в одиночных камерах и могут договориться только один раз — 1-го сентября на обеде после торжественной линейки. После этого они сидят в «одиночках» без окон, совсем не видят друг друга и лампочки.
Найти оптимальную стратегию поведения каждого заключенного с тем, чтобы их выпустили пораньше.

WARNING В коментах появилось два алгоритмических решения, одно вероятностное и одно лимитное. Плюс два-три читерских Есть еще несколько возможных ответах, основанных на довольно сложно поведении зэков. Также всем предлагаю формально оценить время выхода.
Спасибо xmolex за указание возможного первоисточника! По ссылке — фундаментальный pdf-файлик с 10 решениями и математической оценкой каждого из них!
UPD вопли «боян» набирают мощь, и не зря — вот та же задача на Эрудиторе, на Московской олимпиаде и (о боже, позор моим поисковым скилам) на Хабре от юзера ttim
UPD2: для тех кому эта задача и все её решения кажутся легкими, опубликовано продолжение с учетом помех.
Tags:
Hubs:
+53
Comments 252
Comments Comments 252

Articles