设 $S=\{1,2,3,\cdots,100\}$．求最大的整数 $k$，使得 $S$ 有 $k$ 个互不相同的非空子集，具有性质：对这 $k$ 个子集中任意两个不同子集，若它们的交集非空，则它们交集中的最小元素与这两个子集中的最大元素均不相同．
【难度】
【出处】
2014年全国高中数学联赛（二试 ）
【标注】
【答案】
$2^{99}-1$
【解析】
对有限非空实数集 $A$，用 $\min A$ 与 $\max A$ 分别表示 $A$ 的最小元素与最大元素．
考虑 $S$ 的所有包含 $1$ 且至少有两个元素的子集，一共 $2^{99}-1$ 个．
因为$$\min (A_i \cap A_j)=1<\max A_i,$$所以它们显然满足要求．故 $k$ 可以取到 $2^{99}-1$．
下面证明 $k\geqslant 2^{99} $ 时不存在满足要求的 $k$ 个子集．
我们用数学归纳法证明：对整数 $n \geqslant 3$，在集合 $\{1,2,\cdots,n\}$ 的任意 $m(\geqslant 2^{n-1})$ 个不同非空子集 $A_1$，$A_2$，$\cdots $，$A_m$ 中，存在两个子集 $A_i$，$A_j$，$i\neq j$，满足$$A_i\cap A_j \neq \varnothing ,\land \min (A_i\cap A_j)=\max A_i.\quad\cdots \cdots \text{ ① }$$显然只需对 $m=2^{n-1}$ 的情况证明上述结论．
归纳基础 当 $n=3$ 时，将 $\{1,2,3\}$ 的全部 $7$ 个非空子集分成 $3$ 组：
第一组：$\{3\}$，$\{1,3\}$，$\{2,3\}$；
第二组：$\{2\}$，$\{1,2\}$；
第三组：$\{1\}$，$\{1,2,3\}$．
由抽屉原理，任意 $4$ 个非空子集必有两个在同一组中，取同一组中的的两个子集分别记为 $A_i$，$A_j$，排在前面的记为 $A_i$，则满足 ①．
递推证明 假设结论在 $n (\geqslant 3)$ 时成立，考虑 $n+1$ 的情形．
若 $A_1$，$A_2$，$\cdots$，$A_{2^n}$ 中至少有 $2^{n-1}$ 个子集不含 $n+1$，对其中的 $2^{n-1}$ 个子集用归纳假设，可知存在两个子集满足 ①．
若至多有 $2^{n-1}-1$ 个子集不含 $n+1$，则至少有 $2^{n-1}+1$ 个子集含 $n+1$．将其中 $2^{n-1}+1$ 子集都去掉 $n+1$，得到 $\{1,2,3,\cdots,n\}$ 的 $2^{n-1}+1$ 个子集．
由于 $\{1,2,3,\cdots,n\}$ 的全体子集可分成 $2^{n-1}$ 组，每组两个子集互补，故由抽屉原理，在上述 $2^{n-1}+1$ 个子集中一定有两个属于同一组，即互为补集．因此，相应地有两个子集 $A_i$，$A_j$，满足 $A_i \cap A_j=\{n+1\}$，这两个子集显然满足 ①．故 $n+1$ 时结论成立．
综上所述，所求 $k_{\max}=2^{99}-1$．
考虑 $S$ 的所有包含 $1$ 且至少有两个元素的子集，一共 $2^{99}-1$ 个．
因为$$\min (A_i \cap A_j)=1<\max A_i,$$所以它们显然满足要求．故 $k$ 可以取到 $2^{99}-1$．
下面证明 $k\geqslant 2^{99} $ 时不存在满足要求的 $k$ 个子集．
我们用数学归纳法证明：对整数 $n \geqslant 3$，在集合 $\{1,2,\cdots,n\}$ 的任意 $m(\geqslant 2^{n-1})$ 个不同非空子集 $A_1$，$A_2$，$\cdots $，$A_m$ 中，存在两个子集 $A_i$，$A_j$，$i\neq j$，满足$$A_i\cap A_j \neq \varnothing ,\land \min (A_i\cap A_j)=\max A_i.\quad\cdots \cdots \text{ ① }$$显然只需对 $m=2^{n-1}$ 的情况证明上述结论．
第一组：$\{3\}$，$\{1,3\}$，$\{2,3\}$；
第二组：$\{2\}$，$\{1,2\}$；
第三组：$\{1\}$，$\{1,2,3\}$．
由抽屉原理，任意 $4$ 个非空子集必有两个在同一组中，取同一组中的的两个子集分别记为 $A_i$，$A_j$，排在前面的记为 $A_i$，则满足 ①．
若 $A_1$，$A_2$，$\cdots$，$A_{2^n}$ 中至少有 $2^{n-1}$ 个子集不含 $n+1$，对其中的 $2^{n-1}$ 个子集用归纳假设，可知存在两个子集满足 ①．
若至多有 $2^{n-1}-1$ 个子集不含 $n+1$，则至少有 $2^{n-1}+1$ 个子集含 $n+1$．将其中 $2^{n-1}+1$ 子集都去掉 $n+1$，得到 $\{1,2,3,\cdots,n\}$ 的 $2^{n-1}+1$ 个子集．
由于 $\{1,2,3,\cdots,n\}$ 的全体子集可分成 $2^{n-1}$ 组，每组两个子集互补，故由抽屉原理，在上述 $2^{n-1}+1$ 个子集中一定有两个属于同一组，即互为补集．因此，相应地有两个子集 $A_i$，$A_j$，满足 $A_i \cap A_j=\{n+1\}$，这两个子集显然满足 ①．故 $n+1$ 时结论成立．
综上所述，所求 $k_{\max}=2^{99}-1$．
答案
解析
备注
