给定整数 $n(n \geqslant 3)$．证明：集合 $X=\left\{1,2, \cdots, n^{2}-n\right\}$ 能写成两个不相交的非空子集的并，使得每一个子集均不包含 $n$ 个元素 $a_{1}, a_{2}, \cdots, a_{n}, a_{1}<a_{2}<\cdots<a_{n}$，满足 $a_{k} \leqslant \dfrac{a_{k-1}+a_{k+1}}{2}, k=2,3, \cdots, n-1$
【难度】
【出处】
2008第23届CMO试题
【标注】
【答案】
略
【解析】
定义
$S_{k}=\left\{k^{2}-k+1, \cdots, k^{2}\right\}$
$T_{k}=\left\{k^{2}+1, \cdots, k^{2}+k\right\}$
$k=1,2, \cdots, n-1$ 令 $S=\bigcup_{k=1}^{n-1} S_{k}, T=\bigcup_{k=1}^{n-1} T_{k}$
下面证明：$S,T$ 即为满足题目要求的两个子集．首先，$S \cap T=\varnothing$，且 $ S \cup T=X$．
其次，如果 $S$ 中存在 $n$ 个元素 $a_{1}, a_{2}, \cdots, a_{n}, a_{1}<a_{2}<\cdots<a_n$，满足 $a_{k} \leqslant \frac{a_{k-1}+a_{k+1}}{2}, k=2,3, \cdots, n-1$，则 $a_{k}-a_{k-1} \leqslant a_{k+1}-a_{k}$ ①
不妨设 $a_{1} \in S_{i}$．
由于 $\left|S_{n-1}\right|<n$，故 $i<n-1$．于是，$a_{1}, a_{2}, \cdots, a_{n}$ 这 $n$ 个数中至少有 $n-\left|S_{i}\right|=n-i$ 个在 $S_{i+1} \bigcup \cdots \bigcup S_{n-1}$ 中．
根据抽屉原理，必有某个 $S_{j}(i<j<n)$ 中含有其中至少两个数，设最小的一个为 $a_k$，则 $a_{k}, a_{k+1} \in S_{j}$．而 $a_{k-1} \in S_{1} \bigcup \cdots \bigcup S_{j-1}$，于是 $a_{k+1}-a_{k} \leqslant\left|S_{j}\right|-1=j-1,a_{k}-a_{k-1} \geqslant\left|T_{j-1}\right|+1=j$ 则 $a_{k+1}-a_{k}<a_{k}-a_{k-1}$ 与式 ① 矛盾．
故 $S$ 中不存在 $n$ 个元素满足题中假设同理，$T$ 中也不存在这样的 $n$ 个元素．
这表明 $S,T$ 即为满足要求的两个子集．
$S_{k}=\left\{k^{2}-k+1, \cdots, k^{2}\right\}$
$T_{k}=\left\{k^{2}+1, \cdots, k^{2}+k\right\}$
$k=1,2, \cdots, n-1$ 令 $S=\bigcup_{k=1}^{n-1} S_{k}, T=\bigcup_{k=1}^{n-1} T_{k}$
下面证明：$S,T$ 即为满足题目要求的两个子集．首先，$S \cap T=\varnothing$，且 $ S \cup T=X$．
其次，如果 $S$ 中存在 $n$ 个元素 $a_{1}, a_{2}, \cdots, a_{n}, a_{1}<a_{2}<\cdots<a_n$，满足 $a_{k} \leqslant \frac{a_{k-1}+a_{k+1}}{2}, k=2,3, \cdots, n-1$，则 $a_{k}-a_{k-1} \leqslant a_{k+1}-a_{k}$ ①
不妨设 $a_{1} \in S_{i}$．
由于 $\left|S_{n-1}\right|<n$，故 $i<n-1$．于是，$a_{1}, a_{2}, \cdots, a_{n}$ 这 $n$ 个数中至少有 $n-\left|S_{i}\right|=n-i$ 个在 $S_{i+1} \bigcup \cdots \bigcup S_{n-1}$ 中．
根据抽屉原理，必有某个 $S_{j}(i<j<n)$ 中含有其中至少两个数，设最小的一个为 $a_k$，则 $a_{k}, a_{k+1} \in S_{j}$．而 $a_{k-1} \in S_{1} \bigcup \cdots \bigcup S_{j-1}$，于是 $a_{k+1}-a_{k} \leqslant\left|S_{j}\right|-1=j-1,a_{k}-a_{k-1} \geqslant\left|T_{j-1}\right|+1=j$ 则 $a_{k+1}-a_{k}<a_{k}-a_{k-1}$ 与式 ① 矛盾．
故 $S$ 中不存在 $n$ 个元素满足题中假设同理，$T$ 中也不存在这样的 $n$ 个元素．
这表明 $S,T$ 即为满足要求的两个子集．
答案
解析
备注
