试证明：（1）若 $2n- 1$ 为素数，则对于任意 $n$ 个互不相同的正整数 $a_{1}, a_{2}, \cdots, a_{n}$，都存在 $i, j \in\{1,2, \cdots, n\}$，使得 $\dfrac{a_{i}+a_{j}}{\left(a_{i}, a_{j}\right)} \geqslant 2 n-1$
（2）若 $2n-1$ 为合数，则存在 $n$ 个互不相同的正整数 $a_{1}, a_{2}, \cdots, a_{n}$，使得 $\dfrac{a_{i}+a_{j}}{\left(a_{i}, a_{j}\right)} \geqslant 2 n-1$ $\dfrac{a_{i}+a_{i}}{\left(a_{i}, a_{j}\right)}<2 n-1$
其中，$(x,y)$ 表示正整数 $x,y$ 的最大公约数．
（2）若 $2n-1$ 为合数，则存在 $n$ 个互不相同的正整数 $a_{1}, a_{2}, \cdots, a_{n}$，使得 $\dfrac{a_{i}+a_{j}}{\left(a_{i}, a_{j}\right)} \geqslant 2 n-1$ $\dfrac{a_{i}+a_{i}}{\left(a_{i}, a_{j}\right)}<2 n-1$
其中，$(x,y)$ 表示正整数 $x,y$ 的最大公约数．
【难度】
【出处】
2007第22届CMO试题
【标注】
【答案】
略
【解析】
（1）记 $2n - 1$ 为素数 $p$，不妨设 $\left(a_{1}, a_{2}, \cdots, a_{n}\right)=1$．若存在 $i(1 \leqslant i \leqslant n)$，使得 $p | a_{i}$．必然存在 $j \neq i$ 使得 $p \not| a_{j}$．由于 $p \not|\left(a_{i}, a_{j}\right)$，则有 $\dfrac{a_{i}+a_{i}}{\left(a_{i}, a_{j}\right)} \geqslant \dfrac{a_{i}}{\left(a_{i}, a_{j}\right)} \geqslant p=2 n-1$
以下只须要考虑 $\left(a_{i}, p\right)=1, i=1,2, \cdots, n$，则对任意 $i \neq j$ 都是 $p \not|\left(a_{i}, a_{j}\right)$．将 $1,2, \cdots, p-1$ 分成 $n-1$ 类：$\{1, p-1\},\{2,p-2\},\cdots,\{n-1,n\}$．由抽屉原理可知存在 $i\ne j$，使得 $a_i\equiv a_{j}(\bmod p)$ 或者 $a_{i}+a_{j} \equiv 0(\bmod p)$．
当 $a_{i}\equiv a_{j}(\bmod p)$ 时 $\dfrac{a_{i}+a_{j}}{\left(a_{i}, a_{j}\right)}>\dfrac{a_{i}-a_{j}}{\left(a_{i}, a_{j}\right)} \geqslant p=2 n-1$
当 $a_{i}+a_{j} \equiv 0(\bmod p)$ 时 $\dfrac{a_{i}+a_{j}}{\left(a_{i}, a_{j}\right)} \geqslant p=2 n-1$
故（1）得证．
（2）以下我们来构造命题存在性的例子．由于 $2n-1$ 为合数，则存在两个大于 $1$ 的正整数 $p, q$ 使得 $2n-1 = pq$．可以构造如下 $n$ 个数 $\begin{aligned} a_{1}=& 1, a_{2}=2, \cdots, a_{p}=p, a_{p+1}=p+1 ,a_{p+2}=p+3, \cdots, a_{n}=p q-p \end{aligned}$ 其中前面为 $p$ 个连续的整数，从 $p + 1$ 至 $pq-p$ 为 $n-p$ 个连续的偶数．
当 $1 \leqslant i \leqslant j \leqslant p$ 时，显然有 $\dfrac{a_{i}+a_{j}}{\left(a_{i}, a_{j}\right)} \leqslant a_{i}+a_{j} \leqslant 2 p<2 n-1$
当 $p+1 \leqslant i \leqslant j \leqslant n$ 时，因为 $2 |\left(a_{i}, a_{j}\right)$，所以有 $\dfrac{a_{i}+a_{j}}{\left(a_{i}, a_{j}\right)} \leqslant \dfrac{a_{i}+a_{j}}{2} \leqslant p q-p<2 n-1$
当 $1 \leqslant i \leqslant p, p+1 \leqslant j \leqslant n$ 时，分两种情况
（i）当 $i\ne p$ 或 $j\ne n$ 时，显然有 $\dfrac{a_{i}+a_{i}}{\left(a_{i}, a_{j}\right)} \leqslant p q-1<2 n-1$
（2）当 $i=p$ 且 $j=n$ 时，由于 $(p, p q-p)=p$，则有 $\dfrac{a_{p}+a_{n}}{\left(a_{p}, a_{n}\right)} \leqslant \frac{p q}{p} \leqslant q<2 n-1$
经过如上验证，可以看出所构造的 $n$ 个数满足条件．
以下只须要考虑 $\left(a_{i}, p\right)=1, i=1,2, \cdots, n$，则对任意 $i \neq j$ 都是 $p \not|\left(a_{i}, a_{j}\right)$．将 $1,2, \cdots, p-1$ 分成 $n-1$ 类：$\{1, p-1\},\{2,p-2\},\cdots,\{n-1,n\}$．由抽屉原理可知存在 $i\ne j$，使得 $a_i\equiv a_{j}(\bmod p)$ 或者 $a_{i}+a_{j} \equiv 0(\bmod p)$．
当 $a_{i}\equiv a_{j}(\bmod p)$ 时 $\dfrac{a_{i}+a_{j}}{\left(a_{i}, a_{j}\right)}>\dfrac{a_{i}-a_{j}}{\left(a_{i}, a_{j}\right)} \geqslant p=2 n-1$
当 $a_{i}+a_{j} \equiv 0(\bmod p)$ 时 $\dfrac{a_{i}+a_{j}}{\left(a_{i}, a_{j}\right)} \geqslant p=2 n-1$
故（1）得证．
（2）以下我们来构造命题存在性的例子．由于 $2n-1$ 为合数，则存在两个大于 $1$ 的正整数 $p, q$ 使得 $2n-1 = pq$．可以构造如下 $n$ 个数 $\begin{aligned} a_{1}=& 1, a_{2}=2, \cdots, a_{p}=p, a_{p+1}=p+1 ,a_{p+2}=p+3, \cdots, a_{n}=p q-p \end{aligned}$ 其中前面为 $p$ 个连续的整数，从 $p + 1$ 至 $pq-p$ 为 $n-p$ 个连续的偶数．
当 $1 \leqslant i \leqslant j \leqslant p$ 时，显然有 $\dfrac{a_{i}+a_{j}}{\left(a_{i}, a_{j}\right)} \leqslant a_{i}+a_{j} \leqslant 2 p<2 n-1$
当 $p+1 \leqslant i \leqslant j \leqslant n$ 时，因为 $2 |\left(a_{i}, a_{j}\right)$，所以有 $\dfrac{a_{i}+a_{j}}{\left(a_{i}, a_{j}\right)} \leqslant \dfrac{a_{i}+a_{j}}{2} \leqslant p q-p<2 n-1$
当 $1 \leqslant i \leqslant p, p+1 \leqslant j \leqslant n$ 时，分两种情况
（i）当 $i\ne p$ 或 $j\ne n$ 时，显然有 $\dfrac{a_{i}+a_{i}}{\left(a_{i}, a_{j}\right)} \leqslant p q-1<2 n-1$
（2）当 $i=p$ 且 $j=n$ 时，由于 $(p, p q-p)=p$，则有 $\dfrac{a_{p}+a_{n}}{\left(a_{p}, a_{n}\right)} \leqslant \frac{p q}{p} \leqslant q<2 n-1$
经过如上验证，可以看出所构造的 $n$ 个数满足条件．
答案
解析
备注
