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

[109]

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

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

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

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

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

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

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

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

sply

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

Comments

[puzanov.livejournal.com]

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

[109.livejournal.com]

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

[puzanov.livejournal.com]

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

[upstartn.livejournal.com]

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

[109.livejournal.com]

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

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

[dvurukov.livejournal.com]

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

[109.livejournal.com]

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

[alexeyten]

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

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

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

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

[109.livejournal.com]

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

так как?

[dvurukov.livejournal.com]

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

[109.livejournal.com]

нет :-)

[raa.livejournal.com]

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

[raa.livejournal.com]

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

[109.livejournal.com]

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

[navy-99.livejournal.com]

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

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

[109.livejournal.com]

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

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

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

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

[109.livejournal.com]

алгоритм непонятен (что такое "после трёх смен состояния?"), полученное с помощью него среднее время говорит о том, что он к тому же неверен :-)

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

[puzanov.livejournal.com]

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

[109.livejournal.com]

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

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

[lindenalee.livejournal.com]

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

[109.livejournal.com]

верно!

[pricolist.livejournal.com]

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

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

[109.livejournal.com]

верно!

[ruundii.livejournal.com]

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

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

[109.livejournal.com]

верно!

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

[contras.livejournal.com]

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

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

[109.livejournal.com]

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

[pishu]

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

[109.livejournal.com]

креатифф!

[pricolist.livejournal.com]

Мое решение правильное или нет?
Словами. Назначается один человек который может выключать. Остальные должны ОДИН раз включить лампочку. Тоесть они заходят в комнату и если там темно и они не разу не включали, зажигают свет. В противном случае оставляют все как есть.
Выключающий каждый раз попадая в комнату, выключает свет. После того как он выключит свет 9 раз он может с уверенностью сказать что все в комнате побывали.
Возможно есть способ сократить время отсидки...

[109.livejournal.com]

правильное, я же вон записал вас в список победителей :-)

[sply.livejournal.com]

Нумеруются от 1 до 10.

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

Достаточное условие:
N(x) знает, что N(x-1) уже на допросе был, т.е. когда N(x) приходит в "свой" день D=x и видит лампочку зажженой. Первый заключенный зажигает лампочку всегда.

Когда последний N(10) узнает, что N(9) уже был, он заявляет, что всех вызывали.

При равномерном распределении ожидаемый срок сидения - 10000 дней: 10*10 - число дней, необходимых чтобы оказаться нужному номеру в нужный день. *10*10/9 - когда выпадают два дня подряд для смежных номеров и N(x) узнает, что N(x-1) был на допросе, *9 - для смежных номеров известно состояние предыдущего номера.

[109.livejournal.com]

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

[wind-bbc.livejournal.com]

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

[109.livejournal.com]

верно!

[gornal.livejournal.com]

Самый подозрительный из них выключает лампочку, каждый раз как увидит ее включенной, а остальные включают первые два раза, как увидят ее выключенной. Включив лампочку в 2n-2-ой раз самый подозрительный объявляет, что никто не раскололся. Если бы было известно изначальное состояние лампочки - освободились бы в два раза быстрее :-)

[109.livejournal.com]

верно!

[bacek.livejournal.com]

Элементрано: бьём время на декады и назначаем каждому пользователю номер от 1 до 10 распределяя дни декады. Далее действуем так:
1. Если первый пользователь был вызван в первый (т.е. "свой") день декады, то он включает лампочку.
2. Каждый следующий пользователь если он вызван в "свой" день не меняет состояние лампочк. Если в чужой, то он лампочку гасит.
3. 10-й пользователь вызваный в "свой" день смотрит на лампочку, и если она включена говорит "Бинго".

Матожидание считать лень. Будем надеятся, что они не сдохнут от старости.

[109.livejournal.com]

Будем надеятся, что они не сдохнут от старости.


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

[puzanov.livejournal.com]

>> так и что будет в случае, когда какой-то юзер был в камере в первый раз, лампочка уже была включена?
Ничего делать не будет. Уйдет. Те кто еще не включал лампочку - включают, если она выключена. Те кто уже включал - ничего не делают. А один за всеми выключает, если включена и считает количесво выключений.

[109.livejournal.com]

а он точно десять раз сможет выключить? :-)

[countff.livejournal.com]

Хорошие у вас задачки :) Жаль не успел с первой, попробую со второй.
Итак, если следователь допрашивает строго одного юзера в день, то возможен следующий вариант: юзеры должны рассчитаться, тоесть каждому присвоен порядковый номер, кроме того юзеры должны отсчитывать дни от того когда их посадили. Алгоритм следующий: назовем "ХОРОШИМ ДНЕМ ДЛЯ ЮЗЕРА", когда юзера вызывают в день, номер которого при делении на десять дает остаток равный порядковому номеру пользователя. Пользователь номер один ВКЛЮЧАЕТ лампочку если его вызывают в его "хороший" день. Пользователи 2-9 не меняют положение лампочки если их вызывают в их "хорошие" дни. Если пользователя вызывают в "плохой" день, то он должен выключить лампочку, либо не делать ничего если она уже не горит. Если пользователь номер 10 в свой "хороший" день видит горящую лампочку, то он заявляет следователю "вы уже всех вызывали, и никто не раскололся, так что отпускайте нас".

[109.livejournal.com]

работать будет, но посидеть бедолагам придётся немало :-)

если покажете, что человеческой жизни хватит, чтобы выйти, засчитаю :-)

[gornal.livejournal.com]

Мой ответ-то верен?
Мат. ожидание этого алгоритма примерно 2*(n^2+n)

[109.livejournal.com]

верен, извините за задержку с обработкой результатов! в теннис тут поиграл при температуре 40 по цельсию.

[alexfh.livejournal.com]

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

[109.livejournal.com]

верно!