Find the number of ways to write $24$ as the sum of at least three positive integer multiples of $3$. For example, count $3+18+3$, $18+3+3$, and $3+6+3+9+3$, but not $18+6$ or $24$. (PurpleComet 2023, Middle School, Problem 8) Click here for the solutions.
Solution 1: The problem is equivalent to write $8$ as the sum of at least three positive integers.
Case 1: There are $8$ $1$s in the sum, i.e. $1+1+1+1+1+1+1+1$. There is only $1$ way.
Case 2: There are $6$ $1$s in the sum, i.e. $1+1+1+1+1+1+2$. There are $7$ ways.
Case 3: There are $5$ $1$s in the sum, i.e. $1+1+1+1+1+3$. There are $6$ ways.
Case 4: There are $4$ $1$ in the sum, with the following sub-cases:
Case 4.1: For sum as $1+1+1+1+4$, there are $5$ ways.
Case 4.2: For sum as $1+1+1+1+2+2$, there are $\dfrac{6!}{4!\cdot 2!}=15$ ways.
Case 5: There are $3$ $1$s in the sum, with the following sub-cases:
Case 5.1: For sum as $1+1+1+5$, there are $4$ ways.
Case 5.2: For sum as $1+1+1+3+2$, there are $\dfrac{5!}{3!\cdot 1!\cdot 1!}=20$ ways.
Case 6: There are $2$ $1$s in the sum, with the following sub-cases:
Case 6.1: For sum as $1+1+6$, there are $3$ ways.
Case 6.2: For sum as $1+1+4+2$, there are $\dfrac{4!}{2!\cdot 1!\cdot 1}=12$ ways.
Case 6.3: For sum as $1+1+3+3$, there are $\dfrac{4!}{2!\cdot 2!}=6$ ways.
Case 6.4: For sum as $1+1+2+2+2$, there are $\dfrac{5!}{2!\cdot 3!}=10$ ways.
Case 7: There are $1$ $1$s in the sum, with the following sub-cases:
Case 7.1: For sum as $1+5+2$, there are $6$ ways.
Case 7.2: For sum as $1+4+3$, there are $6$ ways.
Case 7.3: For sum as $1+3+2+2$, there are $\dfrac{4!}{1!\cdot 1!\cdot 2!}=12$ ways.
Case 8: There is no $1$s in the sum, with the following sub-cases:
Case 8.1: For sum $2+2+2+2$, there is only $1$ way.
Case 8.2: For sum $2+2+4$, there are $3$ ways.
Case 8.3: For sum $2+3+3$, there are $3$ ways.
Combining all the above cases, the answer to the question is:
$$1+7+6+5+15+4+20+3+12+6+10+6+6+12+1+3+3=\boxed{120}$$
Solution 2: The problem is equivalent to write $8$ as the sum of at least three positive integers, which is the same as placing $8$ identical balls into $n$ unique boxes, where $n=3,4,5,6,7,8$.
Case 1: Place 8 $1$s into $8$ different boxes, with each box contains at least $1$s. There is only ${{8-1}\choose{8-1}}=1$ way.
Case 2: Place 8 $1$s into $7$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{7-1}}=7$ ways.
Case 3: Place 8 $1$s into $6$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{6-1}}=21$ ways.
Case 4: Place 8 $1$s into $5$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{5-1}}=35$ ways.
Case 4: Place 8 $1$s into $4$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{4-1}}=35$ ways.
Case 5: Place 8 $1$s into $3$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{3-1}}=21$ ways.
Combining all the above cases, the answer to the question is:
$$1+7+21+35+35+21=\boxed{120}$$
Solution 3: The problem is equivalent to write $8$ as the sum of at least three positive integers. The total ways of writing $8$ as the sum of any positive integers, without any restrictions, including singleton, is $2^{8-1}=128$, as there are at most $8-1=7$ plus signs $(+)$ that can be used in a sum.
There is $1$ way to write $8$ as the sum of only one positive integers (singleton). And there are $7$ ways to write $8$ as the sum of only two positive integers.
Therefore, by complementary principle, the answer to the question is: $$128-1-7=\boxed{120}$$