20. По кругу расставлено N различных натуральных чисел, каждое из которых не превосходит 400. Сумма любых четырёх идущих подряд чисел делится на 3, а сумма любых трёх идущих подряд чисел не делится на 3. а) Может ли N быть равным 360? б) Может ли N быть равным 149? в) Найдите наибольшее значение N.

Рассмотрим остатки чисел при делении на 3 и обозначим их через a₁, a₂, …, a_N.

Суммы четырёх соседних чисел делятся на 3:

a_i + a_i+1 + a_i+2 + a_i+3 ≡ 0 (mod 3).

Для следующей четвёрки получаем такое же сравнение. Вычитая эти сравнения, имеем:

a_i ≡ a_i+4 (mod 3).

Значит, последовательность остатков периодична с периодом 4.

а) Проверим N = 360.

Так как 360 делится на 4, в каждом блоке из четырёх остатков сумма равна 0 по модулю 3. Сумма любых трёх соседних чисел не делится на 3, поэтому ни один остаток не может быть равен 0: если бы один из четырёх остатков был равен 0, сумма остальных трёх была бы сравнима с 0 по модулю 3.

Следовательно, используются только остатки 1 и 2. Чтобы сумма четырёх остатков делилась на 3, в каждом блоке должны находиться ровно два остатка 1 и два остатка 2. Поэтому среди 360 чисел должно быть по 180 чисел каждого из этих двух видов.

Но среди чисел от 1 до 400 имеется 134 числа с остатком 1 и 133 числа с остатком 2:

1, 4, …, 400 — 134 числа; 2, 5, …, 398 — 133 числа.

Следовательно, 360 различных чисел расставить невозможно.

б) Проверим N = 149.

Из периодичности с периодом 4 и замкнутости круга следует, что период последовательности остатков должен делить НОД(149, 4) = 1. Значит, все остатки одинаковы.

Тогда сумма четырёх остатков даёт 4a ≡ 0 (mod 3), откуда a ≡ 0 (mod 3). Но сумма любых трёх остатков также будет равна 0 по модулю 3, что противоречит условию.

Следовательно, N = 149 невозможно.

в) Найдём наибольшее N.

В последовательности могут использоваться только числа с остатками 1 и 2. В каждом блоке из четырёх чисел должно быть по два числа каждого вида. Поэтому при любом допустимом N количество чисел каждого остатка примерно равно N/2, а при чётном N — ровно N/2.

Чисел с остатком 1 среди чисел от 1 до 400 — 134, а с остатком 2 — 133. Поэтому

N/2 ≤ 133,

откуда N ≤ 266.

Значение 266 достигается: возьмём все 133 числа, сравнимые с 2 по модулю 3, и любые 133 числа, сравнимые с 1 по модулю 3, и расставим их по кругу так, чтобы остатки чередовались:

1, 2, 1, 2, …, 1, 2.

Сумма любых четырёх соседних остатков равна 1 + 2 + 1 + 2 = 6 и делится на 3, а сумма любых трёх равна 4 или 5 и на 3 не делится.

Ответ: а) нет; б) нет; в) 266.