已知 $p\text{,}q$ 为互质的正整数，$n$ 为非负整数。问：有多少个不同的整数可以表示为 $ip+jq$ 的形式，其中 $i\text{,}j$ 为非负整数，且 $i+j\leqslant n$ 。
【难度】
【出处】
2004第3届CGMO试题
【标注】
【答案】
$\frac{p\left( 2n-p+3 \right)}{2}$
【解析】
如果记 $A\left( p\text{,}q\text{,}n \right)\text{=}\left\{i\left. p+jq \right|i\text{,}j\geqslant 0\text{,}i+j\leqslant n \right\}$，则 $A\left(p\text{,}q\text{,}n \right)$ 中所包含的元素个数为 $\left| A\left( p\text{,}q\text{,}n\right) \right|\text{=}\left\{ \begin{matrix}
&\frac{\left( n+1 \right)\left( n+2 \right)}{2}\text{,}n\text{}r \\
& \frac{r\left( 2n-r+3 \right)}{2}\text{,}n\geqslant r \\
\end{matrix} \right.$（1），其中 $r\text{=}\max\left\{ p\text{,}q \right\}$ 下证明（1）式成立：不妨设 $r\text{=}p$ 。由定义易知 $\left| A\left( p\text{,}q\text{,0} \right) \right|\text{=}1$，$\left|A\left( \text{1,1,}n \right) \right|\text{=}n+1$ 。此时（1）式成立。下设 $p\text{}q$ 。根据定义可知 $A\left( p\text{,}q\text{,}n \right)\text{}\!\!\backslash\!\!\text{ }A\left( p\text{,}q\text{,}n-1 \right)\subset \left\{i\left. p+\left( n-i \right)q \right|i\text{=}1\text{,}2\text{,}\cdots n\right\}$ 。注意到 $ip+\left( n-i \right)q\text{=}p\left( i+q \right)+q\left( n-p-i\right)$，且 $\left( i+q \right)+\left( n-p-i \right)\text{=}n-p+q\leqslant n-1$，则有 $ip+\left(n-i \right)q\in A\left( p\text{,}q\text{,}n-1 \right)\Leftrightarrow n-p-i\ge0$ 。 故 $A\left( p,q,n \right)\backslash A\left( p,q,n-1 \right)=\left\{ \begin{matrix}& \left\{ \left. ip+\left( n-i \right)q\right|i=n-p+1,n-p+2,\cdots ,n \right\},n\geqslant p \\
& \left\{ \left. ip+\left( n-i \right)q\right|i=0,1,\cdots ,n \right\},n<p \\
\end{matrix} \right.$ 令 ${{a}_{n}}\text{=}\left|A\left( p\text{,}q\text{,}n \right) \right|$，有 ${{a}_{n}}\text{=}{{a}_{0}}+\left({{a}_{1}}-{{a}_{0}} \right)+\cdots +\left( {{a}_{n}}-{{a}_{n-1}}\right)\text{=}1+2+\cdots +\left( n+1 \right)\text{=}\frac{\left( n+1\right)\left( n+2 \right)}{2}$ 因此，对 $n\geqslant p$，有 ${{a}_{n}}={{a}_{p-1}}+\left({{a}_{p}}-{{a}_{p-1}} \right)+\cdots +\left( {{a}_{n}}-{{a}_{n-1}}\right)={{a}_{p-1}}+\left( n-p+1 \right)p=\frac{p\left( 2n-p+3 \right)}{2}$
&\frac{\left( n+1 \right)\left( n+2 \right)}{2}\text{,}n\text{}r \\
& \frac{r\left( 2n-r+3 \right)}{2}\text{,}n\geqslant r \\
\end{matrix} \right.$（1），其中 $r\text{=}\max\left\{ p\text{,}q \right\}$ 下证明（1）式成立：不妨设 $r\text{=}p$ 。由定义易知 $\left| A\left( p\text{,}q\text{,0} \right) \right|\text{=}1$，$\left|A\left( \text{1,1,}n \right) \right|\text{=}n+1$ 。此时（1）式成立。下设 $p\text{}q$ 。根据定义可知 $A\left( p\text{,}q\text{,}n \right)\text{}\!\!\backslash\!\!\text{ }A\left( p\text{,}q\text{,}n-1 \right)\subset \left\{i\left. p+\left( n-i \right)q \right|i\text{=}1\text{,}2\text{,}\cdots n\right\}$ 。注意到 $ip+\left( n-i \right)q\text{=}p\left( i+q \right)+q\left( n-p-i\right)$，且 $\left( i+q \right)+\left( n-p-i \right)\text{=}n-p+q\leqslant n-1$，则有 $ip+\left(n-i \right)q\in A\left( p\text{,}q\text{,}n-1 \right)\Leftrightarrow n-p-i\ge0$ 。 故 $A\left( p,q,n \right)\backslash A\left( p,q,n-1 \right)=\left\{ \begin{matrix}& \left\{ \left. ip+\left( n-i \right)q\right|i=n-p+1,n-p+2,\cdots ,n \right\},n\geqslant p \\
& \left\{ \left. ip+\left( n-i \right)q\right|i=0,1,\cdots ,n \right\},n<p \\
\end{matrix} \right.$ 令 ${{a}_{n}}\text{=}\left|A\left( p\text{,}q\text{,}n \right) \right|$，有 ${{a}_{n}}\text{=}{{a}_{0}}+\left({{a}_{1}}-{{a}_{0}} \right)+\cdots +\left( {{a}_{n}}-{{a}_{n-1}}\right)\text{=}1+2+\cdots +\left( n+1 \right)\text{=}\frac{\left( n+1\right)\left( n+2 \right)}{2}$ 因此，对 $n\geqslant p$，有 ${{a}_{n}}={{a}_{p-1}}+\left({{a}_{p}}-{{a}_{p-1}} \right)+\cdots +\left( {{a}_{n}}-{{a}_{n-1}}\right)={{a}_{p-1}}+\left( n-p+1 \right)p=\frac{p\left( 2n-p+3 \right)}{2}$
答案
解析
备注
