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.

In how many ways we can choose three numbers from first $11$ natural numbers $(1,2,\cdots,11)$ so that their sum is a multiple of $3$?

I tried using "stars and bars", but as this is about selection i.e $(1,2,3)$ is same as $(3,2,1)$ it's not giving the right answer, any other ideas?

share|improve this question
    
Just to clarify: do the three numbers have to be distinct? From the phrasing it looks like they probably do. –  Tara B Apr 26 '12 at 8:56
    
@Tara B: Yes, they are. –  Quixotic Apr 26 '12 at 8:57
add comment

3 Answers 3

up vote 8 down vote accepted

You might as well work modulo $3$. So what you have are three $0$s, four $1$s and four $2$s, and you need to select combinations that add up to $0$ mod $3$.

share|improve this answer
    
Aha, Thanks that helps! –  Quixotic Apr 26 '12 at 8:56
1  
Good! Especially because you used the tag 'contest-math', I presumed you were looking for just a hint rather than a full solution. –  Tara B Apr 26 '12 at 8:57
add comment

Given two of the numbers, only certain choices for the third number will give you a multiple of 3 as your total. It appears to me that regardless of what the first two numbers total to, roughly one third of the remaining numbers will be suitable.

There are thus 11 choices for the first number, 10 choices for the second number, and roughly 3 valid choices for the third number, yielding about 330 possible sequences.

If you're saying that the ordering doesn't matter, then I'd guess you need to divide 330 by the number of possible ways that 3 items can be rearranged (i.e., 6). That gives 55.

That's my guess. Now to go try an exhaustive search and see what the actual answer is...

Edit: It appears the exact answer is 342 ordered combinations, or 57 unordered ones. This is close to my estimate above.

share|improve this answer
1  
It's much easier than this. –  Tara B Apr 26 '12 at 8:56
    
The answer is $57$. –  Quixotic Apr 26 '12 at 9:02
    
Yes, it was a good estimate. –  Tara B Apr 26 '12 at 9:07
    
Your answer was better. –  MathematicalOrchid Apr 26 '12 at 9:08
add comment

Suppose that you have $n$ distinct numbers, of which $a$ are congruent to $0$ modulo $3$, $b$ are congruent to $1$, and $c$ are congruent to $2$.

There are two ways that a sum of $3$ numbers chosen from these can be divisible by $3$: (i) all the chosen numbers are distinct modulo $3$ or (ii) all the chosen numbers are congruent modulo $3$.

There are $\binom{a}{1}\binom{b}{1}\binom{c}{1}$ possibilities of type (i) and $\binom{a}{3}+\binom{b}{3}+\binom{c}{3}$ possibilities of type (ii).

share|improve this answer
add comment

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.