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

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?

• 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

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

• Aha, Thanks that helps! – Quixotic Apr 26 '12 at 8:56
• 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

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

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.

• 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