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

Последовательность целых чисел $a_1$, $a_2$, $\dots $ определяется следующим образом: $a_1=1$ и $n > 1$, $a_{n+1}$ наименьшее целое число больше $a_n$ и такое, что $a_i+a_j\neq 3a_k$ для любых $i, j$ и $k$ из $\{1, 2, \dots, n+1\}$ не обязательно разные. Определить $a_{2004}$.

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

Можно вычислить первые $a_1=1, \ a_2=3, \ a_3=4, \ a_{4}=7$ небольшим перебором, но теперь покажем что дальше будет закономерность вида $a_{1+4t}=1+9t, \ a_{2+4t}=3+9t, \ a_{3+4t}=4+9t, \ a_{4+4t}=7+9t$ при $t>0$

Отметим что всевозможные попарные суммы $a_{i}+a_{j} \equiv 1,2,4,5,6,7,8 \pmod {9} $ в то время как правая часть $3a_{k} \equiv 0,3 \pmod {9}$

Значит равенство в принципе невозможна, числа с остатками $0,2,5,6,8$ выбирать нельзя, так как $ a{j}= 3a_{k}- a_{i} $ сравнимо либо $a_{j} \equiv 3-(1,3,4,7) \equiv 2,0,8,5 \mod 9$ или $a_{j} = 0 - (1,3,4,7) \equiv 8,6,5,2 \mod 9$ не может принимать вид $9m,9m+2,9m+5,9m+6,9m+8$

Значит $a_{2004} = 7+9 \cdot 500 = 4507$