|
|
 |
Условие
В каждой целой точке числовой оси расположена лампочка с кнопкой, при нажатии которой лампочка меняет состояние – загорается или гаснет. Вначале все лампочки погашены. Задано конечное множество целых чисел – шаблон S. Его можно перемещать вдоль числовой оси как жесткую фигуру и, приложив в любом месте, поменять состояние множества всех лампочек, закрытых шаблоном. Докажите, что при любом S за несколько операций можно добиться того, что будут гореть ровно две лампочки.
Решение 1
Пусть в S больше одного числа (для одного числа всё очевидно). Под текущей позицией будем понимать отрезок лампочек от самой левой горящей до самой правой (положение отрезка на прямой пока для нас не важно). Начав с позиции с одной горящей лампочкой, будем каждый раз прикладывать левую границу шаблона к самой левой горящей лампочке. Легко видеть, что тогда длина каждой получающейся позиции будет меньше длины шаблона, то есть возможных позиций – конечное число. Более того, по каждой позиции можно однозначно восстановить предыдущую: для этого надо приложить правый край шаблона к самой правой горящей лампочке. По теореме о зацикливании начальная позиция когда-нибудь повторится. Теперь последим за расположением позиций на прямой. Каждый раз позиция сдвигалась вправо, поэтому второй раз единственная лампочка будет не на том месте, что в начале.
Очевидно, что если теперь начать с пустой позиции и прикладывать шаблон к тем же местам прямой, то мы в конце получим две горящие лампочки: на начальном и конечном местах.
Решение 2
Будем рассматривать только лампочки, соответствующие неотрицательным числам. Каждому конечному набору горящих лампочек поставим в соответствие многочлен: коэффициент при xk равен 1, если лампочка на k-м месте горит, и 0 – в противном случае. Приложив шаблон левым краем к числу 0, мы получим некоторый многочлен P(x). Сдвинув шаблон вправо на k, мы прибавим к нему многочлен xkP(x) (сложение коэффициентов ведётся по модулю 2). Многократное применение такой операции даёт произведение P(x) на многочлен Q(x), который мы можем выбирать по своему усмотрению. Задача свелась к доказательству того, что некоторый многочлен вида xm + xn делится (по модулю 2) на P(x).
Это доказывается стандартным рассуждением. Рассмотрим остатки от деления одночленов вида xk на P(x). Поскольку количество одночленов бесконечно, а возможных остатков – конечное число (не больше 2p, где p – степень P(x)), для каких-то двух одночленов xm и xn эти остатки совпадают, то есть xm – xn делится на P(x). Но по модулю 2 xm – xn ≡ xm + xn.
Замечания
5 баллов
