设 $A$ 是 是集合 $S=\{1,2,3,\cdots,1000000\}$ 的一个恰有 $101$ 个元素的子集．求证：在 $S$ 中存在数 $t_1,t_2,\cdots,t_{100}$，使得集合 $A_j=\{x+{t}_{j}|x\in A\},j=1,2,\cdots,100$ 中，每两个的交集为空集．（巴西）
【难度】
【出处】
2003年第44届IMO试题
【标注】
【答案】
略
【解析】
考虑集合 $D=\{x-y|x,y\in A\}$，则 $D$ 中至多有 $101\times 100+1=10101$ 个不同元素．两个集合 $A_i$ 与 $A_j$ 有公共元的充要条件是 $t_i-t_j\in D$．于是，我们只需在 $S$ 中取出 $100$ 个元素，使得其中任意两个的差不属于 $D$．
下面用递推方式说明可以取出这样的 $100$ 个元素．
任取 $S$ 中的一个元素作为递推的基础，假设已经取出 $k$ 个满足要求的元素，$k\leqslant 99$．我们需要在 $S$ 中取数 $x$，使得已选出的 $k$ 个数都不属于 $x+D$（这里 $x+D=\{x+y|y\in D\}$）．由于 $k$ 个数取定后，至多有 $10101k\leqslant 999999$ 个 $S$ 中的数不能取，故存在上面要求的 $x$．命题获证．
说明：条件 $|S|=10^6$ 可以改小一些．事实上，我们有下面一般的结论：
若 $A$ 是 $S=\{1,2,\cdots,n\}$ 的一个 $k$ 元子集，$m$ 为正整数，满足 $n>(m-1)\left(\dbinom{k}{2}+1\right)$，则存在 $S$ 中的元素 $t_1,\cdots,t_m$，使得 $A_j=\{x+t_j|x\in A\},j=1,\cdots,m$ 中任意两个的交集为空集．
下面用递推方式说明可以取出这样的 $100$ 个元素．
任取 $S$ 中的一个元素作为递推的基础，假设已经取出 $k$ 个满足要求的元素，$k\leqslant 99$．我们需要在 $S$ 中取数 $x$，使得已选出的 $k$ 个数都不属于 $x+D$（这里 $x+D=\{x+y|y\in D\}$）．由于 $k$ 个数取定后，至多有 $10101k\leqslant 999999$ 个 $S$ 中的数不能取，故存在上面要求的 $x$．命题获证．
说明：条件 $|S|=10^6$ 可以改小一些．事实上，我们有下面一般的结论：
若 $A$ 是 $S=\{1,2,\cdots,n\}$ 的一个 $k$ 元子集，$m$ 为正整数，满足 $n>(m-1)\left(\dbinom{k}{2}+1\right)$，则存在 $S$ 中的元素 $t_1,\cdots,t_m$，使得 $A_j=\{x+t_j|x\in A\},j=1,\cdots,m$ 中任意两个的交集为空集．
答案
解析
备注
