3
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

So you can either try to modify your approach to take these into account, or you can try a totally different approach.

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .