Тема: В юрте у Акына.

[Tempo]

Атэц

[Акын]

Задача:
Есть N заключенных. Их всех привезли в свежепостроенную тюрьму. Тюрьма особенная: заключенные живут в одиночках, причем каждый день из них случайным образом выбирается один и сажается в карцер. Карцер представляет собой "каменный мешок" из мебели - только электрическая лампочка с выключателем) По правилам тюрьмы, заключенные получат свободу только тогда, когда кто то из них скажет, что в карцере все побывали хотя бы раз. Если это правда - всех отпускают. Если нет - расстреливают. Прежде, чем рассадить заключенных по камерам, им дали 15 минут на совещание. О чем они договорились, если известно, что по прошествии некоторого срока всех выпустили. Единственное действие, которое они могут совершать - это включать и выключать лампочку.

[Edking007]

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

[Акын]

Ok

[Tempo]

ты знал....ты знал

[Edking007]

Марик, Tempo,
Правда есть риск - всегда найдётся один тугодум, либо приколист

[BarbaCat]

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

[Edking007]

BarbaCat,
Согласен, тогда это несколько усложняет решение. Будем думать дальше.

[BarbaCat]

Можно просто посчитать через сколько дней по теории вероятности они все там побывают и тогда ответ:
"Они договорились сказать что они все посидели через это кол-во дней."

[Edking007]

Марик,Tempo,BarbaCat
Тогда так:
1. При "совещании" они друг друга пересчитали, и допустим, что зэков Х.
2. Один из них (самый способный, пахан, что-ли) будет иметь право свет выключать и будет обязан считать количество выключений, делая соответствующую татуировку на руке. Это поможет не сбиться.
3. Остальные - рядовые зэки имеют право только включать свет, притом только ОДИН раз.
4. После того, как пахан насчитал Х+1 выключений, он идёт на "доклад" к тюремному начальству.
5. Пахану должны предоставить некоторую свободу перемещения.

[BarbaCat]

Edking007
Хе, это будет слишком долго
Хотя мой вариант тоже не самый быстрый, но он исключает провал.
А вот в втоём вариане вполне могут все пойти на расстрел

С учётом 5-го пункта да, так можно. Но сидят все в одиночках, какая свобода перемещения?!
Да и наколки 100% ему там нечем колоть Я уже вообщем-то дал ответ, мне просто лениво вспоминать Теор.Вероятности и считать

[Edking007]

BarbaCat,
Давай рассуждать вместе:
1. Тюрьма - это вообще, штука небыстрая, поэтому, быдем считать, что время не является критерием.
2. Мы точно не знаем количества заключённый, учавствующих в этой авантюре, а их может оказаться 2000 или 4000.
3. В таком случае, через какое время ты бы сообщил начальству (тьфу, тьфу, тьфу, не обязательно ты) о том, что все в карцере побывали?

[BarbaCat]

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

[Dvulikiy]

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

[Акын]

один из заключенных ведет счет, когда он покидает карцер, то выключает свет.  а правило такое, если заключенный попал в карцер первый раз он, то покидая карцер оставляет свет включенным.  если не в первый раз попал, то свет не трогает (если горел - пусть горит, если не горел - пусть не горит). тоесть когда заключенный-счетовод попадет опять в карцер, он определит: свет горит +1, свет не горит 0.  и когда счетовод насчитает N-1 раз (про себя он знает, что побывал в карцере)...  то тогда объявит, что в карцере все побывали.