# In how many way can the number $100$ be expressed as a sum of $3$ different positive integers?

Australian Mathematics Competition 2022 Junior Level Question 30:

In how many way can the number $$100$$ be expressed as a sum of $$3$$ different positive integers?

The way I tried to approach the problem was to assume the first integer was $$1$$. As the integers had to be different, the possible values were from $$1+2+97$$ to $$1+97+2$$ thus there are $$96$$ ways. If we start from $$2$$, then the possibilities will range from $$2+3+95$$ to $$2+95+3$$ and there are $$95$$ ways. Thus there are $$96+95+94+\ldots+1$$ ways. Using the formula $$n(n+1)/2$$, the answer is $$4656$$. But we overcounted so we have to divide again by $$3!$$. So $$4656/6=776$$. There are $$776$$ ways but this answer is wrong.

Can anybody assist me with this problem?

Thanks.

Slightly less technical solution. Note that the number of solutions to $$x_1 + x_2 + x_3 = 100$$ is just $$\binom{99}{2}$$ by "Stars and Bars." There are no solution with $$x_1 = x_2 = x_3$$. Now consider the set of solutions with exactly two of the same numbers. They are of the form $$((1,1,98),\dots,(49,49,2)).$$ Clearly, there are $$49$$ of these, each of which can be permuted in three ways. Therefore, the total number of tuples with distinct $$x_1, x_2, x_3$$ is just $$\binom{99}{2} - 49 \cdot 3$$. Each of these are counted six times by your own reasoning. Therefore, the total number of ways $$100$$ can be expressed as the sum of three positive integers is just $$\frac{\binom{99}{2} - 49\cdot 3}{6} = \frac{99 \cdot 49 - 3 \cdot 49}{6} = \frac{96 \cdot 49}{6} = 16 \cdot 49 = 28^2 = \fbox{784}.$$
First, we can see that your solution does not work because, for instance, in the sequence of sums $$2+3+95, \\ 2+4+94, \\ \vdots \\2+95+3,$$ there is one instance where the last two terms are equal, and you have counted this: $$2+49+49.$$
If $$a+b+c = 100$$ where $$1 \le a < b < c$$ are positive integers, then clearly we must have $$1 \le a \le 32$$, since if $$a \ge 33$$, then $$b \ge 34$$ and $$c \ge 35$$, the sum of which would exceed $$100$$. So suppose $$a$$ is such an integer between $$1$$ and $$32$$. Then consider
$$(a-a) + (b-a) + (c-a) = b' + c' = 100 - 3a,$$ where we define $$b' = b-a$$, and $$c' = c-a$$. Then $$1 \le b' < c'$$ and we want to find, as a function of $$a$$, the number of such solutions. And we apply the same logic as before; if $$b' \ge \lfloor (100 - 3a)/2 \rfloor + 1$$, then we cannot choose a $$c' > b$$. There is a subtlety here; if $$100 - 3a$$ is even, then the choice $$b' = (100-3a)/2$$ is still not valid, since it would lead to $$c' = b'$$. So when $$a$$ is odd, there are $$\lfloor (100-3a)/2 \rfloor$$ choices for $$b'$$, and when $$a$$ is even, there are $$\lfloor (100-3a)/2 \rfloor - 1$$ choices for $$b'$$. In either case, once $$b'$$ is chosen, $$c'$$ is uniquely determined. As there are exactly $$32/2 = 16$$ cases where $$a$$ is even and $$16$$ where $$a$$ is odd, the total number of such sums is
$$-16 + \sum_{a=1}^{32} \left\lfloor \frac{100 - 3a}{2} \right\rfloor = 784.$$