ID: 00008998
По кругу расставлено N различных натуральных чисел, каждое из которых не превосходит 365. Сумма любых четырёх идущих подряд чисел делится на 4, а сумма любых трёх идущих подряд чисел нечётна.
а) Может ли N быть равным 200?
б) Может ли N быть равным 109?
в) Найдите наибольшее значение N.
Источник: ФИПИ
Что дано: по кругу стоят N различных натуральных чисел, каждое \leqslant 365. Сумма любых четырёх подряд делится на 4, а сумма любых трёх подряд нечётна. Из этих условий вытащим, какими вообще могут быть числа.
Обозначим числа по кругу a_1,a_2,\dots,a_N. Сумма трёх подряд всегда нечётна: a_i+a_{i+1}+a_{i+2} и a_{i+1}+a_{i+2}+a_{i+3} нечётны, значит их разность a_i-a_{i+3} чётна — числа на расстоянии 3 одной чётности. Сумма четырёх подряд кратна 4: вычитая соседние такие суммы, получаем a_i\equiv a_{i+4}\pmod 4 — в частности, и одной чётности на расстоянии 4.
Чётность повторяется с шагом 3 и с шагом 4. Но если что-то имеет период 3 и период 4 одновременно, оно вообще постоянно. Значит все числа одной чётности. А так как сумма трёх нечётна — эта чётность нечётная. Все числа нечётные.
Пункт а). Может ли N=200? Различных нечётных чисел, не превосходящих 365, всего 183 (это 1,3,5,\dots,365). Больше 183 различных нечётных взять неоткуда, поэтому N\leqslant 183\lt 200. Значит — нет.
Пункт б). Может ли N=109? Условие a_i\equiv a_{i+4}\pmod 4 связывает места через 4. Так как 109 и 4 взаимно просты, шаги по 4 обходят весь круг, и все числа получают один и тот же остаток по модулю 4. Нечётные числа \leqslant 365 с остатком 1 — это 1,5,\dots,365 (их 92); с остатком 3 — это 3,7,\dots,363 (их 91). В любом случае различных не больше 92, а 109\gt 92. Значит — нет.
Пункт в). Чтобы N было побольше, хочется использовать оба остатка 1 и 3 по модулю 4. Это возможно, когда N делится на 2, но не на 4 (тогда шаги по 4 разбивают круг на чётные и нечётные позиции, и на них можно держать разные остатки). Поставим на одни позиции числа с остатком 1, на другие — с остатком 3.
Проверим условия: сумма четырёх подряд = два числа с остатком 1 плюс два с остатком 3 \equiv 2\cdot 1+2\cdot 3=8\equiv 0\pmod 4 — годится; сумма трёх нечётных нечётна — годится. Чисел с остатком 3 всего 91, значит таких позиций не больше 91, а столько же позиций с остатком 1. Поэтому N\leqslant 182. Набор из 91 числа с остатком 1 и 91 с остатком 3 (всего 182) такой круг даёт. Наибольшее N — 182.
а) нет; б) нет; в) 182.