Қалалық Жәутіков олимпиадасы, 9 сынып, 2017 жыл

1, 2, $\ldots$, 299, 300 сандары берілген. Осы сандардан, қандай да бір ретпен қатарға орналастырғанда, пайда болған сандар тізбегі төмендегі шартты қанағаттандыратындай ең көп дегенде қанша сан таңдап алуға болады:
1) кез келген қатар орналасқан төрт санның қосындысы 3-ке бөлінбейді;
2) кез келген қатар орналасқан бес санның қосындысы 3-ке бөлінеді.

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ: 126.
Решение. Заменим для удобства все числа их остатками при делении на 3 (от этого делимость или неделимость на 3 не изменится). Тогда у нас имеется ровно по 100 чисел (остатков) 0, 1 и 2. Следующий ряд $$2,1,1,1,1,2,1,1,1,1,2,\ldots ,1,1,1,1,2,$$ в котором использованы все 100 чисел 1 и 26 чисел 2 (они повторяются через каждые 4 единицы), удовлетворяет условию задачи. Всего в этом примере 126 чисел. Покажем, что больше, чем 126, чисел с соблюдением условия задачи выбрать и расставить так, как требуется, нельзя. Пусть последовательность чисел $${{a}_{1}},{{a}_{2}},{{a}_{3}},\ldots ,{{a}_{n}} \quad (*)$$ удовлетворяет условиям 1) и 2). Ввиду приведённого примера можем считать, что $n\ge 127.$ Тогда для любого числа из последовательности $(*)$ найдутся ещё по крайней мере 4 числа, стоящие либо слева от него, либо справа.
Пусть, для определённости, справа от числа $a$ расположены еще числа $b,c,d,e$. Тогда, по условию, число $a+b+c+d+e$ делится на 3, а число $b+c+d+e$ на 3 не делится. Поэтому $a$ не делится на 3. Таким образом, среди чисел последовательности $(*)$ нет чисел, кратных 3, т.е. (поскольку мы их заменили остатками) нет чисел 0, и, значит, есть только числа 1 и 2.
Рассмотрим любую пятёрку подряд идущих чисел последовательности $ (*)$, сумма которых, по условию, делится на 3. Среди них есть по крайней мере 3 одинаковых числа, поэтому их сумма делится на 3. Тогда и сумма двух оставшихся чисел делится на 3. Но эти два оставшихся числа могут быть только 1 и 2. Таким образом, для всех пятёрок подряд идущих чисел последовательности $(*)$ имеет место альтернатива: либо в каждой из них четыре 1 и одна 2, либо в каждой из них четыре 2 и одна 1.
Разобьём теперь все числа последовательности (*) на пятёрки подряд идущих чисел; в конце, возможно, останется неполная пятёрка. Пусть, для определённости, в любой пятёрке по 4 единицы и 1 двойка. Так как всего имеется 100 единиц и в каждой пятёрке их четыре, то полных пятёрок не более $100:4=25$. А если их ровно 25, то оставшаяся (неполная) пятёрка может состоять только из одного числа: единиц уже нет, а подряд стоящих двоек может быть не более одной. Итого, в последовательности $(*)$ не более $25\cdot 5+1=126$ чисел.