По кругу расставлено $N$ различных натуральных чисел, каждое из которых не превосходит 365. Сумма любых четырёх идущих подряд чисел делится на 4, а сумма любых трёх идущих подряд чисел нечётна.
а) Может ли $N$ быть равным 200?
б) Может ли $N$ быть равным 109?
в) Найдите наибольшее значение $N.$
Задание с развёрнутым ответом. Запишите решение и сравните его с разбором.
Ответ: а) нет; б) нет; в) 182.
Решение
Обозначим числа по кругу через $a_i$, продолжая индексы по кругу. Например, после $a_N$ снова идёт $a_1$. Сравнение соседних сумм помогает увидеть, как связаны отдельные числа.
Суммы четырёх соседей делятся на 4. Их разность тоже делится на 4:
$$
(a_{i+1}+a_{i+2}+a_{i+3}+a_{i+4})
-(a_i+a_{i+1}+a_{i+2}+a_{i+3})=a_{i+4}-a_i.
$$
Значит, $a_{i+4}$ и $a_i$ имеют одинаковые остатки при делении на 4 и, в частности, одну чётность.
Аналогично две соседние суммы трёх нечётны, поэтому их разность чётна:
$$
(a_{i+1}+a_{i+2}+a_{i+3})-(a_i+a_{i+1}+a_{i+2})=a_{i+3}-a_i.
$$
Чётность повторяется и через три, и через четыре позиции. Отсюда чётность $a_i$ равна чётности $a_{i+4}$, а та — чётности $a_{i+1}$ (они на расстоянии три). Поэтому все соседние числа одной чётности. Если бы все были чётными, любая тройная сумма была бы чётной. Значит, все числа нечётные.
а) Среди чисел от 1 до 365 нечётные $1,3,\ldots,365$. Их количество:
$$
\frac{365-1}{2}+1=182+1=183.
$$
Числа различны, поэтому 200 чисел взять нельзя. Ответ: нет.
б) Покажем, почему при нечётном $N$ все остатки по модулю 4 совпадут. Идя каждый раз на четыре позиции вперёд, попадаем в число с тем же остатком. Этот обход посетит все $N$ позиций: если через $j$ шагов вернулись в начало, то $4j$ делится на $N$; у нечётного $N$ нет общих простых множителей с 4, поэтому $j$ должно делиться на $N$. Первое возвращение возможно только через $N$ шагов.
При $N=109$ все числа должны иметь один остаток при делении на 4. Поскольку они нечётные, остаток либо 1, либо 3. Чисел с остатком 1 от 1 до 365 — $1,5,\ldots,365$, их $(365-1)/4+1=92$. С остатком 3 — $3,7,\ldots,363$, их $(363-3)/4+1=91$. Ни одного вида не хватит на 109 различных чисел. Ответ: нет.
в) Уже доказано $N\le183$. Случай 183 нечётный и исключается тем же рассуждением: пришлось бы взять 183 числа одного остатка, а их не больше 92. Значит, $N\le182$.
Для 182 возьмём все нечётные от 1 до 363. Среди них 91 число с остатком 1 и 91 число с остатком 3. Расположим их поочерёдно: одно из первого вида, одно из второго. Например, можно выписать пары $(1,3),(5,7),\ldots,(361,363)$ по кругу. Из-за чётного количества позиций чередование сохраняется и через замыкание круга.
Любая четвёрка имеет остатки 1,3,1,3 или 3,1,3,1. Их сумма $1+3+1+3=8$ кратна 4. Каждая тройка состоит из нечётных, поэтому её сумма нечётна. Все условия выполнены.
Ответ: а) нет; б) нет; в) 182.