задачка №2, посложнее

[109]

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

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

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

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

главный вопрос: каков алгоритм действий пользователей ЖЖ, приводящий к успеху? бонус вопрос: сколько им в среднем придётся просидеть в тюряге? гм... слово "в среднем" здесь, наверное, не очень уместно... каково мат. ожидание срока, который им придётся отсидеть при условии, что следователь не напрягается и допрашивает каждый день только одного человека пользователя ЖЖ.

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

да и вот ещё... комменты типа "эта задачка для 6 класса" без решения, или "эту задачку я уже видел [в интернете|в ЖЖ|где-то|в Ж]" я, пожалуй, буду удалять даже не расскринивая.

Update: победители (в порядке поступления):

sply

Update #2: Приём решений прекращаю (за исключением апдейтов типа мат. ожидания времени отсидки), комменты расскриниваю.

Comments

[puzanov.livejournal.com]

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

[puzanov.livejournal.com]

Сори, опечатка. "... который будет всегда ВЫКЛЮЧАТЬ..."

[109.livejournal.com]

направление мысли правильное - но так, как вы сформулировали, работать не будет (сразу две ошибки, не считая описки).

[upstartn.livejournal.com]

Юзеры сговариваются, что кто-то из них будет "счетчиком".
Остальные придерживаются следующего правила:
если юзер в комнате первый раз, то, если лампочка не горит он ее зажигает, иначе ничего не делает
"счетчик", попадая на допрос, гасит лампочу и прибавляет 1 в уме
когда "счетчик" доходит до N (число юзеров), то он говорит, что, мол, ВСЕ

не помню как считать мат. ожидание :-) ?

[dvurukov.livejournal.com]

Мне кажется, что состояние лампочки нужно менять только в том случае, когда юзер приходит в первый раз - все последующие свои приходы он не должен менять состояние лампочки. Все юзеры знают, в каком состоянии была лампочка в начале. Каждый пользователь, всякий раз приходя на допрос, должен замечать состояние лампочки и считать сколько раз оно менялось. Как только
он насчитает 10 смен, включая свое переключение, он должен сказать:
"вы уже всех вызывали, и никто не раскололся, так что отпускайте нас" :-).
Про ожидание точно не помню... кажется (N+1)/2 - тогда каждого наиболее вероятно вызовут 55 раз, то есть около 55 дней им там сидеть :-) - хотя в бонусе могу ошибаться :-) не судите строго - любил пить пиво на теорвере :-)

[alexeyten]

1. Пусть изначально лампа выключена.
Алгоритм действия:
- Все, кроме Васи, зажигают лампу, если видят выключенную лампу впервые.
- Вася выключает лампу.
- Как только Вася выключает лампу в девятый раз, он требует освобождения.

2. Пусть изначально лампа включена.
Алгоритм действия:
- Все, кроме Васи, выключают лампу, если видят включенную лампу впервые.
- Вася включает лампу.
- Как только Вася включает лампу в девятый раз, он требует освобождения.

3. Начальное состояни неизвестно.
Алгоритм действия:
- Все, кроме Васи, зажигают лампу, если видят выключенную лампу впервые или во второй раз.
- Вася выключает лампу.
- Как только Вася выключает лампу в семнадцатый раз, он требует освобождения.

P.S. Что-то мне подсказывет, что в третьем случае можно освободится быстрее, но как-то не придумывается алгоритм.

так как?

[dvurukov.livejournal.com]

Ну так как, я правильно перед этим ответил или нет? :-)

[raa.livejournal.com]

фигассе, посложнее. короче есть решение в лоб. но преполагается, что как минимум один в день заходит, иначе сильно сложнее (предп.1) . назначается один, который типа главный и руку на пульсе держит. а все время бъется на промежутки, причем за каждый промежуток времени "отвечает" только один заключенный условно 10-й, из общих соображений берем промежуток равный 10 дням. суть такая: пусть в первый день (каждого промежутка) любой входящий выключает лампочку (предп.1). в теч. остальных 9 дней лампочка сначала выключена, и ее может включить только один из девяти, причем точно известно кто. тогда, если в этот промежуток зайдет 10-й и увидит включенную лампочку, он запомнит кто был, а лампу выключит. если он не зайдет, лампу выключат в первый день следующего промежутка. оценка по времени если очень грубая 500 дней. наверное можно играть с длиной промежутка, чтобы найти более оптимальный срок - но это уже мозги напрягать надо и теории вспоминать.

[raa.livejournal.com]

пока редактировал решение, напутал :) читать в такам порядке:
назначается один, который типа главный и руку на пульсе держит - условно 10й. а все время бъется на промежутки, причем за каждый промежуток времени "отвечает" только один заключенный. из общих соображений берем промежуток равный 10 дням.

[navy-99.livejournal.com]

Я пока могу придумать ответ для случая, когда в начальном состоянии лампочка выключена...
Пусть есть N пользователей.
Договор
1)Первый включает лампочку 2^0 раз
2)второй 2^1 раз
3)Третий 2^2 раз
...
Последний только выключает и запоминает выключения. Как только он выключит (2^N - 1) - (все единички) раз, то значит все были.
...

