Теория чисел: По кругу расставлено N различных натуральных... — задача

Условие, ответ и разбор задачи

Числа и их свойстваФИПИ

По кругу расставлено

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.

б) Рассмотрим последовательность чисел по кругу:

a_1, a_2, a_3, a_4, a_5, \dots

. Из делимости сумм четырёх подряд на 3 получаем, что

a_1 \equiv a_5 \pmod{3}

a_2 \equiv a_6 \pmod{3}

и т.д. То есть остатки чисел периодичны с периодом 4. При

N = 149

числа 149 и 4 взаимно просты, поэтому, обойдя весь круг, получим, что все числа имеют одинаковый остаток. Тогда сумма любой тройки делится на 3 — противоречие.

в) Наибольшее возможное

N

не может превышать 267. При

N = 267

числа 267 и 4 взаимно просты (так как 267 не кратно 4), значит, как в пункте б), все числа имели бы одинаковый остаток — противоречие. Следовательно,

N

должно быть кратно 4.

Если

N

кратно 4, то можно расставить числа, чередуя остатки 1 и 2. Например, последовательность остатков

1,2,1,2,\dots

по кругу. Тогда сумма любых четырёх подряд:

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 и расставляем их с чередованием остатков.

Таким образом, наибольшее

N = 266

.

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

266.

Теория чисел: По кругу расставлено N различных натуральных... — задача

Похожие задачи