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

[109]

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

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

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

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

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

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

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

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

sply

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

Comments

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

[lindenalee.livejournal.com]

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

[109.livejournal.com]

верно!

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

[alexeyten]

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

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

[109.livejournal.com]

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