Республиканская олимпиада по математике, 2018 год, 11 класс


Дано множество $S = \{ xy\left( {x + y} \right)\; |\; x,y \in \mathbb{N}\}$. Пусть $a$ и $n$ натуральные числа такие, что $a+2^k\in S$ для каждого $k=1,2,\ldots,n.$ Найдите наибольшее возможное значение $n.$ ( Сатылханов К. )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Ответ: 3.
Решение. Легко заметить, что при всех натуральных $x$ и $y$ $$xy(x+y)\equiv 0,\, 2,\, 3,\, 6,\, 7 \pmod9 .$$ Следовательно, $s \not \equiv 1,\, 4,\, 5,\, 8 \pmod 9$ для любого $s \in S$. Заметим, что $2^6 \equiv 1 \pmod 9$.
  Теперь, для каждого $a \equiv 0,\, 1,\, \ldots,\, 8 \pmod 9$ выпишем числа $a+2^i \pmod 9$, где $1 \le i \le 9$. $$2, \ 4, \ 8, \ 7, \ 5, \ 1, \ 2, \ 4, \ 8;$$ $$3, \ 5, \ 0, \ 8, \ 6, \ 2, \ 3, \ 5, \ 0;$$ $$4, \ 6, \ 1, \ 0, \ 7, \ 3, \ 4, \ 6, \ 1;$$ $$5, \ 7, \ 2, \ 1, \ 8, \ 4, \ 5, \ 7, \ 2;$$ $$6, \ 8, \ 3, \ 2, \ 0, \ 5, \ 6, \ 8, \ 3;$$ $$7, \ 0, \ 4, \ 3, \ 1, \ 6, \ 7, \ 0, \ 4;$$ $$8, \ 1, \ 5, \ 4, \ 2, \ 7, \ 8, \ 1, \ 5;$$ $$0, \ 2, \ 6, \ 5, \ 3, \ 8, \ 0, \ 2, \ 6;$$ $$1, \ 3, \ 7, \ 6, \ 4, \ 0, \ 1, \ 3, \ 7.$$
  Отсюда видно, что для каждого $a \equiv 0, 1, \ldots, 8 \pmod 9$ и $1 \le i \le 6$ хотя бы одно из чисел $a+2^i$, $a+2^{i+1}$, $a+2^{i+2}$, $a+2^{i+3}$ дает остаток 1, 4, 5 или 8 при делении на 9. Значит $n \le 3$.
  Для $n=3$ подходит число $a=124$, так как $$ 126 =2\cdot7\cdot(2+7), \quad 128=4\cdot4\cdot(4+4), \quad 132 = 1 \cdot 11\cdot(1+11).$$