Сообщений в теме: 37

[Freakazoitt]

Группу заключенных через несколько дней собираются переселить в одиночные камеры. Из них можно совершать прогулки по одному в пустующем коридоре, где нет ничего, кроме никуда не подключенного рубильника. Охрана предлагаем им шанс освободиться раньше срока. Для этого один из заключенных во время прогулки должен прокричать, что все другие уже бывали на прогулке один раз и не ошибиться. В случае ошибки все заключенные остаются в камерах навсегда.
Общаться ни знаками, ни голосом из одиночных камер заключенные не смогут.
Вопрос: Как должны действовать заключенные, чтобы выполнить эти условия?
Решение может быть если начальное положение рубильника известно и более сложное — если начальное положение рубильника неизвестно.

[Wasteland Rat]

У рубильника 2 положения или сколько угодно в пределах 180 градусов? Если второе, то элементарно — делим 180 на количество заключенных, получаем угол поворота на каждого заключенного, когда рубильник доходит до противоположного конца — можно кричать.

[Freakazoitt]

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

[Vault City]

Wasteland Rat
Ваше элементарное решение требует просто нереальный глазомер и многих часов тренировок. Не каждый сможет крутить что-то на строго определенное кол-во градусов без предварительной подготовки. А в каких-то случаях задача вообще становится невыполнимой.

Это сообщение отредактировано Vault City - 6 ноября 2011 | 15:03

[Vault_13]

А рубильник при включении/выключении звук издаёт ? Должен .

[Vault City]

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

[Wasteland Rat]

QUOTE

Ваше элементарное решение требует просто нереальный глазомер и многих часов тренировок.

Ну я ж не знал что их 50 Для 5-6 вполне реально.

Короче задачка на числовые последовательности явно, надо подумать.

QUOTE

А рубильник при включении/выключении звук издаёт ? Должен

Они из камер не могут друг друга услышать даже если орать будут, а вы хотите чтоб щелчок рубильника услышали? )

QUOTE

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

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

[exelenz]

Если в коридоре ничего нет кроме рубильника, то там нет и окон. А значит он освещается обычными лампочками с выключателем у охраны. Заключенные договариваются между собой о двух вещах:
1. оставаться на прогулке как можно дольше;
2. каждый заключенный должен напомнить охраннику об экономии электроэнергии и обязанности выключасть свет в коридоре когда там никого нет.
Как говорит Freakazoitt,

QUOTE

Количество заключенных пусть будет 50.

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

Либо:

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

В обоих случаях рубильник нам не нужен.

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

[Wasteland Ghost]

QUOTE

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

Наш уважаемый Freakazoitt не упомянул, что каждый ЗК может побывать в коридоре неограниченное число раз. Вот более точная формулировка:

QUOTE

В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу, и предложил следующие условия: "В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON/OFF (верх/низ). Вас будут в произвольном порядке по одному приводить в эту комнату и через несколько минут уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен сказать, что в комнате побывали все заключённые. Если он окажется прав — всех отпустят, если ошибётся — вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключённые и что каждого из вас будут приводить туда снова и снова неограниченное число раз." После этого заключённым разрешили собраться и обсудить стратегию, потом развели по камерам. Что им нужно делать, чтобы гарантированно выйти на свободу?

[exelenz]

Если неограниченное, то все проще.

Вариант с заранее известным положением переключателя. Пусть переключатель изначально находится в положении "верх" и количество заключенных = K. Тогда все заключенные кроме одного должны будут при входе в комнату поставить переключатель "вниз", но только один раз. Оставшийся заключенный всегда переключает его "вверх", считая количество переключений. Когда счет дойдет до числа К-1, он объявит что побывали все.

[Wasteland Ghost]

exelenz, в яблочко. С неизвестным положением тоже просто. Ключевая фраза — "хотя бы один раз".

[Freakazoitt]

Не знал, что это есть в интернетах.

Это сообщение отредактировано Freakazoitt - 7 ноября 2011 | 09:29

[eye-eye mkII]

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

[Wasteland Rat]

Вообще условия некорректные, т.к. данные "обещания" не запрещают держать одного заключенного в резерве и не выводить его вообще, поскольку в реальности последовательность прогулок всегда конечная:

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

[Wasteland Ghost]

QUOTE

Я, честно говоря, не увидел в условиях, что будет проведён полный цикл без повторений...

Я тоже. Вот условие:

QUOTE

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

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

QUOTE

Вас будут в произвольном порядке по одному приводить в эту комнату и через несколько минут уводить.

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

QUOTE

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

И что? Он просто не будет трогать рубильник и не будет считать. Если охрана сдержит обещание "каждого из вас будут приводить туда снова и снова неограниченное число раз", то рано или поздно все будут посчитаны.

QUOTE

Вообще условия некорректные, т.к. данные "обещания" не запрещают держать одного заключенного в резерве и не выводить его вообще, поскольку в реальности последовательность прогулок всегда конечная:

Запрещают:

QUOTE

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

Wasteland Rat, это задача, а не реальный план побега. В заданных условиях случайного выбора и неограниченного числа попыток решение exelenz абсолютно верно.

Отправлено: 7 ноя 11 13:39
Не заметила сообщение:

QUOTE

Не знал, что это есть в интернетах.

"100 Prisoners and a Light Bulb"
Оригинальный оригинал:

QUOTE

100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?

Целая куча заумностей на тему оптимального решения данной задачки.

[Artem13]

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

[Wasteland Ghost]

QUOTE

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

Неверно. "Момент K-1" наступает тогда и только тогда, когда в комнате побывали K-1 разных заключённых и при этом считающий посчитал их всех. "K-1" — это не момент времени! Время не ограничено, число посещений не ограничено, заключённые выбираются случайно. Т.о. речь не идёт о каком-то моменте времени, хотя, конечно, при заданных интервалах между посещениями можно найти мат. ожидание до освобождения (в статье по ссылке этот интервал равен суткам и среднее время — 28 годам).

Задачка чем-то похожа на парадокс Монти Холла: сначала вызывает ступор, потом очевидность решения вызывает острое нежелание его принимать.

[eye-eye mkII]

QUOTE

И что? Он просто не будет трогать рубильник и не будет считать. Если охрана сдержит обещание "каждого из вас будут приводить туда снова и снова неограниченное число раз", то рано или поздно все будут посчитаны.

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

QUOTE

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

В таком случае, вероятность того, что я, выйдя из дома, встречу Tyrannosaurus Rex тоже стремится к 100%. Ведь, как известно, в бесконечной вселенной, в бесконечном времени...
Никогда не понимал такие задачи. Ох и тяжело в этом суровом мире абстрактной математики ограниченным деб людям, лишённым высокой способности мыслить непредметно.

[dreadfull]

Читаем решение ещё раз:

QUOTE

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

[eye-eye mkII]

QUOTE

Читаем решение ещё раз:

О. Ну да. Действительно.
Пойду убью себя.