Задача 78190

Тема:    [ Арифметика остатков (прочее) ]

Сложность: 4- Классы: 8,9

Условие

Автор: Леонтович А.М.

Дано n чисел, x₁, x₂, ..., x_n, при этом  x_k = ±1.  Доказать, что если  x₁x₂ + x₂x₃ + ... + x_nx₁ = 0,  то n делится на 4.

Решение 1

Заметим, что каждое слагаемое в указанной сумме также равно ±1. Так как их сумма равна нулю, количество единиц (обозначим его k) равно количеству минус единиц, то есть  n = 2k.  Произведение всех этих слагаемых равно  (x₁x₂...x_n)² = 1.  Следовательно, количество отрицательных сомножителей (то есть k) чётно. Поэтому  n = 2k  делится на 4.

Решение 2

x₁x₂ + x₂x₃ + ... + x_nx₁ ≡ 0 (mod 4).  Это сравнение остается справедливым при замене знака у любого из чисел x_j. Заменив все числа на единицы, приходим к сравнению  n ≡ 0 (mod 4).

Решение 3

Эта задача эквивалентна задаче 30952: расставим числа по кругу и на место единиц посадим рыцарей из одной страны, а на место минус единиц – рыцарей из другой страны.

Источники и прецеденты использования

web-сайт
задача
книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	3
Название	Сравнения
Тема	Деление с остатком. Арифметика остатков
задача
Номер	04.097
олимпиада
Название	Московская математическая олимпиада
год
Номер	22
Год	1959
вариант
Класс	7
Тур	2
задача
Номер	5
олимпиада
Название	Московская математическая олимпиада
год
Номер	22
Год	1959
вариант
Класс	8
Тур	2
задача
Номер	1
журнал
Название	"Квант"
год
Год	1971
выпуск
Номер	7
Задача
Номер	М93