Задача №15460

По кругу расставлено $N$ различных натуральных чисел, каждое из которых не превосходит 400. Сумма любых четырёх идущих подряд чисел делится на 3, а сумма любых трёх идущих подряд чисел не делится на 3.

а) Может ли $N$ быть равным 360?

б) Может ли $N$ быть равным 149?

в) Найдите наибольшее значение $N\text{.}$

а) Рассмотрим остатки от деления чисел на 3: для каждого числа $a_i$ положим $r_i=a_i\mathrm{mod}3\text{,}$ где $r_i\in \{0,1,2\}\text{.}$ Из условия сумма любых четырёх идущих подряд чисел делится на 3, поэтому для любого $i\text{:}$

$$r_i+r_{i+1}+r_{i+2}+r_{i+3}\equiv 0(\mathrm{mod}3).$$

Для следующей четвёрки:

$$r_{i+1}+r_{i+2}+r_{i+3}+r_{i+4}\equiv 0(\mathrm{mod}3).$$

Вычитая, получаем $r_i\equiv r_{i+4}(\mathrm{mod}3)\text{,}$ значит последовательность остатков периодична с периодом 4.

Из условия сумма любых трёх идущих подряд чисел не делится на 3. Рассмотрим период из четырёх остатков: $r_i,r_{i+1},r_{i+2},r_{i+3}\text{,}$ причём $r_{i+4}=r_i\text{.}$ Обозначим $a=r_i\text{,}$ $b=r_{i+1}\text{,}$ $c=r_{i+2}\text{,}$ $d=r_{i+3}\text{,}$ и $a=d\text{.}$ Условия:

1. $a+b+c+d\equiv 0(\mathrm{mod}3)$ (сумма четырёх делится на 3).
2. Суммы трёх подряд не делятся на 3: $a+b+cot\equiv 0\text{,}$ $b+c+d=b+c+aot\equiv 0\text{,}$ $c+d+a=c+2aot\equiv 0\text{,}$ $d+a+b=2a+bot\equiv 0$ (все по модулю 3).

Перебором возможных значений $a,b,c\in \{0,1,2\}$ с учётом $a=d$ показывает, что единственно возможные наборы — это перестановки двух остатков 1 и двух остатков 2. Остаток 0 не встречается. Следовательно, все числа дают остаток 1 или 2 при делении на 3.

Оценим количество различных натуральных чисел, не превосходящих 400, дающих остаток 1 или 2.

Числа вида $3k+1\text{:}$ от 1 до 400, количество $\lfloor \frac{400-1}{3}\rfloor +1=133+1=134\text{.}$

Числа вида $3k+2\text{:}$ от 2 до 398, количество $\lfloor \frac{398-2}{3}\rfloor +1=132+1=133\text{.}$

Всего таких чисел $134+133=267\text{.}$

Для $N=360$ требуется 360 различных чисел, но максимально возможное количество чисел с остатком 1 или 2 равно 267, и $360>267\text{.}$ Следовательно, $N$ не может быть равным 360.

Ответ: нет.

б) Из периодичности остатков с периодом 4 следует, что количество чисел $N$ должно быть кратно 4. Число 149 не делится на 4, поэтому не может быть таким $N\text{.}$

Ответ: нет.

в) Поскольку $N$ кратно 4 и все числа имеют остатки 1 или 2, и в каждом периоде из 4 остатков два остатка 1 и два остатка 2, то общее количество чисел с остатком 1 равно количеству чисел с остатком 2 и равно $N/2\text{.}$ Поэтому необходимо, чтобы $N/2$ не превышало количества доступных чисел с остатком 1 и с остатком 2. Наибольшее количество чисел с остатком 2 равно 133, поэтому $N/2\le 133\text{,}$ откуда $N\le 266\text{.}$ Также $N$ должно быть кратно 4. Наибольшее кратное 4, не превосходящее 266, это 264. Покажем, что $N=264$ возможно.

Для $N=264$ нужно выбрать 132 числа с остатком 1 и 132 числа с остатком 2. Это возможно, так как имеется 134 числа с остатком 1 и 133 числа с остатком 2. Например, возьмём все числа с остатком 1, кроме 1 и 400 (исключаем два числа), и все числа с остатком 2, кроме 398 (исключаем одно число). Тогда получим 132 числа с остатком 1 (от 4 до 397 с шагом 3) и 132 числа с остатком 2 (от 2 до 395 с шагом 3). Расположим эти числа по кругу в порядке, соответствующем периодической последовательности остатков, например, повторяя блок остатков $1,2,1,2$ или $1,1,2,2$ и т.п., что удовлетворяет условиям на суммы.

Следовательно, наибольшее возможное значение $N$ равно 264.

Ответ: 264.