设集合 $M\text{=}\left\{ 1\text{,}2\text{,}\cdots \text{,}19 \right\}\text{,}A\text{=}\left\{ {{a}_{1}}\text{,}{{a}_{2}}\text{,}\cdots \text{,}{{a}_{k}} \right\}\subseteq M$，求最小的 $k$，使得对任意的 $b\in M$，存在 ${{a}_{i}}\text{,}{{a}_{j}}\in A$，满足 $b\text{=}{{a}_{i}}$ 或 $b\text{=}{{a}_{i}}\pm {{a}_{j}}$（${{a}_{i}}\text{,}{{a}_{j}}$ 可以相同）
【难度】
【出处】
2006第5届CGMO试题
【标注】
【答案】
最小的 $k\text{=}5$
【解析】
由假设，在 $A$ 中，有 $k\left(k+1 \right)$ 种可能的组合。从而，$k\left( k+1 \right)\geqslant 19$，即 $k\geqslant 4$ 。 当 $k\text{=}4$ 时，有 $k\left(k+1 \right)\text{=}20$ 。不妨假设 ${{a}_{1}}\text{<}{{a}_{2}}\text{<}{{a}_{3}}\text{<}{{a}_{4}}$，则 ${{a}_{4}}\ge10$ 。（1）当 ${{a}_{4}}\text{=}10$ 时，有 ${{a}_{3}}\text{=9}$ 。这时，${{a}_{2}}\text{=}8$ 或 ${{a}_{2}}\text{=}7$ 。 如果 ${{a}_{2}}\text{=}8$，则 $20$，$10-9\text{=}1$，$9-8\text{=}1$，故 $A$ 中的 $19$ 个数不可能全部产生。如果 ${{a}_{2}}\text{=}7$，则 ${{a}_{1}}\text{=}6$ 或 ${{a}_{1}}\text{=}5$ 。由于 $20$，$10-9\text{=}1$，$7-6\text{=}1$ 或 $20$，$9-7\text{=}2$，$7-5\text{=}2$，这不可能。（2）当 ${{a}_{4}}\text{=}11$ 时，有 ${{a}_{3}}\text{=8}$ 。这时，${{a}_{2}}\text{=}7$ 以及 ${{a}_{1}}\text{=}6$，这不可能。（3）当 ${{a}_{4}}\text{=}12$ 时，有 ${{a}_{3}}\text{=}7$ 。这时，${{a}_{2}}\text{=6}$ 或 ${{a}_{1}}\text{=}5$，这不可能。（4）当 ${{a}_{4}}\text{=}13$ 时，有 ${{a}_{3}}\text{=6}$，${{a}_{2}}\text{=}5$，${{a}_{1}}\text{=4}$，这不可能。（5）当 ${{a}_{4}}\text{=}14$ 时，有 ${{a}_{3}}\text{=}5$，${{a}_{2}}\text{=}4$，${{a}_{1}}\text{=}3$，这不可能。（6）当 ${{a}_{4}}\text{=}15$ 时，有 ${{a}_{3}}\text{=4}$，${{a}_{2}}\text{=3}$，${{a}_{1}}\text{=2}$，这不可能。（7）当 ${{a}_{4}}\text{=}16$ 时，有 ${{a}_{3}}\text{=3}$，${{a}_{2}}\text{=2}$，${{a}_{1}}\text{=1}$，这不可能。（8）当 ${{a}_{4}}\ge17$ 时，均不可能。 所以 $k\ge5$ 。如果取 $A\text{=}\left\{ 1\text{,}3\text{,}5\text{,}9\text{,}16 \right\}$，则 $A$ 满足条件。故最小的 $k\text{=}5$ 。
答案
解析
备注
