[задача] про заключённых и лампочку

ну если посадили целую банду нехороших дядек, то они могли сговориться, что если их будут допрашивать, выключать свет =)

В quiz@

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

Состояние лампочки между допросами не меняется. То есть, как ее один оставил, так следующий и увидит.

+1 всё верно

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

день бредовых задач на ЛОРе

Да, действительно, подхоже на правду. Я бы не додумался до такого.

http://cyxymu.livejournal.com/438495.html

Во-первых не оговорено, включена лампа перед началом допроса или нет. Пусть будет выключена.

пусть 0-й выключает, их трое.

Порядок
0 - выключил.
1 - пришёл, включил (больше не трогает).
2 - пришёл, ничего не делает.
=== все побывали на допросе
далее вызывают 0-го до бесконечности. Он никогда не скажет "Да", значит их никогда не освободят.

Следовательно данное описание не позволяет им гарантированно освободиться.

Я так решил, что "в случайном порядке" в условии задачи означает "с равной вероятностью", поэтому, по законам статистики, при достаточно большом по сравнению с N количеством допросов, каждого заключенного будут вызывать по несколько раз. Вопрос о состоянии лампы до допроса, конечно, остается, но его можно решить даговорившись, например, что каждый должен включить по 2 раза. Таким образом, максимальное число включений лампы может быть 1 + 2 * (N - 1). Но уже после того, как (N - 1) * 2 она окажется включеной, заключенный, который ее выключает, может сделать вывод, что это было или 1 включение до начала допросов + 2*(N - 2) + 1 /*кто-то включил ее 1 раз, остальные по 2*/, или (N - 1) * 2 /*все включили по 2*/.

Словом, при любом раскладе (N - 1) * 2 включений наберется тогда и только тогда, когда каждый из N - 1 заключенных включит лампу хотя бы раз, независимо от того, была ли лампа включена вначале.

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

А ведь лампочка может быть не только вкл/выкл но и нагретой/не нагретой

s/договорится/договориться/

> Следовательно данное описание не позволяет им гарантированно освободиться.

ИМХО, тут и не будет гарантированного варианта освобождения. Возьмём приведённый вами крайний случай - всех вызывают по очереди и только 1 раз, а последнего - бесконечное количество раз. Лампочка чрезчур "бинарна", чтобы каждый вызванный заключённый мог бы "в ней отметиться". Последний заключённый получит информации ровно в один бит, который может быть израсходован на сообщение "ты последний" (да/нет) :) Но это неорганизуемо :))

Я тоже сомневаюсь в наличии корректного решения при поставленных условиях. А так приведённое решение по-моему правильно.

> А ведь лампочка может быть не только вкл/выкл но и нагретой/не нагретой

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

> Вопрос о состоянии лампы до допроса, конечно, остается, но его можно решить даговорившись, например, что каждый должен включить по 2 раза

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

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

Опа! Вот и решение проблемы невызываемого нулевого: любой, кто видит, что лампа не выключается уже 2^N допросов (его личных допросов), делает вывод.

Ну вызовут второго 2^N раз а потом третьего (точнее третьего уже не успеют, их всех расстреляют из за вывода второго).

1. Первый вызванный включает лампу или оставляет ее включенной.

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

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

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

4. Первый, кто закончил свои упражнения с выключателем и видит, что лампа не изменяет состояние уже на протяжении 1+2+...+N ходов, говорит, что финиш.

В целом идея хорошая но я бы её обобщил так: заключённые договариваются действовать следующим образом - пересчитывают своё количество, допустим N, каждый при первом допросе если лампа включена оставляет её включенной, если была выключена включает, и свой личный щётчик n устанавливает в 1, при всех последующих вопросах если лампа включена выключает её, добавляет к личному счётчику n=n+1 и отвечает "нет" пока n<N при n=N отвечает "да", если лампа выключена отвечает "нет".

Такой подход есть более быстрым, и надёжным ибо ктото может умреть побывав всего на нескольких допросах, а когото могут допрашивать только один раз.

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

>ИМХО, тут и не будет гарантированного варианта освобождения.

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

> Да, гарантированого нет. Тюремщики могут быть нечестны и вызывать только одного:) а могут сами играться и включать-выключать лампочку;)

Ну, скажем, при приведённым Легионером раскладом - ни один из предложенных вариантов не даст освобождения. Хотя всех зеков честно вызовут и лампочку не тронут.

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

;)

Подумай ещё это решение, и причём самое лучшее.

Что значит какого-то заключённого могли забыть? Когда имеют возможность договорится всех ТОЧНО пересчитывают ==N и никого забывать нельзя. Дальше ввиду того что никто умерать не хочет каждый очень хорошо будет запоминать свой индивидуальный счётчик n и увеличивать его! Ну для склерозников можно дать установку что если ты забыл свой индивидуальный счётчик то лучше его уменьшить или прекратить считать и ВСЕГДА отвечать "нет", а если считать не умеешь и не понял мой пост выше - отвечаешь ВСЕГДА "нет"!!!

>Ну для склерозников можно дать установку что если ты забыл свой индивидуальный счётчик то лучше его уменьшить или прекратить считать и ВСЕГДА отвечать "нет", а если считать не умеешь и не понял мой пост выше - отвечаешь ВСЕГДА "нет"!!!

Это бред! Всё остальное написанное правильно.

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

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

Если убьют всех то не очень обидно. А если конец света — то вообще даже весело (наверное).

Вся проблема в том, что тех, кого уже допросили, если и не будут включать/выключать лампу, одного могут не вызвать. Вызывают же в случайном порядке. То есть после N*x (где x - произвольное натуральное число) раз могут не вызвать по крайней мере одного заключённого на допрос.

А теперь посмотрим, если будут трогать лампу:
Дело в том, что если лампа выключена некоторое время (не трогают выключатель допрошенные), тогда получается проблема и физического решения задачи. Поэтому надо сделать так, чтобы количество заключённых имела чётное/нечётное число. То есть чтобы лампа была включена в конце концов. Но тут возвращаемся к первой проблеме.

Да действительно не умрут но выйдут только когда первого вызовут два раза подряд, а потом будут вызывать сразу за новым (впервые вызванным заключённым):(

Да похоже с распределённой считалкой ничего не выходит считать должен только один! Тогда похоже быстрее чем сказано в LMN-tal (*) (15.08.2008 19:12:29) не получится никак.

Один включает и считает, остальные выключают 1 раз.

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

>считать должен только один!

Обломайтеся. Этого одного могут не вызвать ни разу. Считать должны все.

> Обломайтеся. Этого одного могут не вызвать ни разу. Считать должны все.

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

Зато они гарантированно не будут казнены.