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

[109]

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

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

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

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

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

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

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

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

sply

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

Comments

[contras.livejournal.com]

А почему именно 5 лет ? Тут же не столько от алгоритма зависит, сколько от следователя. Если он для начала вызовёт всех по одному разу, то освободятся строго на 10 день (т.е. минимально возможное время отсидки значительно меньше, чем в других алгоритмах, где "контролирующий сиделец" только один). А если он будет 100 лет гонять 1-9, то так и будут сидеть 100 лет при любом алгоритме.

[109.livejournal.com]

мат. ожидание имеется в виду. если много-много таких групп по десять набрать, то в среднем каждая группа будет сидеть 5 лет.

почему? потому что вероятность вызова всех ровно по разу - 0.9 * 0.8 * 0.7 * 0.6 ... * 0.1 = 3E-4, что даёт нам 2300 попыток, чтобы достичь вероятности удачи 50%.

что даёт нам... 23000/365 = 63 года. хм, откуда я пять лет взял? ошибся где-то (в уме оценивал).