Pull to refresh

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

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

WARNING В коментах появилось два алгоритмических решения, одно вероятностное и одно лимитное. Плюс два-три читерских Есть еще несколько возможных ответах, основанных на довольно сложно поведении зэков. Также всем предлагаю формально оценить время выхода.
Спасибо xmolex за указание возможного первоисточника! По ссылке — фундаментальный pdf-файлик с 10 решениями и математической оценкой каждого из них!
UPD вопли «боян» набирают мощь, и не зря — вот та же задача на Эрудиторе, на Московской олимпиаде и (о боже, позор моим поисковым скилам) на Хабре от юзера ttim
UPD2: для тех кому эта задача и все её решения кажутся легкими, опубликовано продолжение с учетом помех.
Tags:заключенныезэки1 бит памятилампочказадачаузникилогикаlight bulb
Hubs: Entertaining tasks
Total votes 77: ↑65 and ↓12+53
Views3.5K

Popular right now

Top of the last 24 hours