设 $n,k,m$ 是正整数，满足 $k\geqslant 2$，且 $n\leqslant m<\dfrac{2k-1}{k}n$．设 $A$ 是 $\{1,2,\cdots,m\}$ 的 $n$ 元子集．
证明：区间 $(0,\dfrac{n}{k-1})$ 中每个整数均可表示为 $a-a^\prime$，其中 $a,a^\prime\in A$．
证明：区间 $(0,\dfrac{n}{k-1})$ 中每个整数均可表示为 $a-a^\prime$，其中 $a,a^\prime\in A$．
【难度】
【出处】
2018年全国高中数学联赛（A卷加试试题）
【标注】
【答案】
略
【解析】
用反证法．假设存在整数 $x\in(0,\dfrac{n}{k-1})$ 不可表示为 $a-a^\prime,a,a^\prime\in A$．作带余除法 $m=xq+r$，其中 $0\leqslant r<x$．将 $1,2,\cdots,m$ 按模 $x$ 的同余类划分成 $x$ 个公差为 $x$ 的等差数列，其中 $r$ 个等差数列有 $q+1$ 项，$x-r$ 个等差数列有 $q$ 项．由于 $A$ 中没有两数之差为 $x$，故 $A$ 不能包含以 $x$ 为公差的等差数列的相邻两项．从而 $n=|A|\leqslant r[\dfrac{q+1}{2}]+(x-r)[\dfrac{q}{2}]=\begin{cases}
x\cdot \dfrac{q+1}{2},2\not|q\\
x\cdot\dfrac{q}{2}+r,2|q\\
\end{cases}$ ①
这里 $\left\lceil\alpha \right\rceil $ 表示不小于 $\alpha$ 的最小整数．由条件，我们有
$n>\dfrac{k}{2k-1}m=\dfrac{k}{2k-1}(xq+r)$．②
又 $x\in(0,\dfrac{n}{k-1})$，故 $n>(k-1)x$．③
情形一
$q$ 是奇数，则由 ① 知，$n\leqslant x\cdot \dfrac{q+1}{2}$．④
结合 ②，④ 可知，$x\cdot\dfrac{q+1}{2}\geqslant n>\dfrac{k}{2k-1}(xq+r)\geqslant \dfrac{k}{2k-1}xq$，从而 $q<2k-1$．再由 $q$ 是奇数可知，$q\leqslant 2k-3$，于是 $n\leqslant x\cdot\dfrac{q+1}{2}\leqslant (k-1)x$，与 ③ 矛盾．
情形二
$q$ 是偶数，则由 ① 知，$n\leqslant x\cdot\dfrac{q}{2}+r$．⑤
结合 ②，⑤ 可知，$x\cdot\dfrac{q}{2}+r\geqslant n>\dfrac{k}{2k-1}(xq+r)$，从而 $\dfrac{xq}{2(2k-1)}<\dfrac{k-1}{2k-1}r<\dfrac{(k-1)x}{2k-1}$，故 $q<2(k-1)$．再由 $q$ 是偶数可知，$q\leqslant 2k-4$，于是 $n\leqslant x\cdot\dfrac{q}{2}+r\leqslant (k-2)x+r<(k-1)x$，与 ③ 矛盾．
综上可知，反证法假设不成立，结论获证．
x\cdot \dfrac{q+1}{2},2\not|q\\
x\cdot\dfrac{q}{2}+r,2|q\\
\end{cases}$ ①
这里 $\left\lceil\alpha \right\rceil $ 表示不小于 $\alpha$ 的最小整数．由条件，我们有
$n>\dfrac{k}{2k-1}m=\dfrac{k}{2k-1}(xq+r)$．②
又 $x\in(0,\dfrac{n}{k-1})$，故 $n>(k-1)x$．③
情形一
$q$ 是奇数，则由 ① 知，$n\leqslant x\cdot \dfrac{q+1}{2}$．④
结合 ②，④ 可知，$x\cdot\dfrac{q+1}{2}\geqslant n>\dfrac{k}{2k-1}(xq+r)\geqslant \dfrac{k}{2k-1}xq$，从而 $q<2k-1$．再由 $q$ 是奇数可知，$q\leqslant 2k-3$，于是 $n\leqslant x\cdot\dfrac{q+1}{2}\leqslant (k-1)x$，与 ③ 矛盾．
情形二
$q$ 是偶数，则由 ① 知，$n\leqslant x\cdot\dfrac{q}{2}+r$．⑤
结合 ②，⑤ 可知，$x\cdot\dfrac{q}{2}+r\geqslant n>\dfrac{k}{2k-1}(xq+r)$，从而 $\dfrac{xq}{2(2k-1)}<\dfrac{k-1}{2k-1}r<\dfrac{(k-1)x}{2k-1}$，故 $q<2(k-1)$．再由 $q$ 是偶数可知，$q\leqslant 2k-4$，于是 $n\leqslant x\cdot\dfrac{q}{2}+r\leqslant (k-2)x+r<(k-1)x$，与 ③ 矛盾．
综上可知，反证法假设不成立，结论获证．
答案
解析
备注
