I found this problem from an old math questionnaire.
How many 3-element subsets of {1,2,3,…,11,12,13} are there for which the sum of the 3 elements is divisible by 3?
At first, I tried listing down all of them. But then, I realized they were too many and so, I just stopped. Next, I tried using stars and bars technique. I represented the 3 elements as a,b,c and their sum as a+b+c=m where m is the set of positive integers divisible by 3 from 3 to 39. From there, I tried out each equation with stars and bars from a+b+c=3 to a+b+c=15, and found a total of 185 subsets satisfying the given conditions. I stopped at here since I noticed that if I continued doing this from a+b+c=18 to a+b+c=39, I would have an error since I was not able to limit the values of a,b,c at most 13.
I do not know how to proceed right now. Can anyone help?
Best Answer
Hint: There are five elements of your set that are $1 \bmod 3$, four that are $0 \bmod 3$ and four that are $2 \bmod 3$. You can get a sum that is $0 \bmod 3$ by taking three of the same kind or one of each kind.