Answer

问题及解答

在集合 $1,2,\ldots,2n$ 中任取 $n+2$ 个数构成一个子集 $A$, 证明存在 $x,y\in A$, 使得 $x+y\in A$.

Posted by haifeng on 2016-08-23 10:24:20 last update 2016-08-23 11:35:01 | Edit | Answers (1)

在集合 $1,2,\ldots,2n$ 中任取 $n+2$ 个数构成一个子集 $A$, 证明存在 $x,y\in A$, 使得 $x+y\in A$.

 


应用:

总共有 $2n$ 个参赛队 $A_1,A_2,\ldots,A_{2n}$, 组委会设定获奖队伍个数是 $n+2$ 个. 则存在这样两只获奖队伍 $A_i$ 和 $A_j$, 使得 $A_{i+j}$ 也是获奖队伍.

1

Posted by haifeng on 2016-08-23 11:29:48

记 $S_{2n}=\{1,2,\ldots,2n\}$. 任取 $A\subset S_{2n}$, $|A|=n+2$.

使用归纳法。当 $n=2,3$ 时容易验证.


假设 $n\leqslant k$ 时命题成立. 然后考虑 $n=k+1$ 的情况.

此时 $S_{2(k+1)}=S_{2k}\cup\{2k+1,2k+2\}$. 任取 $A\subset S_{2k+2}$. 我们分三种情况,

(1) $A\subset S_{2k}$, 由于 $|A|=k+3 > k+2$, 根据归纳假设, 命题成立.

(2) $B:=A-\{2k+1\}\subset S_{2k}$ 或 $B:=A-\{2k+2\}\subset S_{2k}$. 此时 $|B|=k+2$, 于是又归纳假设, 命题成立.

(3) $B:=A-\{2k+1,2k+2\}\subset S_{2k}$, 此时 $|B|=k+1$. 但是 $A$ 含有 $2k+1, 2k+2$. 

我们对于 (3) 进行讨论:

对于此时的 $B$, 它有 $k+1$ 个元素, 我们考虑 $S_{2(k-1)}$. 如果 $B\subset S_{2(k-1)}$, 则根据归纳假设, 在 $B$ 中存在 $x,y$, 使得 $x+y\in B$. 

如果 $B-\{2k-1\}\subset S_{2(k-1)}$