China Mathematical Olympiad

Let $a_1=a_2=1$, $a_3=a_4=3$, $a_5=\cdots =a_{12}=0$. It is easy to check that any 9 integers of them will not meet the requirement. So $n\ge 13$. We will prove that $n=13$.

We only need to prove the following statement: Given a group of $m$ integers $a_1,a_2,\dots ,a_m$, if there are not three $a_{i_1},a_{i_2},a_{i_3}$ in them and $b_1,b_2,b_3\in \{4,7\}$ such that $b_1{a}_{i_1}+b_2{a}_{i_2}+b_3{a}_{i_3}\equiv 0(\mathrm{mod}9)$, then either $m\le 6$ or $7\le m\le 8$ and there are $a_{i_1},a_{i_2},\dots ,a_{i_6}$ in $a_1,a_2,\dots ,a_m$ and $b_1,b_2,\dots ,b_6\in \{4,7\}$ such that $9\mid b_1{a}_{i_1}+b_2{a}_{i_2}+\cdots +b_6{a}_{i_6}$.

We define $$A_1=\{i\mid 1\le i\le m,9\mid a_i\},$$ $$A_2=\{i\mid 1\le i\le m,a_i\equiv 3(\mathrm{mod}9)\},$$ $$A_3=\{i\mid 1\le i\le m,a_i\equiv 6(\mathrm{mod}9)\},$$ $$A_4=\{i\mid 1\le i\le m,a_i\equiv 1(\mathrm{mod}3)\},$$ $$A_5=\{i\mid 1\le i\le m,a_i\equiv 2(\mathrm{mod}3)\}.$$ Then $|A_1|+|A_2|+|A_3|+|A_4|+|A_5|=m$ and

(1) if $i\in A_2,j\in A_3$ then $9\mid 4a_i+4a_j$;

(2) if $i\in A_4,j\in A_5$ then one of $4a_i+4a_j,4a_i+7a_j$ and $7a_i+4a_j$ is a multiple of 9 as all of them are divisible by 3 and they are distinct according to mod 9;

(3) if either $i,j,k\in A_2$ or $i,j,k\in A_3$ then $9\mid 4a_i+4a_j+4a_k$;

(4) if either $i,j,k\in A_4$ or $i,j,k\in A_5$ then one of $4a_i+4a_j+4a_k,4a_i+4a_j+7a_k$ and $4a_i+7a_j+7a_k$ is a multiple of 9 as all of them are divisible by 3 and they are distinctive according to mod 9.

By the assumption, we have $|A_i|\le 2$ ($1\le i\le 5$).

If $|A_1|\ge 1$, then $|A_2|+|A_3|\le 2$, $|A_4|+|A_5|\le 2$. Hence $$m=|A_1|+|A_2|+|A_3|+|A_4|+|A_5|\le 6.$$ Now assume $|A_1|=0$ and $m\ge 7$. Then $$7\le m=|A_1|+|A_2|+|A_3|+|A_4|+|A_5|\le 8.$$ Further, $$\min \{|A_2|,|A_3|\}+\min \{|A_4|,|A_5|\}\ge 3.$$ From (1) and (2) we know there exist $i_1,i_2,\dots ,i_6\in A_2\cup A_3\cup A_4\cup A_5$ ($i_1<i_2<\cdots <i_6$) and $b_1,b_2,\dots ,b_6\in \{4,7\}$ such that $9\mid b_1{a}_{i_1}+b_2{a}_{i_2}+\cdots +b_6{a}_{i_6}$. The proof of statement is complete.

Now, when $n\ge 13$ it is easy to verify with the statement, for any group of integers $a_1,a_2,\dots ,a_n$, there always exist $a_{i_1},a_{i_2},\dots ,a_{i_9}$ ($1\le i_1<i_2<\cdots <i_9\le n$) and $b_i\in \{4,7\}$ ($i=1,2,\dots ,9$) such that $b_1{a}_{i_1}+b_2{a}_{i_2}+\cdots +b_9{a}_{i_9}$ is a multiple of 9. That completes the proof.