Prove that from any set of $11$ natural numbers, there exists 6 numbers such that their sum is divisible by $6$.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Lemma. From any set of five natural numbers we can pick three so that their sum is a multiple of $3$.
Proof: If three of the numbers have the same remainder $\pmod 3$, their sum is a multiple of $3$ and we are done. Thus assume each remainder occurs at most twice, hence - by the pigeon-hole principle - each remainder occurs at least once. But $0+1+2\equiv 0\pmod 3$. $_\square$
By the lemma, pick three numbers $a_1,a_2,a_3$ with $3\mid a_1+a_2+a_3$. Form the remaining $8$ numbers pick $b_1,b_2,b_3$ with $3\mid b_1+b_2+b_3$. Froim the remaining five numbers pick $c_1,c_2,c_3$ with $3\mid c_1+c_2+c_3$. Among the three numbers $a_1+a_2+a_3$, $b_1+b_2+b_3$, $c_1+c_2+c_3$, two must have the same parity (again by the pigeon-hole principle). Together we obtain six numbers whose sum is divisible by both $3$ and $2$, hence by $6$.