[алгоритм] задача про лампочку и заключенных

клёво! наверно ответ на эту задачу как всегда не имеет никакого алгоритма...

бу-га-га

ответ есть, во всяком случае на упрощенный вариант достаточно простой, чтобы быть правильным, а на полный — моим знакомым дырок в алгоритме обнаружить не удалось

правда я не пробовал доказать, что мат. ожидание срока окончания этого процесса конечно при случайном тусовании заключенных, но весьма на это похоже.

ну боян же, один считает, остальные включают, выключают

> ну боян же, один считает, остальные включают, выключают

а полную версию?

да кстати и неполную тоже: если один включит, а другой выключит?

>Объяснение условия: нужна 100% уверенность в том, что заключенных не расстреляют

Ну не говорить «в этой камере побывали все заключенные», и все.

> Ну не говорить «в этой камере побывали все заключенные», и все.

есть более интересный вариант

> Ну не говорить «в этой камере побывали все заключенные», и все.

есть более интересный вариант вроде даже и с конечным матожиданием времени всеобщего освобождения

Эта задачка - фигня. Вот то же самое, но про заключённых эльфов (там ещё свет может случайно отключаться на случайные промежутки времени, надзиратель может лампочку от балды выключить) - вот это да. Это жесть была :)

...

Во:

1-го сентября 100 бессмертных эльфийских магаданских зэков (далее — эльфов) постоили на торжественную линейку и предложили им ускорить процесс своего освобождения.

Каждый день одного из них будут отводить в одиночную камеру для воспитательных работ. В камере есть абсолютно чистый стол, неспособный запачкаться и без тайников (впрочем, неважно), к тому же его периодически будут менять (впрочем, неважно).

На столе стоит настольная лампа. Каждый день эльф с охранником заходят в комнату, эльф садится, включает лампу, рисует, либо читает книгу, либо думает, либо делает что-либо еще (неважно). Далее по протоколу эльф обязан выключить лампу (должен, но иногда этого может не делать) и уйти с охраной. Охранник иногда проверяет и, если эльф не выключил лампу, он делает это за него (потому что был както в магаданской тюрьме инцидент). Охранник неаккуратный, ленивый, но иногда лампу он выключает (пусть и редко). Также иногда в тюрьме бывают перебои с электричеством, и в этот день никого в комнату не водят. В таких случаях лампочку переводят в положение «выключено». Эльфов выбирают абсолютно случайно. Каждый день водят не более одного.

У каждого заключенного тюремщик будет спрашивать: «А все ли твои товарищи тут были хотя бы раз?». Если он ответит «не знаю» («нет»), то игра продолжается. Если он ответит «да», и это неправда — высшая мера наказания для всех. Если каждый из сотни эльфов сказал «да», и это всегда была правда, всех всех выпускают на волю в тундру.

Примечание. Если эльф сказал «да», и это правда, его, как остальных, продолжают водить в эту камеру на общих правах.

Заключенные сидят в одиночных камерах и могут договориться только один раз — 1-го сентября на обеде после торжественной линейки. После этого они сидят в «одиночках» без окон, совсем не видят друг друга и лампочки.

-----

Вот это - жесть. (Да, задача имеет решения).

чем-то твоя задача реалистичнее, интересно, подумаю

однако есть и упрощения:

Каждый день водят не более одного.

>да кстати и неполную тоже: если один включит, а другой выключит?
тот который считает, он и выключает, каждый включает только один раз, если лампочка горит, то не трогают.

над остальными версиями лень думать, лучше решить реальную задачу.

за время предполагаемой жизни вселенной у меня не получается их освободить

если их водят действительно случайно — то можно

а если их водят не случайно, а так например что каждый заранее неизвесный период времени все точно все побывают в камере, но вредный надзиратель может специально неслучайно их водить, например из вредности всегда водить А перед Б, то решение есть?

и аналогичный вопрос — проверяющий охранник не выключает лампочку случайно, или из вредности имеет право взять и вдруг стать аккуратным?

«из вредности» означает, что он догадался про алгоритм заключенных, и сознательно противодействует ему, при этом, однако, выключая лампочку не более чем в 0.01% случаев за большой промежуток времени

> над остальными версиями лень думать, лучше решить реальную задачу.

ну и над упрощенной версией тоже было лень думать, так?

чем упрощённая реально отличается от неупрощённой (или там первого не обязательно на следующий день отправят в камеру)?

www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf

> З.Ы. интересно, кто автор задачи?
ганс рейзер не?

Эльфа выбирают случайно или нет? Если случайно, то стоит забить на все алгоритмы и т.п. и посчитать вероятность того, что все эльфы побывают в камере с учётом, что каждый раз выбирается один из (100 эльфов + 1 выключено) и решить какая доля вероятности всех устраивает, и после этого дня начать говорить, что все были :)

> чем упрощённая реально отличается от неупрощённой (или там первого не обязательно на следующий день отправят в камеру)?

не обязательно на следующий и не обязательно на день

> решить какая доля вероятности всех устраивает, и после этого дня начать говорить, что все были :)

не годится

зато можно придумать комбинацию, которая встретиться раз в (100!)*что-то-большое дней

вот я и спрашиваю — может ли охранник этому противодействовать

... 100 бессмертных эльфийских магаданских зэков... ?

