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

[109]

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

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

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

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

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

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

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

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

sply

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

Comments

[shigin.livejournal.com]

Дни бьются на отрезки по 10 дней. Человек, входящий в комнату в первый день отрезка выключает лампочку. В n--ый отрезок времени лампочку может включить только (n mod 10)--ый человек.

Люди, заходящие после него могут с уверенностью утверждать, что человек (n mod 10) уже подвергался допросу.

На бонус не отвечу, но предполагаю, что около 150 дней...

[109.livejournal.com]

алгорим не совсем понятен. кто и в какой момент заявит, что всех допросили?

[shigin.livejournal.com]

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

Хотя другие решения, конечно лучше...

[upstartn.livejournal.com]

Корректирую:
счетчиком будет юзер, зашедший первым

[109.livejournal.com]

годится!

[isk.livejournal.com]

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

а насчет матожидания я еще подумаю

[109.livejournal.com]

верно! фдисятке!

[sply.livejournal.com]

Что-то не получается на комментарий с вопросами ответить, потому отвечаю на сам пост.

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

[sply.livejournal.com]

а вообще-то, что-то я все слишком усложнил, это если у заключенных еще и памят плохая - один бит :)

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

мат. ожидание: 100 дней

[109.livejournal.com]

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

я предлагаю так: если покажете, что мат. ожидание отсидки короче человеческой жизни, то засчитаю.

[raa.livejournal.com]

сочли мое решение неверным :) ?

[109.livejournal.com]

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

не получали?

[raa.livejournal.com]

не, не получал. по-моему это очевидно из общих физических соображений. положим промежуток времени, который закрепляется за одним из 9-ти заключенных равным 1 году. какова вероятность того, что вызывая по одному человеку в день запоминающий зайдет после того как вызвали того, за кем этот год закреплен? почти 100%. 10 человек - 10 лет, для настоящего коммерсанта не срок ;)

если по-научному - я боюсь ошибиться, но оценю грубо, чтоб было понятно эти цифры порядка года. итак пусть каждому человеку отводится 9 дней - чтоб зашел сначала он, а потом запоминающий. расчитаем вероятность, что событие НЕ случится. это значит, что если первый (тот кто включит) зашел в какой-то день, ни в один из последующих дней не зашел запоминающий (тот кто запомнит и выключит). 1/10 - вероятность того, что включающий зашел в n-й день и 1-(9/10)**(n-1) если в остальные n-1 не зашел запоминающий. это где-то 0.3, за какое число промежутков можно сказать, что это событие свершится? за 5 раз (50 дней) - вероятность такого события уже около 95%. а 50*9 (всего таких 9 человек) - это 450 дней, почти та цифра которую я назвал.

[109.livejournal.com]

как-то неубедительно. вот моё рассуждение: вероятность, что чувака вообще вызовут в его десятидневку - примерно 0.65, такая же вероятность для счётчика. то, что вызовут обоих, соответственно, 0.4. теперь, счётчик должен быть вызван после обычного чувака, вероятность чего 50%, после умножения на 0.4 остаётся 0.2. то есть в среднем на каждого чувака - 30 дней. на 9 чуваков, соответственно, 270.

короче, засчитываю :-)

[sply.livejournal.com]

> годится, но ни фига не 100 дней. 100 дней только в идеальном варианте, когда в каждую следующую десятидневку юзеры попадают сразу после номера, пришедшего в правильный день и при условии, что этот номер ещё не попадался.
>
> я предлагаю так: если покажете, что мат. ожидание отсидки короче человеческой жизни, то засчитаю.

ага, здесь получается 9000 дней, чуть меньше, чем в моем первом варианте:
10*10 - число дней, необходимых чтобы оказаться нужному номеру в нужный день; *10 - перед ним может быть любой из десяти; *9 - ему нужно увидеть информацию от остальных девяти

а первый вариант решения (http://www.livejournal.com/users/109/257878.html?thread=862294#t862294) засчитывается?

[109.livejournal.com]

так я ж не получил ответа на свой вопрос! но ладно, засчитываю.

[sply.livejournal.com]

блин, а решение плохое :( как-то time division сразу в голову засел и другие варианты просто не воспринимались :(