给定正整数 $m、n$．求具有下述性质的最小整数 $N(N\geqslant m)$：若一个 $N$ 元整数集含有模 $m$ 的完全剩余系，则其有一个非空子集，其元素和被 $n$ 整除．
【难度】
【出处】
2013第28届CMO试题
【标注】
【答案】
略
【解析】
$N=\max \left\{m, m+n-\dfrac{1}{2} m[(m, n)+1]\right\}$．
首先证明：
$N \geqslant \max \left\{m, m+n-\dfrac{1}{2} m[(m, n)+1]\right\}$ ①
设 $d=(m, n), m=d m_{1}, n=d n_{1}$．
若 $n>\dfrac{1}{2} m(d+1)$，考虑一个模 $m$ 的完全剩余系 $x_{1}, x_{2}, \cdots, x_{m}$，其模 $n$ 的余数恰为 $m_1$ 个 $1,2, \cdots, d$．这样的一组完全剩余系是存在的，如下面 $m$ 个数 $i+d n_{1} j\left(i=1,2, \cdots, d, j=1,2, \cdots, m_{1}\right)$．
再添上 $k=n-\dfrac{1}{2} m(d+1)-1$ 个模 $n$ 余 $1$ 的数 $y_{1}, y_{2}, \cdots, y_{k}$，则集合 $A=\left\{x_{1}, x_{2}, \cdots, x_{m}, y_{1}, y_{2}, \cdots, y_{k} \right\}$ 含有模 $m$ 的完全剩余系，但不存在非空子集的元素和被 $n$ 整除．
事实上，集合 $A$ 中没有一个元素被 $n$ 整除，故 $A$ 的每个元素除以 $n$ 的最小正余数之和为 $m_{1}(1+2+\cdots+d)+k=n-1$．
从而，集合 $A$ 中不存在非空子集其元素和被 $n$ 整除．
因此，$N \geqslant m+n-\dfrac{1}{2} m(d+1)$，即式 ① 成立．
其次证明：$N=\max \left\{m, m+n-\frac{1}{2} m[(m, n)+1]\right\}$ 满足要求．
反复利用结论：$k$ 个整数中必存在若干个之和被 $k$ 整除．
设这 $k$ 个整数为 $a_{1}, a_{2}, \cdots, a_{k}$，令 $S_{i}=a_{1}+a_{2}+\cdots+a_{i}$．
若有一个 $S_i$ 被 $k$ 整除，则结论成立．否则，存在 $1\leqslant i<j\leqslant k$，使得 $S_{i} \equiv S_{j}(\bmod k)\Rightarrow k |\left(S_{j}-S_{i}\right)=a_{i+1}+a_{i+2}+\cdots+a_{j}$
由上，知在 $k$ 个均被正整数 $a$ 整除的整数中，必可取出若干个数之和被 $ka$ 整除．
对原问题分两种情形讨论．
（1）$n \leqslant \dfrac{1}{2} m(d+1)$
此时，$N=m$．如果一个有限整数集的所有元素和可被 $k$ 整除，则称“$k$ -集”．
设 $x_{1}, x_{2}, \cdots, x_{m}$ 是模 $m$ 的完全剩余系，将这些数分成 $m_1$ 组，每组构成模 $d$ 的完全剩余系．设 $y_{1}, y_{2}, \cdots, y_{d}$ 是一个模 $d$ 的完全剩余系．则 $y_{i} \equiv i(\bmod d)$．
若 $d$ 为奇数，则可将一个模 $d$ 的完全剩余系分成 $\dfrac{d+1}{2}$ 个 $d$ -集，如 $\left\{y_{1}, y_{d-1}\right\}, \cdots,\left\{y_{\frac{d-1}{2}}, y_{\frac{d+1}{2}}\right\},\left\{y_{d}\right\}$
共有 $\dfrac{1}{2}m_1(d+1)$ 个 $d$ -集．
由于 $n_{1} \leqslant \dfrac{1}{2} m_{1}(d+1)$，故从这些 $d$ 一集
中可选出一些集合，其总和被 $n_1d=n$ 整除．
若 $d$ 为偶数，类似地，可将 $y_{1}, y_{2}, \cdots, y_{d}$ 分成 $\dfrac{d}{2}$ 个 $d$ -集，此时多余 $y_{\frac{d}{2}}$．
注意到，两个模 $d$ 余 $\dfrac{d}{2}$ 的数又可组成一个 $d$ -集．则从一个模 $m$ 的完全剩余系中可取出 $\dfrac{1}{2} m_{1} d+\left[\dfrac{m_{1}}{2}\right]$ 个 $d$ -集（$[x]$ 表示不超过实数 $x$ 的最大整数）．
又 $n_{1} \leqslant \dfrac{1}{2} m_{1}(d+1)=\dfrac{1}{2} m_{1} d+\dfrac{m_{1}}{2}$，故 $n_{1} \leqslant \dfrac{1}{2} m_{1} d+\left[\dfrac{m_{1}}{2}\right]$．
于是，可从这些 $d$ -集中选出一些，其总和被 $n_1d=n$ 整除．
（2）$n>\dfrac{1}{2} m(d+1)$
此时，$N=m+n-\dfrac{1}{2} m(d+1)$
设 $A$ 是一个 $N$ 元集包含模 $m$ 的完全剩余系 $x_{1}, x_{2}, \cdots, x_{m}$，另外还有 $n-\dfrac{1}{2} m(d+1)$ 个数．
若 $d$ 是奇数，则由（1）的论证，可将一个模 $m$ 的完全剩余系分成 $\dfrac{1}{2} m_{1}(d+1)$ 个 $d$ -集．另外，$n-\dfrac{1}{2} m(d+1)$ 个数又可分成 $n_{1}-\dfrac{1}{2} m_{1}(d+1)$ 组数，每组 $d$ 个数，每一组中又可取出一个 $d$ -集，即从另外的数中可找到 $n_{1}-\dfrac{1}{2} m_{1}(d+1)$ 个 $d$ -集．这样共得到 $n_1$ 个 $d$ -集．
若 $d$ 是偶数，则由（1）的论证，可将一个模 $m$ 的完全剩余系分成 $\dfrac{1}{2} m_{1} d+\left[\dfrac{m_{1}}{2}\right]$ 个 $d$ -集．
当 $m_1$ 为偶数时，可得至少 $n_{1}-\dfrac{1}{2} m_{1}(d+1)$ 个 $d$ -集．
当 $m_1$ 为奇数时，剩余的 $\{x_i\}$ 也是一个 $\dfrac{d}{2}$ -集，共有 $2 n_{1}-m_{1}(d+1)+1$ 个 $d$ -集，从中可取出至少 $n_{1}-\dfrac{1}{2} m_{1}(d+1)+\dfrac{1}{2}$ 个 $d$ -集．这样共得到 $n_1$ 个 $d$ -集．
最后，从这 $n_1$ 个 $d$ -集中可选出一部分数，其总和被 $n_1d=n$ 整除．
首先证明：
$N \geqslant \max \left\{m, m+n-\dfrac{1}{2} m[(m, n)+1]\right\}$ ①
设 $d=(m, n), m=d m_{1}, n=d n_{1}$．
若 $n>\dfrac{1}{2} m(d+1)$，考虑一个模 $m$ 的完全剩余系 $x_{1}, x_{2}, \cdots, x_{m}$，其模 $n$ 的余数恰为 $m_1$ 个 $1,2, \cdots, d$．这样的一组完全剩余系是存在的，如下面 $m$ 个数 $i+d n_{1} j\left(i=1,2, \cdots, d, j=1,2, \cdots, m_{1}\right)$．
再添上 $k=n-\dfrac{1}{2} m(d+1)-1$ 个模 $n$ 余 $1$ 的数 $y_{1}, y_{2}, \cdots, y_{k}$，则集合 $A=\left\{x_{1}, x_{2}, \cdots, x_{m}, y_{1}, y_{2}, \cdots, y_{k} \right\}$ 含有模 $m$ 的完全剩余系，但不存在非空子集的元素和被 $n$ 整除．
事实上，集合 $A$ 中没有一个元素被 $n$ 整除，故 $A$ 的每个元素除以 $n$ 的最小正余数之和为 $m_{1}(1+2+\cdots+d)+k=n-1$．
从而，集合 $A$ 中不存在非空子集其元素和被 $n$ 整除．
因此，$N \geqslant m+n-\dfrac{1}{2} m(d+1)$，即式 ① 成立．
其次证明：$N=\max \left\{m, m+n-\frac{1}{2} m[(m, n)+1]\right\}$ 满足要求．
反复利用结论：$k$ 个整数中必存在若干个之和被 $k$ 整除．
设这 $k$ 个整数为 $a_{1}, a_{2}, \cdots, a_{k}$，令 $S_{i}=a_{1}+a_{2}+\cdots+a_{i}$．
若有一个 $S_i$ 被 $k$ 整除，则结论成立．否则，存在 $1\leqslant i<j\leqslant k$，使得 $S_{i} \equiv S_{j}(\bmod k)\Rightarrow k |\left(S_{j}-S_{i}\right)=a_{i+1}+a_{i+2}+\cdots+a_{j}$
由上，知在 $k$ 个均被正整数 $a$ 整除的整数中，必可取出若干个数之和被 $ka$ 整除．
对原问题分两种情形讨论．
（1）$n \leqslant \dfrac{1}{2} m(d+1)$
此时，$N=m$．如果一个有限整数集的所有元素和可被 $k$ 整除，则称“$k$ -集”．
设 $x_{1}, x_{2}, \cdots, x_{m}$ 是模 $m$ 的完全剩余系，将这些数分成 $m_1$ 组，每组构成模 $d$ 的完全剩余系．设 $y_{1}, y_{2}, \cdots, y_{d}$ 是一个模 $d$ 的完全剩余系．则 $y_{i} \equiv i(\bmod d)$．
若 $d$ 为奇数，则可将一个模 $d$ 的完全剩余系分成 $\dfrac{d+1}{2}$ 个 $d$ -集，如 $\left\{y_{1}, y_{d-1}\right\}, \cdots,\left\{y_{\frac{d-1}{2}}, y_{\frac{d+1}{2}}\right\},\left\{y_{d}\right\}$
共有 $\dfrac{1}{2}m_1(d+1)$ 个 $d$ -集．
由于 $n_{1} \leqslant \dfrac{1}{2} m_{1}(d+1)$，故从这些 $d$ 一集
中可选出一些集合，其总和被 $n_1d=n$ 整除．
若 $d$ 为偶数，类似地，可将 $y_{1}, y_{2}, \cdots, y_{d}$ 分成 $\dfrac{d}{2}$ 个 $d$ -集，此时多余 $y_{\frac{d}{2}}$．
注意到，两个模 $d$ 余 $\dfrac{d}{2}$ 的数又可组成一个 $d$ -集．则从一个模 $m$ 的完全剩余系中可取出 $\dfrac{1}{2} m_{1} d+\left[\dfrac{m_{1}}{2}\right]$ 个 $d$ -集（$[x]$ 表示不超过实数 $x$ 的最大整数）．
又 $n_{1} \leqslant \dfrac{1}{2} m_{1}(d+1)=\dfrac{1}{2} m_{1} d+\dfrac{m_{1}}{2}$，故 $n_{1} \leqslant \dfrac{1}{2} m_{1} d+\left[\dfrac{m_{1}}{2}\right]$．
于是，可从这些 $d$ -集中选出一些，其总和被 $n_1d=n$ 整除．
（2）$n>\dfrac{1}{2} m(d+1)$
此时，$N=m+n-\dfrac{1}{2} m(d+1)$
设 $A$ 是一个 $N$ 元集包含模 $m$ 的完全剩余系 $x_{1}, x_{2}, \cdots, x_{m}$，另外还有 $n-\dfrac{1}{2} m(d+1)$ 个数．
若 $d$ 是奇数，则由（1）的论证，可将一个模 $m$ 的完全剩余系分成 $\dfrac{1}{2} m_{1}(d+1)$ 个 $d$ -集．另外，$n-\dfrac{1}{2} m(d+1)$ 个数又可分成 $n_{1}-\dfrac{1}{2} m_{1}(d+1)$ 组数，每组 $d$ 个数，每一组中又可取出一个 $d$ -集，即从另外的数中可找到 $n_{1}-\dfrac{1}{2} m_{1}(d+1)$ 个 $d$ -集．这样共得到 $n_1$ 个 $d$ -集．
若 $d$ 是偶数，则由（1）的论证，可将一个模 $m$ 的完全剩余系分成 $\dfrac{1}{2} m_{1} d+\left[\dfrac{m_{1}}{2}\right]$ 个 $d$ -集．
当 $m_1$ 为偶数时，可得至少 $n_{1}-\dfrac{1}{2} m_{1}(d+1)$ 个 $d$ -集．
当 $m_1$ 为奇数时，剩余的 $\{x_i\}$ 也是一个 $\dfrac{d}{2}$ -集，共有 $2 n_{1}-m_{1}(d+1)+1$ 个 $d$ -集，从中可取出至少 $n_{1}-\dfrac{1}{2} m_{1}(d+1)+\dfrac{1}{2}$ 个 $d$ -集．这样共得到 $n_1$ 个 $d$ -集．
最后，从这 $n_1$ 个 $d$ -集中可选出一部分数，其总和被 $n_1d=n$ 整除．
答案
解析
备注
