2015年全国高中数学联赛吉林省预赛

• 数学竞赛

  >

  简单组合

  >

  简单组合

$503$

第一步： 构造一个 $503$ 元“好集”$A$．设 $A=\{1,3,5,\cdots,1005\} $．若 $\lambda_{1}$、$\lambda_{2}$、$\lambda_{3}$ 均不为 $0$，则 $\lambda_{1}x_{1} +\lambda_{2}x_{2}+\lambda_{3}x_{3} \equiv x_{1} +x_{2} +x_{3} \equiv 1(\mod 2)$，即 $\lambda_{1}x_{1} +\lambda_{2}x_{2}+\lambda_{3}x_{3} $ 为奇数，一定不是 $2014$ 的倍数．
若 $\lambda_{1}$、$\lambda_{2}$、$\lambda_{3}$ 中有 $0$，不妨设 $\lambda_{3}=0$，则由 ① 知 $\lambda_{1}$、$\lambda_{2}$ 中至少有一个不为 $0$．由条件 ③ 知 $\lambda_{1}x_{1} +\lambda_{2}x_{2} \ne 0$．又 $\lvert \lambda_{1}x_{1} +\lambda_{2}x_{2} \rvert \leqslant \lvert \lambda_{1}x_{1} \rvert + \lvert \lambda_{2}x_{2} \rvert \leqslant \lvert x_{1} \rvert + \lvert x_{2}\rvert \leqslant 2 \times 1005 < 2014$，因此 $\lambda_{1}x_{1} +\lambda_{2}x_{2}$ 一定不是 $2014$ 的倍数．
显然 $x_{1}x_{2}x_{3}$ 为奇数，一定不是 $2014$ 的倍数．
综上，$A = \{1,3,5,\cdots,1005\}$ 为 $503$ 元“好集”．
第二步：设 $S$ 为一个“好集”，下面证明 $\lvert S \rvert \leqslant 503$．
设 $S$ 的最小元素为 $d$，则 $S$ 中任意两元素的差不为 $d$．否则设 $a_{1},a_{2} \in S,a_{1} - a_{2} =d$，得 $a_{1} - a_{2} =d =0$ 为 $2014$ 的倍数，矛盾．
将 $ \{1,2,3,\cdots,1006\}$ 中大于 $d$ 的元素从大到小每 $2d$ 分为一组，设可分成 $q$ 组，余下的 $r$ 个数 $(0 \leqslant r <2d)$ 为 $d +1,d+2,\cdots,d+r,$ 显然 $2dq +r +d = 1006$，$q$ 组中的每一组至多有 $d$ 个数在 $S$ 中．
由“好集”的定义知，$2014$，$1007 \not\in S$，且 $k$ 和 $2014 - k$ 不同在 $S$ 中．
我们不妨设 $S\subseteq \{1,2,3,\cdots,1006\}$，否则只需将 $S$ 中大于 $1007$ 的元素换成 $2014 - k$，理由是若 $\lambda_{1}x_{1} +\lambda_{2}x_{2}$ 中有某个 $x_{i} >1007$，则将其中的 $\lambda_{i}$ 变为 $-\lambda_{i}$，将 $x_{i}$ 变为 $2014 - x_{i}$ 后得到的数与 $\lambda_{1}x_{1} +\lambda_{2}x_{2}+\lambda_{3}x_{3}$ 对 $\mod 2014$ 不改变．
下面对 $r$ 分情况讨论：
① 若 $d \leqslant r <2d $，则 $d +1,,d+2,\cdots,d+r$ 中至多有 $d-1$ 个数属于 $S$，所以$$\lvert S \rvert \leqslant 1 + (d -1) + dq = dq +d \leqslant dq +\dfrac{r}{2} +\dfrac{d}{2} = 503.$$② 若 $0 \leqslant r \leqslant d - 1$，则$$ \lvert S \rvert \leqslant 1 +r +dq \leqslant dq +\dfrac{r}{2} +\dfrac{d}{2} + \dfrac{1}{2}= 503.5,$$即 $\lvert S \rvert \leqslant 503$．
综上，任意一个“好集”$S$ 必满足 $\lvert S \rvert \leqslant 503$．“好集”$A$ 所含元素个数最大值为 $503$．