Здравствуйте, KonstantinA, Вы писали:

KA>

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

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

Итак.
Сначала без шалящих охранников и с гарантированно выключенным выключателем в начале.
N-1 разбойников включают — каждый должен включить 2^k раз, где k-его номер.
Последний разбойник — сторож — выключает и считает, сколько раз он выключал.
Как только это число в двоичном виде будет всеми единицами (N-1 штук), он останавливает игру.

Теперь пусть охранники некоторое число раз могут включить сами.
Выбираем ближайшую сверху к этому числу степень двойки и сдвигаемся на столько разрядов влево.
(Т.е. каждый включающий теперь включает ровно 2^(k+k0) раз)
Сторож не смотрит на нижние разряды (а посмотрев, узнает поведение охранников).

Наконец, если охранники могут не только включать, но и выключать (менять K раз),
сторож может мысленно включить К раз (добавить K к своему числу).
Тогда мы приходим к предыдущему случаю — охранники могут только включать,
но не более, чем 2K раз.