Can someone check which logic is finally correct?:
In how many ways can three numbers be selected from the numbers $1,2,\dots,300$ such that their sum is divisible by $3$?
I found different answers about the exact question but everyone states something different.
Dividing $\{1, \dots , 300\}$ into three groups $(A,B,C)$ where each one of them has $100$ numbers in it and ${}\bmod 3$ results in $0$ or $1$ or $2$ seems correct as a first step.
Then if we want the sum of the three numbers to be divisible by $3$ we should take cases:
- All of them belong to one of the groups: $ {{100}\choose{3}} + {{100}\choose{3}} + {{100}\choose{3}} $
- We take one from each group: $ {{100}\choose{1}} × {{100}\choose{1}} × {{100}\choose{1}} $
The answer ends there by adding the above numbers (because one of them can happen).
But what about combinations such as:
Taking one number from the group that gives remainder $1$ and two numbers from the group that gives remainder $2$??
Best Answer
So we can choose the first two numbers how we like. The third has to have a definite residue class mod $3$ to make the total divisible by $3$.
If the third residue class is distinct from the residue class the first two numbers, the first two have to be from different residue classes. The number of ways of choosing one from each residue class is $\binom {300}1 \times \binom {200}1 \times\binom {100}1$, but there are six different orders in which the same three numbers can be selected.
If the final residue class is the same as one of the previous ones, they all have to be the same. We choose one of the three residue classes, and there are then $\binom {100}3$ ways of choosing a triple.
So the overall number of ways is $$\frac 16\times\binom {300}1 \times \binom {200}1 \times\binom {100}1+3\times\binom {100}3$$
And this is equal to $$\binom {100}1 \times \binom {100}1 \times\binom {100}1+3\times\binom {100}3$$