LINUX.ORG.RU
ФорумTalks

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


0

0

А эту как решить?

Про заключенных и лампочку: В тюрьму приводят N заключенных, дают им пол часа пообщатья и разводят по одиночным камерам.

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

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

Как надо им действовать, чтобы всем освободиться?

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

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

★★★★★

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

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

grom0zekin ()

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

В quiz@

FiXer ★★☆☆☆ ()

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

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

LMN-tal ()
Ответ на: Re: [задача] про заключённых и лампочку от grom0zekin

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

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

anonymous ()

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

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

anonymous ()
Ответ на: Re: [задача] про заключённых и лампочку от LMN-tal

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

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

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

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

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

Legioner ★★★★★ ()
Ответ на: Re: [задача] про заключённых и лампочку от Legioner

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

Я так решил, что "в случайном порядке" в условии задачи означает "с равной вероятностью", поэтому, по законам статистики, при достаточно большом по сравнению с 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 заключенных включит лампу хотя бы раз, независимо от того, была ли лампа включена вначале.

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

LMN-tal ()

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

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

anonymous ()
Ответ на: Re: [задача] про заключённых и лампочку от Legioner

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

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

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

lv ()

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

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

Legioner ★★★★★ ()
Ответ на: Re: [задача] про заключённых и лампочку от anonymous

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

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

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

lv ()
Ответ на: Re: [задача] про заключённых и лампочку от LMN-tal

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

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

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

anonymous ()

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

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

abraziv_whiskey ★★★★★ ()
Ответ на: Re: [задача] про заключённых и лампочку от abraziv_whiskey

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

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

abraziv_whiskey ★★★★★ ()
Ответ на: Re: [задача] про заключённых и лампочку от abraziv_whiskey

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

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

Legioner ★★★★★ ()
Ответ на: Re: [задача] про заключённых и лампочку от Legioner

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

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

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

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

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

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

abraziv_whiskey ★★★★★ ()
Ответ на: Re: [задача] про заключённых и лампочку от LMN-tal

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

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

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

hse ()

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

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

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

anonymous ()
Ответ на: Re: [задача] про заключённых и лампочку от anonymous

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

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

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

lv ()
Ответ на: Re: [задача] про заключённых и лампочку от Freek

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

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

;)

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

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

hse ()

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

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

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

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

hse ()

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

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

Freek ()

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

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

Anarquista ()

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

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

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

Quasar ★★★★★ ()
Ответ на: Re: [задача] про заключённых и лампочку от Freek

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

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

hse ()
Ответ на: Re: [задача] про заключённых и лампочку от Quasar

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

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

hse ()

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

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

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

anonymous ()
Ответ на: Re: [задача] про заключённых и лампочку от abraziv_whiskey

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

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

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

lv ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.