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{array}{ll}\frac{(n+1)(n+2)}{2},& \text{if }n<r,\\ \frac{r(2n-r+3)}{2},& \text{if }n\ge r,\end{array}$$ where $r=\max \{p,q\}$.

Now we establish the equation $(\ast )$. 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 $(\ast )$. 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{array}{ll}\{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{array}$$ It implies that $$s_n-s_{n-1}=\{\begin{array}{ll}p,& \text{if }n\ge p,\\ n+1,& \text{if }n<p.\end{array}$$ If $n<p$, we conclude that $$s_n=s_0+(s_1-s_0)+\cdots +(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{array}{rl}{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{array}$$