Выбрано 12 задач 
Убрать все задачи
Делимое в шесть раз больше делителя, а делитель в шесть раз больше частного. Чему равны делимое, делитель и частное?
В равносторонний треугольник со стороной a вписана окружность. К окружности проведена касательная, отрезок которой внутри треугольника равен b.
Найдите площадь треугольника, отсечённого этой касательной.
Бумажный прямоугольный треугольник АВС перегнули по прямой так, что вершина С прямого угла совместилась с вершиной В и получился четырёхугольник. В каких отношениях точка пересечения диагоналей четырёхугольника делит эти диагонали?
В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.
Приведите пример числа, делящегося на 2020, в котором каждая из десяти цифр встречается одинаковое количество раз.
На стороны BC и CD параллелограмма ABCD (или
на их продолжения) опущены перпендикуляры AM и AN.
Докажите, что треугольники MAN и ABC подобны.
В треугольнике ABC угол A равен 40°. Треугольник случайным образом бросают на стол.
Найдите вероятность того, что вершина A окажется восточнее двух других вершин.
Найдите производящие функции последовательностей многочленов Чебышева первого и второго рода:
На острове 100 рыцарей и 100 лжецов. У каждого из них есть хотя бы один друг. Однажды ровно 100 человек сказали: "Все мои друзья – рыцари", и ровно 100 человек сказали: "Все мои друзья – лжецы". Каково наименьшее возможное количество пар друзей, один из которых рыцарь, а другой лжец?
Один из четырёх углов, образующихся при пересечении двух прямых, равен 41°. Чему равны три остальных угла?
Монету бросают трижды. Сколько разных последовательностей орлов и решек можно при этом получить?
Назовем расстановку n единиц и m нулей по кругу хорошей, если в ней можно поменять местами соседние нуль и единицу так, что получится расстановка, отличающаяся от исходной поворотом. При каких натуральных n, m существует хорошая расстановка?
|
|
 |
Условие
Назовем расстановку 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. Значит, при этом не может получиться расстановка, отличающаяся от исходной поворотом.
Ответ
При взаимно простых m, n.
