Задание олимпиады: Числа ±1, произведения и делимость на 4
Дано n чисел, x1, x2, ..., xn, при этом xk = ±1. Доказать, что если x1x2 + x2x3 + ... + xnx1 = 0, то n делится на 4.
Разобрать решение
Решение 1:Заметим, что каждое слагаемое в указанной сумме также равно ±1. Так как их сумма равна нулю, количество единиц (обозначим его k) равно количеству минус единиц, то есть n = 2k. Произведение всех этих слагаемых равно (x1x2...xn)² = 1. Следовательно, количество отрицательных сомножителей (то есть k) чётно. Поэтому n = 2k делится на 4.
Решение 2:x1x2 + x2x3 + ... + xnx1 ≡ 0 (mod 4). Это сравнение остается справедливым при замене знака у любого из чисел xj. Заменив все числа на единицы, приходим к сравнению n ≡ 0 (mod 4).
Решение 3:Эта задача эквивалентна задаче 130952: расставим числа по кругу и на место единиц посадим рыцарей из одной страны, а на место минус единиц – рыцарей из другой страны.
Обсуждение
0Комментариев пока нет.