Let $X$ be a set of $11$ integers. Prove that one can find a nonempty subset $\{a_1, a_2, \cdots , a_k \}$ of $X$ such that $3$ divides $k$ and $9$ divides the sum $\sum_{i=1}^{k} 4^i a_i$.
Problem
Source: RMO KV 2024 Q6
Tags: combinatorics
04.11.2024 17:08
Bump.....
05.11.2024 17:07
Lemma. Given any $5$ integers, one can pick $3$ of them whose sum is divisible by $3$. Proof: Look at the residues modulo $3$. If $0, 1 , 2$ are all present, then the sum of one element of each type is $0$ modulo $3$. Otherwise, by PHP, there are three elements with same residue modulo $3$. In that case, the sum of these $3$ elements is divisible by $3$. $\spadesuit$ Now, by repeated applications of Lemma 1, from our $11$ numbers, we can pick three disjoint subsets of length three each $A= \{a_1, a_2, a_3\}$, $B=\{b_1, b_2, b_3\}$ and $C=\{c_1, c_2, c_3\}$ such that their sums are divisible by $3$. Therefore $a= a_1+4 a_2+ 7a_3$, $b = b_1 +4b_2 + 7b_3$ and $c= c_1+4c_2+ 7c_3$ are also all divisible by $3$. Now, by Pigeonhole Principle, two of the terms $0, \dfrac{a}{3}, \dfrac{a}{3}+\dfrac{b}{3}, \dfrac{a}{3}+\dfrac{b}{3}+\dfrac{c}{3}$ has same residue modulo $3$. subtracting, we will see that one of $a, b, c, a+b, b+c, a+b+c$ must be divisible by $9$. Now, $\displaystyle\sum_{i=1}^{3d}4^{i-1} a_i \equiv \displaystyle\sum_{i=1}^{d} (a_{3d-2}+4a_{3d-1}+7a_{3d}) \pmod{9}$. Therefore, we are done. $\blacksquare$