设 $E$ 是一个给定的 $n$ 元集合，$A_1 , A_2 , \ldots ,A_k$ 是 $E$ 的 $k$ 个两两不同的非空子集，满足：对任意的 $1\leqslant i<j\leqslant k$，要么 $A_i$ 与 $A_j$ 的交集为空集，要么 $A_i$ 与 $A_j$ 中的一个是另一个的子集．求 $k$ 的最大值．
【难度】
【出处】
2012年中国西部数学邀请赛试题
【标注】
【答案】
略
【解析】
$k$ 的最大值为 $2n-1$．
不妨设 $E=\{1,2,\ldots ,n\}$．例子如下：当 $1\leqslant i\leqslant n$ 时，令 $A_i=\{i\}$；
当 $n+1\leqslant i\leqslant 2n-1$ 时，令 $
A_{i}=\{x \in E | 1 \leqslant x \leqslant i-n+1\}
$
这样取出的 $2n-1$ 个集合 $A_i$ 满足题意．
下面用数学归纳法证明：$k\leqslant 2n-1$．
当 $n=1$ 时可见结论显然成立；
假设 $n\leqslant m-1$ 时结论都成立，当 $n=m$ 时，考察 $A_1 , A_2 , \ldots,A_k$ 中不为全集且元素个数最多的集合，记为 $A_1$，并设 $A_1$ 中有 $t$ 个元素，则 $t\leqslant m-1$．
将 $A_1 , A_2 , \ldots ,A_k$ 分为三类：
第一类：全集；
第二类：不是全集，且与 $A_1$ 的交集不为空集；
第三类：与 $A_1$ 的交集是空集．
由 $A_1$ 的选取可知，第二类中的集合都是 $A_1$ 的子集，且依然满足条件，
由归纳假设知第二类中的集合个数不超过 $2t-1$．
第三类中的集合都是 $E\backslash A_1$ 的子集，由归纳假设知集合个数不超过 $2(m-t)-1$．
因此，$k \leqslant 1+(2 t-1)+[2(m-t)-1]=2 m-1$，即当 $n=m$ 时也成立．
所以，由数学归纳法可知对于任意的 $n$ 元集合 $E$，都有 $k\leqslant 2n-1$．
不妨设 $E=\{1,2,\ldots ,n\}$．例子如下：当 $1\leqslant i\leqslant n$ 时，令 $A_i=\{i\}$；
当 $n+1\leqslant i\leqslant 2n-1$ 时，令 $
A_{i}=\{x \in E | 1 \leqslant x \leqslant i-n+1\}
$
这样取出的 $2n-1$ 个集合 $A_i$ 满足题意．
下面用数学归纳法证明：$k\leqslant 2n-1$．
当 $n=1$ 时可见结论显然成立；
假设 $n\leqslant m-1$ 时结论都成立，当 $n=m$ 时，考察 $A_1 , A_2 , \ldots,A_k$ 中不为全集且元素个数最多的集合，记为 $A_1$，并设 $A_1$ 中有 $t$ 个元素，则 $t\leqslant m-1$．
将 $A_1 , A_2 , \ldots ,A_k$ 分为三类：
第一类：全集；
第二类：不是全集，且与 $A_1$ 的交集不为空集；
第三类：与 $A_1$ 的交集是空集．
由 $A_1$ 的选取可知，第二类中的集合都是 $A_1$ 的子集，且依然满足条件，
由归纳假设知第二类中的集合个数不超过 $2t-1$．
第三类中的集合都是 $E\backslash A_1$ 的子集，由归纳假设知集合个数不超过 $2(m-t)-1$．
因此，$k \leqslant 1+(2 t-1)+[2(m-t)-1]=2 m-1$，即当 $n=m$ 时也成立．
所以，由数学归纳法可知对于任意的 $n$ 元集合 $E$，都有 $k\leqslant 2n-1$．
答案
解析
备注