М.... если для случая с начальным неизвесным состоянием, то сдвигаем вправо, первый включает 2^1 раз, второй - 2^2 итд, сторож не смотрит на младший бит.

[http://users.livejournal.com/_dyn/]

При первом возвращении с допроса пользователь ЖЖ должен сменить состояние лампочки (с выкл на вкл или vise versa).
После трех смен состояния все пользователи были допрошены.

Среднее время, с учетом одного допроса в день = 5-6 дней (точнее 5,5 :)

[puzanov.livejournal.com]

Почему не сработает этот вариант? Человек, который выключает лампочки после десятого выключения смело может считать, что все остальные уже в камере были. Единственное условие: остальные пользователи должны договориться, что они включают лампочку только один раз. Если пользователь уже в камере был, то с лампочкой ничего делать не должен :)

А может быть так?

[lindenalee.livejournal.com]

Нужно проделать следующее:
1) выбрать главного в команде пользователейЖЖ. Главным становится тот, кто идет на допрос в первый день. Если лампа включена в этот первый день, он ее выключает .
Этот человек и собирает результирующуюю информацию.
2) Все, кто побывал на допросе должны сообщать об этом главному путем вклюючения лампы, но каждый, кто побывал на допросе должен включить лампочку только 1 раз. Попадая второй раз на допрос, лампу он не включат.
3) Выключать лампочку имеет право только главный
4) Включать можно только выключенную лампочку. Т.е. даже если пользователь жж попадает в первый раз, но лампочка уже горит, он не предпринимает никаких действий.
5) Когда главный понимает, что все побывали на допросе, он сообщает об этом и всех отпускают
Таким образом, основная идея состоит в том, что пользоваель жж включает лампочку, тем самым он сообщает главарю о том, что уже побывал на допросе, а выключение означает: "сообщение принял". Очевидно, что просидят там пользователи жж не менее 19 дней.

[pricolist.livejournal.com]

ГВ - главный выключальщик. Назначается собранием. Остальные выключать не могут
КОбщ - общее кол-во человек (после на раз два рассчитайсь :) )
ЖЖ - обыкновенный жж юзер
КВыкл - количество выключений

ЛАМПОЧКА (ЖЖ)
(
ЕСЛИ (ЖЖ = ГВ и СОСТ_ЛАМП = горит)
ТО (КВыкл++; СОСТ_ЛАМП = выключено)
ИНАЧЕ ЕСЛИ (ЖЖ еще не влючал не разу и СОСТ_ЛАМП = выключено) TO (СОСТ_ЛАМП <- горит)
)
ПОКА (КВыкл+1 < KОбщ)
(
ЖЖ<-rand; ЛАМПОЧКА (ЖЖ)
)

[ruundii.livejournal.com]

предположим что лампочка изначально включена

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

возможно, неоптимально, но...

[contras.livejournal.com]

Раз их 10 человек, то мерять срок будем интервалами по 10 дней. В самый первый день допросов самый первый допрашиваемый пользователь лампочку выключает. Десятидневка считается "чистой", если в течении её ни одного пользователя не вызвали на допрос дважды или более раз. Если всё-таки вызвали, то в свой второй допрос пользователь лампочку включает (флаг "грязной" десятидневки). Каждый n*10 день допрашиваемый в этот день юзер анализирует состояние лампочки. Если она погашена, то за прошедшие до этого 9 дней текущей десятидневки успели по одному разу допросить остальных юзеров, значит можно смело делать заявление об освобождении. Если же лампочка горит, значит десятидневка была "грязной", продолжаем молча отпираться, но перед уходом лампочку гасим, запуская тем самым новую десятидневку.

Общий срок отсидки предсказать невозможно - он может быть любым числом, кратным 10, в зависимости от рассеяности следователя. :-)

[pishu]

Каждому выцарапывать первую букву своего ника на панели выключателя лампочки при визите. Все видят отметку и прикидывают когда можно сказать волшебное слово. Если на лампочку следак не обращает внимание, то и на выключатель не будет. Подзабыл нужный раздел математики, но думаю что в лучшем случае будут сидеть 10 дней, а в худшем наверное 10!.

[109.livejournal.com]

по этому алгоритму 10 смен сможет насчитать только тот, кого вызвали на допрос первым. и только если его будут вызывать после каждого изменения состояния лампочки. а если вдруг вызывали 1-2-3-1-..., то юзеры будут сидеть в тюряге вечно.

[109.livejournal.com]

верно!

[109.livejournal.com]

нет :-)

[109.livejournal.com]

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

[109.livejournal.com]

великолепно! даже начальное состояние лампы учтено! (я уж решил на это внимания не обращать)

[109.livejournal.com]

я, если честно, решение совершенно не понял. то есть, может оно и будет работать, но я просто не понимаю написанного. нельзя ли как-нибудь поподробнее/пояснее?

[109.livejournal.com]

отлично! альтернативное решение, я про него не знал!

[109.livejournal.com]

однако сидеть им придётся гораздо дольше, чем при известном мне решении :-)