设 $X$ 是一个 $56$ 元集合．求最小的正整数 $n$，使得对 $X$ 的任意 $15$ 个子集，只要它们中任何 $7$ 个的并的元素个数都不少于 $n$，则这 $ 15 $ 个子集中一定存在 $ 3$ 个，它们的交非空．
【难度】
【出处】
2006第21届CMO试题
【标注】
【答案】
略
【解析】
$n$ 的最小值为 $41$．
首先证明 $n = 41$ 合乎条件．用反证法．假定存在 $X$ 的 $15$ 个子集，它们中任何 $7$ 个的并不少于 $41$ 个元素，而任何 $3$ 个的交都为空集．因每个元素至多属于 $2$ 个子集，不妨设每个元素恰好属于 $2$ 个子集（否则在一些子集中添加一些元素，上述条件仍然成立），由抽屉原理，必有一个子集，设为 $A$，至少含有 $\left[\dfrac{2 \times 56}{15}\right]+1=8$ 个元素，又设其他 $14 $ 个子集为 $A_{1}, A_{2}, \cdots, A_{14}$．考察不含 $A$ 的任何 $7$ 个子集，都对应 $X$ 中的 $41$ 个元素，所有不含 $A$ 的 $7$ 元子集组一共至少对应41 $\mathrm{C}_{14}^{7}$ 个元素．另一方面，对于元素 $a$，若 $a \notin A$，则 $A_{1}, A_{2}, \cdots, A_{14}$ 中有 $2 $ 个含有 $a$，于是 $a $ 被计算了 $C_{14}^{7}-C_{12}^{7}$ 次；若 $a\in A$，则 $A_{1}, A_{2}, \cdots, A_{14}$ 中有一个含有 $a$，于是 $a$ 被计算了 $C_{14}^{7}-C_{13}^{7}$ 次于是
$\begin{aligned} 41 \mathrm{C}_{14}^{7} \leqslant &(56-|A|)\left(\mathrm{C}_{14}^{7}-\mathrm{C}_{12}^{7}\right)+|A|\left(\mathrm{C}_{14}^{7}-\mathrm{C}_{13}^{7}\right)=56\left(\mathrm{C}_{14}^{7}-\mathrm{C}_{12}^{7}\right)-|A|\left(\mathrm{C}_{13}^{7}-\mathrm{C}_{12}^{7}\right) \leqslant 56\left(\mathrm{C}_{14}^{7}-\mathrm{C}_{12}^{7}\right)-8\left(\mathrm{C}_{13}^{7}-\mathrm{C}_{12}^{7}\right) \end{aligned}$
由此可得 $196\leqslant 195$，矛盾．
其次证明 $n\geqslant 41$．
用反证法．假定 $n\leqslant 40$，设 $X=\{ 1,2, \cdots, 56 \}$，令 $A_{i}=\{i, i+7, i+14, i+21, i+28, i+35, i+42, i+49\}i=1,2, \cdots, 7$
$B_{j}=\{j, j+8, j+16, j+24, j+32, j+40, j+48\}j=1,2, \cdots, 8$
显然
$\left|A_{i}\right|=8, i=1,2, \cdots, 7$
$\left|A_{i} \cap A_{j}\right|=0,1 \leqslant i<j \leqslant 7$
$\left|B_{j}\right|=7, j=1,2, \cdots, 8$
$\left|B_{i} \cap B_{j}\right|=0,1 \leqslant i<j \leqslant 8$
$\left|A_{i} \cap B_{j}\right|=1,1 \leqslant i \leqslant 7,1 \leqslant j \leqslant 8$
于是，对其中任何 $3$ 个子集，必有 $2$ 个同时为 $A_i$，或者同时为 $B_j$ 其交为空集．对其中任何 $7$ 个子集 $A_{i_{1}}, A_{i_{2}}, \cdots, A_{i_s}, B_{j_{1}}, B_{j_{2}}, \cdots, B_{j_{t}}(s+t=7)$ 有
$| A_{i_{1}} \cup A_{i_{2}} \cup \cdots \cup A_{i} \cup B_{j_{1}} \cup B_{j_{2}} \cup \cdots \cup B_{j_{i}} 1=\left|A_{i_{1}}\right|+\left|A_{i_{i}}\right|+\cdots+\left|A_{i_{i}}\right|+\left|B_{j_{1}}\right|+\left|B_{j_{2}}\right|+\cdots+\left|B_{j_{i}}\right|-s t\\=8 s+7 t-s t=8 s+7(7-s)-s(7-s)=(s-3)^{2}+40 \geqslant 40$
任何 $3$ 个子集的交为空集，所以 $n\geqslant 41$．
综上所述，$n$ 的最小值为 $41$．
首先证明 $n = 41$ 合乎条件．用反证法．假定存在 $X$ 的 $15$ 个子集，它们中任何 $7$ 个的并不少于 $41$ 个元素，而任何 $3$ 个的交都为空集．因每个元素至多属于 $2$ 个子集，不妨设每个元素恰好属于 $2$ 个子集（否则在一些子集中添加一些元素，上述条件仍然成立），由抽屉原理，必有一个子集，设为 $A$，至少含有 $\left[\dfrac{2 \times 56}{15}\right]+1=8$ 个元素，又设其他 $14 $ 个子集为 $A_{1}, A_{2}, \cdots, A_{14}$．考察不含 $A$ 的任何 $7$ 个子集，都对应 $X$ 中的 $41$ 个元素，所有不含 $A$ 的 $7$ 元子集组一共至少对应41 $\mathrm{C}_{14}^{7}$ 个元素．另一方面，对于元素 $a$，若 $a \notin A$，则 $A_{1}, A_{2}, \cdots, A_{14}$ 中有 $2 $ 个含有 $a$，于是 $a $ 被计算了 $C_{14}^{7}-C_{12}^{7}$ 次；若 $a\in A$，则 $A_{1}, A_{2}, \cdots, A_{14}$ 中有一个含有 $a$，于是 $a$ 被计算了 $C_{14}^{7}-C_{13}^{7}$ 次于是
$\begin{aligned} 41 \mathrm{C}_{14}^{7} \leqslant &(56-|A|)\left(\mathrm{C}_{14}^{7}-\mathrm{C}_{12}^{7}\right)+|A|\left(\mathrm{C}_{14}^{7}-\mathrm{C}_{13}^{7}\right)=56\left(\mathrm{C}_{14}^{7}-\mathrm{C}_{12}^{7}\right)-|A|\left(\mathrm{C}_{13}^{7}-\mathrm{C}_{12}^{7}\right) \leqslant 56\left(\mathrm{C}_{14}^{7}-\mathrm{C}_{12}^{7}\right)-8\left(\mathrm{C}_{13}^{7}-\mathrm{C}_{12}^{7}\right) \end{aligned}$
由此可得 $196\leqslant 195$，矛盾．
其次证明 $n\geqslant 41$．
用反证法．假定 $n\leqslant 40$，设 $X=\{ 1,2, \cdots, 56 \}$，令 $A_{i}=\{i, i+7, i+14, i+21, i+28, i+35, i+42, i+49\}i=1,2, \cdots, 7$
$B_{j}=\{j, j+8, j+16, j+24, j+32, j+40, j+48\}j=1,2, \cdots, 8$
显然
$\left|A_{i}\right|=8, i=1,2, \cdots, 7$
$\left|A_{i} \cap A_{j}\right|=0,1 \leqslant i<j \leqslant 7$
$\left|B_{j}\right|=7, j=1,2, \cdots, 8$
$\left|B_{i} \cap B_{j}\right|=0,1 \leqslant i<j \leqslant 8$
$\left|A_{i} \cap B_{j}\right|=1,1 \leqslant i \leqslant 7,1 \leqslant j \leqslant 8$
于是，对其中任何 $3$ 个子集，必有 $2$ 个同时为 $A_i$，或者同时为 $B_j$ 其交为空集．对其中任何 $7$ 个子集 $A_{i_{1}}, A_{i_{2}}, \cdots, A_{i_s}, B_{j_{1}}, B_{j_{2}}, \cdots, B_{j_{t}}(s+t=7)$ 有
$| A_{i_{1}} \cup A_{i_{2}} \cup \cdots \cup A_{i} \cup B_{j_{1}} \cup B_{j_{2}} \cup \cdots \cup B_{j_{i}} 1=\left|A_{i_{1}}\right|+\left|A_{i_{i}}\right|+\cdots+\left|A_{i_{i}}\right|+\left|B_{j_{1}}\right|+\left|B_{j_{2}}\right|+\cdots+\left|B_{j_{i}}\right|-s t\\=8 s+7 t-s t=8 s+7(7-s)-s(7-s)=(s-3)^{2}+40 \geqslant 40$
任何 $3$ 个子集的交为空集，所以 $n\geqslant 41$．
综上所述，$n$ 的最小值为 $41$．
答案
解析
备注
