N разбойников сажают в тюрьму. Им дается возможность сговориться перед тем, как их изолируют друг от друга.
Охранники вызывают разбойников по-одному в пустую комнату с выключателем, который может находиться в двух положениях (включен/выключен).
Разбойник может:
1. изменить состояние выключателя
2. ничего не делать
3. сказать, что все разбойники хотя бы раз побывали в этой комнате
если угадал --- всех выпускают
если не угадал --- всем каюк
— Охранники вызывают кого хотят и когда хотят.
— Охранники знают, как сговорились себя вести разбойники.
— Гарантируется, что каждый разбойник будет вызван неограниченное число раз.
Вопрос: могут ли разбойники гарантированно спастись?
Здравствуйте, KonstantinA, Вы писали:
KA>N разбойников сажают в тюрьму. Им дается возможность сговориться перед тем, как их изолируют друг от друга.
KA>Охранники вызывают разбойников по-одному в пустую комнату с выключателем, который может находиться в двух положениях (включен/выключен).
KA>Разбойник может: KA>1. изменить состояние выключателя KA>2. ничего не делать KA>3. сказать, что все разбойники хотя бы раз побывали в этой комнате KA> если угадал --- всех выпускают KA> если не угадал --- всем каюк
KA>- Охранники вызывают кого хотят и когда хотят. KA>- Охранники знают, как сговорились себя вести разбойники. KA>- Гарантируется, что каждый разбойник будет вызван неограниченное число раз.
KA>Вопрос: могут ли разбойники гарантированно спастись?
Могут ли охранники изменять состояние выключателя между вызовами разбойников?
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Могут ли охранники изменять состояние выключателя между вызовами разбойников?
Нет, они могут только решать кого позвать в следующий раз.
P.S. Хотя... Что если охранники могут изменять состояние выключателя, но не более некоторого фиксированного (известного) количества раз. Кажется, что и в этом случае задача решаема.
Здравствуйте, KonstantinA, Вы писали:
KA>N разбойников сажают в тюрьму. Им дается возможность сговориться перед тем, как их изолируют друг от друга.
KA>Охранники вызывают разбойников по-одному в пустую комнату с выключателем, который может находиться в двух положениях (включен/выключен).
KA>Разбойник может: KA>1. изменить состояние выключателя KA>2. ничего не делать KA>3. сказать, что все разбойники хотя бы раз побывали в этой комнате KA> если угадал --- всех выпускают KA> если не угадал --- всем каюк
KA>- Охранники вызывают кого хотят и когда хотят. KA>- Охранники знают, как сговорились себя вести разбойники. KA>- Гарантируется, что каждый разбойник будет вызван неограниченное число раз.
KA>Вопрос: могут ли разбойники гарантированно спастись?
Договор: Выбираем одного конкретного разбойника. Только он имеет право включать выключатель (и никогда его сам не выключает). Он же считает число выключений.
Попав в камеру, он проверяет число выключений. Если оно равно N-1, то он заявляет, что все тут уже побывали. Иначе он включает выключатель.
Любой другой, попав в камеру, проверяет состояние выключателя. Если выключатель включен и он до этого ни разу его не выключал, то он его выключает. В противном случае он ничего не делает.
Здравствуйте, Lexey, Вы писали:
L>Договор: Выбираем одного конкретного разбойника. Только он имеет право включать выключатель (и никогда его сам не выключает). Он же считает число выключений. L>Попав в камеру, он проверяет число выключений. Если оно равно N-1, то он заявляет, что все тут уже побывали. Иначе он включает выключатель. L>Любой другой, попав в камеру, проверяет состояние выключателя. Если выключатель включен и он до этого ни разу его не выключал, то он его выключает. В противном случае он ничего не делает.
Ну что же, это сработает, если известно, что выключатель изначально выключен.
Если же про его начальное состояние не известно ничего, то можно ошибиться.
Пример. Изначально выключатель включен, вызывают разбойника-счетовода, N=2.
Как быть, если не известно начальное положение выключателя?
Здравствуйте, KonstantinA, Вы писали:
KA>Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>>Могут ли охранники изменять состояние выключателя между вызовами разбойников?
KA>Нет, они могут только решать кого позвать в следующий раз.
KA>P.S. Хотя... Что если охранники могут изменять состояние выключателя, но не более некоторого фиксированного (известного) количества раз. Кажется, что и в этом случае задача решаема.
Факт. Пусть это число K. Пусть первый должен насчитать M выключений до того, как скажет, что все уже тут были, а P — максимыльное число выключений, которые могут сделать "выключающие разбойники". Тогда нужно:
M — K >= P * (N — 2) + 1, т.е. каждый из разбойников сделал хотя бы одно реальное выключение.
И P * (N-1) — K >= M, если все возможные выключения сделаны, то счетчик должен это заметить.
N = 2, M >= K + 1, P >= M + K. Минимальное решение — M = K + 1, P = 2 * K + 1.
N > 2: P <= (M — (K + 1)) / (N-2) и P >= (M + K) / (N — 1);
M >= (K + 1)(N — 1) + K(N-2). Минимальное решение: M = (K+1)(N-1)+K(N-2), P = (2K +1)*(N-1)
Здравствуйте, KonstantinA, Вы писали:
KA>Здравствуйте, Lexey, Вы писали:
L>>Договор: Выбираем одного конкретного разбойника. Только он имеет право включать выключатель (и никогда его сам не выключает). Он же считает число выключений. L>>Попав в камеру, он проверяет число выключений. Если оно равно N-1, то он заявляет, что все тут уже побывали. Иначе он включает выключатель. L>>Любой другой, попав в камеру, проверяет состояние выключателя. Если выключатель включен и он до этого ни разу его не выключал, то он его выключает. В противном случае он ничего не делает.
KA>Ну что же, это сработает, если известно, что выключатель изначально выключен.
KA>Если же про его начальное состояние не известно ничего, то можно ошибиться. KA>Пример. Изначально выключатель включен, вызывают разбойника-счетовода, N=2.
Ты прав.
KA>Как быть, если не известно начальное положение выключателя?
Ну тогда сводим эту задачу к случаю с помехами при K = 1.
Решение, которое дал Lexey замечательно тем, что даёт, похоже, наиболее быстрый способ для разбойников. Но в случае с шалящими охранниками его очень сложно понять.
Вот другое решение, имхо существенно более простое для понимания. Оно потребует вроде как большего, числа вызовов. Но так как охранники вызывают по своему произволу, это мнимый недостаток — в обоих алгоритмах они могут сделать освобождение сколь угодно долгим. (О более быстрых и более медленных алгоритмах есть смысл говорить только, если обязать охранников делать промежуток между последовательными вызовами каждого разбойника не более чем M).
Итак.
Сначала без шалящих охранников и с гарантированно выключенным выключателем в начале.
N-1 разбойников включают — каждый должен включить 2^k раз, где k-его номер.
Последний разбойник — сторож — выключает и считает, сколько раз он выключал.
Как только это число в двоичном виде будет всеми единицами (N-1 штук), он останавливает игру.
Теперь пусть охранники некоторое число раз могут включить сами.
Выбираем ближайшую сверху к этому числу степень двойки и сдвигаемся на столько разрядов влево.
(Т.е. каждый включающий теперь включает ровно 2^(k+k0) раз)
Сторож не смотрит на нижние разряды (а посмотрев, узнает поведение охранников).
Наконец, если охранники могут не только включать, но и выключать (менять K раз),
сторож может мысленно включить К раз (добавить K к своему числу).
Тогда мы приходим к предыдущему случаю — охранники могут только включать,
но не более, чем 2K раз.
