# An application of Pigeon Hole Principle

Prove that from any set of $11$ natural numbers, there exists 6 numbers such that their sum is divisible by $6$.

-
First note that this is quite a hard question (at least I think so, if you haven't seen the solution). Second, it would be good to know what you have tried and the context in which the pigeonhole principle is mentioned. – Mark Bennet Apr 22 '14 at 16:41
Satvik, you have asked 17 questions, and accepted answers on none of them. Are you aware you can do this by clicking on the checkmark next to the answer? This thanks the person who answered you, and also indicates for future readers looking for things to answer that their help might not be needed. – Jack M Apr 24 '14 at 10:14
Ohh thank you to aware me. Now I will accept the answer. – Satvik Mashkaria Apr 24 '14 at 11:19

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$.
And note that $10$ natural numbers won't necessarily do it e.g. $1,1,1,1,1,6,6,6,6,6$ – Mark Bennet Apr 22 '14 at 16:57