По кругу расставлено N различных натуральных чисел, каждое из которых не превосходит 400. Сумма любых четырёх идущих подряд чисел делится на 3 , а сумма любых трёх идущих подряд чисел не делится на 3. а) Может ли N быть равным 360? б) Может ли N быть равным 149? в) Найдите наибольшее значение N.
Решение
Сначала заметим, что среди чисел не может быть кратных 3. Действительно, если есть число a, кратное 3, то рассмотрим четвёрку чисел, в которую оно входит. Сумма этой четвёрки делится на 3, значит, и сумма остальных трёх чисел в этой четвёрке тоже делится на 3, что противоречит условию (сумма любых трёх подряд не делится на 3). Следовательно, все числа дают остатки 1 или 2 при делении на 3.
Всего натуральных чисел от 1 до 400, не кратных 3, равно 400−133=267.
а) Если N=360, то нам нужно 360 чисел, не кратных 3, но их всего 267. Поэтому N не может быть равно 360.
б) Рассмотрим последовательность чисел по кругу: a1,a2,a3,a4,a5,…. Из делимости сумм четырёх подряд на 3 получаем, что a1≡a5(mod3),a2≡a6(mod3) и т.д. То есть остатки чисел периодичны с периодом 4. При N=149 числа 149 и 4 взаимно просты, поэтому, обойдя весь круг, получим, что все числа имеют одинаковый остаток. Тогда сумма любой тройки делится на 3 — противоречие.
в) Наибольшее возможное N не может превышать 267. При N=267 числа 267 и 4 взаимно просты (так как 267 не кратно 4), значит, как в пункте б), все числа имели бы одинаковый остаток — противоречие. Следовательно, N должно быть кратно 4.
Если N кратно 4, то можно расставить числа, чередуя остатки 1 и 2. Например, последовательность остатков 1,2,1,2,… по кругу. Тогда сумма любых четырёх подряд: 1+2+1+2=6 делится на 3. Сумма любых трёх подряд: либо 1+2+1=4, либо 2+1+2=5 — ни одно не делится на 3. Условие выполнено.
Наибольшее N, кратное 4 и не превосходящее 267, это N=266. Чисел с остатком 1 от 1 до 400 имеется 134, с остатком 2 — 133. Для чередования при N=264 нужно поровну: 133 числа с остатком 1 и 133 с остатком 2. Это возможно, так как чисел каждого типа достаточно. Выбираем любые 133 числа с остатком 1 и 133 с остатком 2 и расставляем их с чередованием остатков.
