Given set $S = \{ xy\left( {x + y} \right)\; |\; x,y \in \mathbb{N}\}$.Let $a$ and $n$ natural numbers such that $a+2^k\in S$ for all $k=1,2,3,...,n$.Find the greatest value of $n$.
Problem
Source: Kazakhstan MO 2018 final round.Grade 11;Problem 5
Tags: number theory, Kazakhstan
qweDota
04.05.2018 14:44
It is easy to see that for all natural $ x $ and $ y $ ;$ xy (x + y) \equiv 0, \, 2, \, 3, \, 6, \, 7 \pmod9. $Hence $s \not \equiv 1, \, 4, \, 5, \, 8 \pmod 9 $ for any $ s \in S $. Note that $ 2 ^ 6 \equiv 1 \pmod 9 $.
Now, for each $ a \equiv 0, \, 1, \, \ldots, \, 8 \pmod 9 $ we write out the numbers $ a + 2 ^ i \pmod 9 $, where $ 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. $$Hence, for each $ a \equiv 0, 1, \ldots, 8 \pmod 9 $ and $ 1 \le i \le 6 $, at least one of the numbers $ a + 2 ^ i $, $ a + 2 ^ { i + 1} $, $ a + 2 ^ {i + 2} $, $ a + 2 ^ {i + 3} $ gives the remainder $1, 4, 5 $ or $8$ when divided by $9$. This means $ n \le 3 $ .
For $ n = 3 $, the number $ a = 124 $ is suitable, since $$ 126 = 2 \cdot7 \cdot (2 + 7), \quad 128 = 4 \cdot4 \cdot (4 + 4), \quad 132 = 1 \cdot 11 \cdot (1 + 11)$$.Hence the answer is $\boxed{3}$