>проверяющий охранник не выключает лампочку случайно, или из вредности имеет право взять и вдруг стать аккуратным?

Случайно. Охранник ничего не знает про заговор заключённых. Электрики и начальство тюрьмы - тоже :)

>100 бессмертных эльфийских магаданских зэков... ?

Да.

>Эльфа выбирают случайно или нет?

Случайно.

и решить какая доля вероятности всех устраивает

Нет, эльфов удовлетворяет только 100%-я гарантия :)

«Бессмертные» и «высшая мера» - это как деление на 0.

> Случайно. Охранник ничего не знает про заговор заключённых. Электрики и начальство тюрьмы - тоже :)

а у меня в полноценном варианте знает, и может вредничать. однако есть период, например год, за котороый он все же обязан сделать так, чтобы каждый побывал хотя бы один раз (однако этот период заключенным НЕ известен)

> www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf

там опять простая версия

а пдф-ка с кучей вариаций (со страницы http://math.stanford.edu/~dford/ ) не отдается — 403.

класс

если каждого могут держать не больше M дней, то вроде вероятность освободиться за NK дней
(1 - (1 / M ** K)) ** (N - 1) * (1 / M ** K)
и ожидание сходится.. ?

а если неограниченно, то ничего не получится у них

> а если неограниченно, то ничего не получится у них

я думаю, задача имеет смысл в условии «начальство установило максимальное число дней, которое может держать каждого вне камеры, но оно заключенным не известно»

по задаче KRoN73 вроде получается (может найду дырки) что-то порядка С*(100)^200 дней до освобождения, и при обязательном условии не-вредности начальства

а хотелось бы без этого условия

Вредный гражданин начальник будет гонять туда-сюда одного и того же длинноухого. И домой в итоге никто не пойдёт, как ни изворачивайся.

> Вредный гражданин начальник будет гонять туда-сюда одного и того же длинноухого. И домой в итоге никто не пойдёт, как ни изворачивайся.

начальство установило максимальное число дней, которое может держать каждого вне камеры, но оно заключенным не известно

при этом, однако, начальство, зная алгоритм, пытается помешать освобождению путем тасования заключенных в особом порядке

а, ну тогда да, каждый не может просидеть подрят больше M
только для 10 заключенных освободиться за миллион лет при M=10 вероятность у меня получается 1%

> а, ну тогда да, каждый не может просидеть подрят больше M только для 10 заключенных освободиться за миллион лет при M=10 вероятность у меня получается 1%

допустим, начальство для себя решило, что будет прогонять *всех* заключенных через камеру каждые Х дней (или раньше)

я щас подтормаживаю и легко ошибиться могу, но в полном варианте моей задачи гарантированный срок освобождения че-то 100Х или 200Х

гм

а какое решение задачи ? я так решил: нужно найти период из K дней, когда каждый отсидел ровно один день, тогда гарантия, что отсидели все.

(почитаю завтра по ссылкам внимательно :)

соотв. вероятность, что каждый отсидит 1 день за период K дней
P1 = 1 / (X - (K - 1)) ** K
делим всё на периоды по K дней, вероятность, что на N-й период наконец получится
P2 = ((1 - P1) ** (N - 1)) * P1
так?

тогда выходит довольно странно.. если K = 10, X = 20, то график P2(количество лет) получается примерно такой:

http://omploader.org/vM3Jqaw/Screenshot.png

я где-то ошибаюсь?

Напомнило SuperJail. Пересмотреть, что ли.

При планировании эльфы рассчитываются по порядку [0..n). Время делится на фиксированные периоды. В период i эльф (i mod n) всегда включает лампочку. Алгоритм для остальных:

• Если 1-й день периода и лампочка включена: выключить лампочку.
• Если не 1-й день периода и лампочка включена: посчитать эльфа (i mod n).
• Иначе: оставить лампочку в том же состоянии, как была.

Как только все камрады посчитаны, можно смело говорить «да».

хорошо

а теперь усложним задачу про эльфов: выбросим из условия «перебои с электроэнергией» (которые задачу не усложняют) и добавим: есть дни, когда никого из эльфов в камеру не водят, причем в эти дни лампочку возможно выключат, возможно не выключат; на количество этих дней подряд не наложено никакого ограничения (т.е. если применять описанный алгоритм, то может получиться, что в 1-й день нового периода лампочка горит, т.к. осталась гореть после старого периода)

хотя можно «перебои с электроэнергией» и оставить, но все равно добавить «дни, когда никого из эльфов в камеру не водят»

Задача из Baldur's Gate 2: Тебя и напарника злой маг посадил в соседние камеры. Звук изолирован, других каналов связи тоже нет. Если вы оба нажмете кнопку или оба не нажмете кнопку в течении десяти минут, то вы оба умрете. Если кнопку нажмет один из вас, то он один останется жить. Нажмете вы кнопку или нет?

> Нажмете вы кнопку или нет?

Хочешь жить - нажимай, не хочешь - не нажимай.

> Тебя и напарника ...

Кнопку жмет лидер партии.

>> Тебя и напарника ...

Кнопку жмет лидер партии.

Там ситуация чисто гипотетическая. Если скажешь что не нажмешь, назовут идиотом только и все.

Так ведь не все: монстряк в «самоотверженной» версии добрее.