Математикадан республикалық олимпиада, 2003-2004 оқу жылы, 11 сынып

${{a}_{1}},{{a}_{2}},\ldots $ бүтін сандардың тізбегі келесі түрде табылады: ${{a}_{1}}=1$ және $n\ge 1$ үшін ${{a}_{n+1}}$ ең кішкентай бүтін сан ${{a}_{n}}$-нен үлкен және ${{a}_{i}}+{{a}_{j}}\ne 3{{a}_{k}}$ кез келген $i,j$ және $k$ үшін, $i,j$ және $k$ тиісті $\left\{ 1,2,\ldots ,n+1 \right\}$ және $k$ әртүрлі болуы міндетті емес. ${{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$