Здравствуйте, 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)