|
|
 |
Условие
Назовем расстановку n единиц и m нулей по кругу хорошей, если в ней можно поменять местами соседние нуль
и единицу так, что получится расстановка, отличающаяся
от исходной поворотом. При каких натуральных n, m существует хорошая расстановка?
Решение
Пронумеруем позиции по кругу числами от 0 до m + n – 1 по часовой стрелке.
Построение расстановки для взаимно простых m и n. Поскольку n и m взаимно просты, взаимно просты и n и m + n. Тогда при k = 0, 1, ..., m + n – 1 числа nk дают попарно разные остатки при делении на m + n. Возьмем k0 такое, что nk0 дает остаток 1 при делении на m + n.
Поставим 1 на позиции, соответствующие остаткам при делении на m + n чисел k0, 2k0, ..., (n – 1)k0, nk0≡ 1, а на остальные позиции нули. Тогда при повороте на k0 позиций против часовой стрелки наша расстановка перейдет в расстановку с единицами на позициях, соответствующих остаткам чисел 0, k0, 2k0, ..., (n – 1)k0 . То есть при данном повороте единица на позиции 1 поменяется местами с нулем на позиции 0, а значит, расстановка является хорошей.
Доказательство взаимной простоты m и n. Пусть числа m и n имеют общий делитель d > 1 . Рассмотрим остаток, который даёт сумма номеров позиций единиц при делении на d. При повороте на k к каждому номеру добавляется k (и, возможно, вычитается m + n), значит, к сумме всех номеров добавляется kn и вычитается некоторое кратное m + n, то есть остаток при делении на d этой суммы не меняется. С другой стороны, если поменять местами соседние 0 и 1, этот остаток изменяется ровно на 1. Значит, при этом не может получиться расстановка, отличающаяся от исходной поворотом.
