Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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 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 at 10:14
1  
Ohh thank you to aware me. Now I will accept the answer. –  Satvik Mashkaria Apr 24 at 11:19

1 Answer 1

up vote 14 down vote accepted

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$.

share|improve this answer
2  
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 at 16:57
    
Given the question title, maybe "hence each remainder occurs at least once" should have a lampshade hung on it. If any remainder occurs 0 times then we're trying to put 5 pigeons into two holes and hence one remainder occurs at least thrice, contrary to what was assumed. –  Steve Jessop Apr 22 at 18:17
    
@SteveJessop I don't understand the lampshade analogy. Does that mean you want to make that point less visible? I get the feeling you meant the opposite –  Cruncher Apr 22 at 18:20
2  
@Cruncher: oh sorry, by "hang a lampshade" I mean make it more obvious as you say. tvtropes.org/pmwiki/pmwiki.php/Main/LampshadeHanging defines it as "dealing with any element of the story that threatens the audience's Willing Suspension of Disbelief ... by calling attention to it and simply moving on". Here I mean call attention to the fact that Pigeonhole principle is used here in the proof, although for a small finite case you normally wouldn't (and Hagen didn't) actually cite it. –  Steve Jessop Apr 22 at 18:21
    
@SteveJessop Well, the pigeon-hole principle is in fact used twice (the other instance being: Three integer-pigeons are put into two parity-holes). Added lampshades accordingly –  Hagen von Eitzen Apr 23 at 15:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.