China Girls' Mathematical Olympiad

Define a set
$$S(p, q, n) = \{ip + jq \mid i \text{ and } j \text{ are nonnegative integers with } i + j \le n\}$$
Let $s_n = |S(p, q, n)|$, where $|X|$ denotes the number of elements in set $X$. The answer of the problem is
$$s_n = \begin{cases} \dfrac{(n+1)(n+2)}{2}, & \text{if } n < r, \\ \dfrac{r(2n-r+3)}{2}, & \text{if } n \ge r, \end{cases}$$
where $r = \max\{p, q\}$.

Now we establish the equation $(*)$. Without loss of generality, we assume that $r = p > q$. It is easy to see that $s_0 = |S(p, q, 0)| = |\{0\}| = 1$ satisfying equation $(*)$. Note that
$$S(p, q, n) \setminus S(p, q, n-1) \subseteq \{ip + (n-i)q \mid i = 0, 1, \dots, n\}.$$
Note also that
$$ip + (n - i)q = (i + q)p + (n - p - i)q,$$
with
$$(i+q) + (n-p-i) = n+q-p \le n-1.$$
Hence number $ip + (n-i)q$ belongs to both sets $S(p, q, n)$ and $S(p, q, n-1)$ if and only if $n-p-i \ge 0$, or $i \le n-p$. Therefore,
$$S(p, q, n) \setminus S(p, q, n-1) = \begin{cases} \{ip + (n-i)q \mid i = n-p+1, n-p+2, \dots, n\}, & \text{if } n \ge p, \\ \{ip + (n-i)q \mid i = 0, 1, \dots, n\}, & \text{if } n < p. \end{cases}$$
It implies that
$$s_n - s_{n-1} = \begin{cases} p, & \text{if } n \ge p, \\ n+1, & \text{if } n < p. \end{cases}$$
If $n < p$, we conclude that
$$s_n = s_0 + (s_1 - s_0) + \dots + (s_n - s_{n-1})$$
$$=1+2+\cdots+(n+1)=\frac{(n+1)(n+2)}{2}.$$
In particular, $s_{p-1} = \frac{p(p+1)}{2}$. If $n \ge p$, we conclude that
$$\begin{aligned} s_n &= s_{p-1} + (s_p - s_{p-1}) + \cdots + (s_n - s_{n-1}) \\ &= \frac{p(p+1)}{2} + (n-p+1)p = \frac{p(2n-p+3)}{2}. \end{aligned}$$