Число переменных

[wpoms.]

Пусть `n` - натуральное число, для которого уравнение `x_1x_2 + x_2x_3 + x_3x_4 + x_4x_5 + ... + x_{n-1}x_n + x_nx_1 = 0` имеет решение, где все `x_i` принимают значение `1` или `-1`. Докажите, что `n` делится на `4`.

@темы: Теория чисел

Comments

[Adjirranirr]

Рассмотрим последовательность `x_1,\ x_2,\ ...,\ x_n,\ x_1`. Если `x_i != x_{i + 1}`, будем называть это «прыжком» (лучше слова не придумалось =). Очевидно, прыжки есть, так как в противном случае все произведения были бы положительными, и их сумма — ненулевой. С другой стороны, количество прыжков в данной последовательности четно, иначе выполнялось бы `x_1 != x_1`, что невозможно.

Умножая на `-2` и прибавляя `2(x_1^2 + x_2^2 + ... + x_n^2)`, получим
`(x_1 - x_2)^2 + (x_2 - x_3)^2 + ... + (x_{n - 1} - x_n)^2 + (x_n - x_1)^2 = 2 (x_1^2 + x_2^2 + ... + x_n^2)`. Выражения в скобках из левой части не обращаются в ноль только при прыжке, и, следовательно, ненулевых скобок — четное количество. А так как выражения в скобках принимают значения из множества `{-2,\ 0,\ 2}`, то все ненулевые квадраты имеют значение `4`, а вся сумма в левой части представима в виде `2k * 4`. Правая часть равна `2 \sum_n (+-1)^2 = 2n`, и `2n = 8k <=> n = 4k`, что и требовалось доказать.