给定正整数 $n(\geqslant 2)$，求 $|X|$ 的最小值，使得对集一合 $X$ 的任意 $n$ 个二元子集 $B_{1}, B_{2}, \cdots, B_{n}$，都存在集合 $X$ 的一个子集 $Y$，满足：
（1）$|Y|=n$；
（2）对 $i=1,2, \cdots, n$，都有 $\left|Y \cap B_{i}\right| \leqslant 1$．
这里 $|A|$ 表示有限集合 $A$ 的元素个数．
（1）$|Y|=n$；
（2）对 $i=1,2, \cdots, n$，都有 $\left|Y \cap B_{i}\right| \leqslant 1$．
这里 $|A|$ 表示有限集合 $A$ 的元素个数．
【难度】
【出处】
2006年中国西部数学奥林匹克试题
【标注】
【答案】
略
【解析】
$|X|_{\min }=2 n-1$
（1）当 $|X|=2 n-2$ 时不一定存在满足条件的 $Y$．事实上，令 $X=\{1,2, \cdots, 2 n-2\}$，考虑 $X$ 的一个划分 $B_{1}=\{1,2\}, B_{2}=\{3,4\}, \cdots, B_{n-1}=\{2 n-3,2 n-2\}$．因为 $|Y|= n$，因此 $Y$ 中至
少有两个元素属于同一个 $B_j$，故此时 $\left|Y \cap B_{j}\right|>1$，矛盾．
（2）下证 $|X|=2 n-1$ 符合题意．
记 $B=\bigcup\limits_{i=1}^{n} B_{i},|B|=2 n-1-z$，则存在 $z$ 个在所有 $B_i$ 中未出现的元素，记为 $a_{1}, a_{2}, \cdots, a_{z}$．如果 $z \geqslant n-1$，则取 $Y=\left\{a_{1}, \cdots\right.a_{n-1}, d \}, d \in B$ 便可．
下设 $z < n-1$．
设在 $B_{1}, B_{2}, \cdots, B_{n}$ 中仅出现 $1$ 次的元素有 $t$ 个，因 $\displaystyle \sum\limits_{i=1}^{n}\left|B_{i}\right|=2n$，则 $t+2(2 n-1-z-t) \leqslant 2 n$，所以 $t \geqslant 2 n-2-2 z$．
故在 $B_{1}, B_{2}, \cdots, B_{n}$ 中出现的次数 $\geqslant 2$ 的元素至多累计出现了 $2 n-(2 n-2-2 z)=2+2 z$ 次．
考虑在 $B_{1}, B_{2}, \cdots, B_{n}$ 中出现一次的元素 $b_{1}, b_{2}, \cdots, b_{t}$，于是 $B_{1}, B_{2}, \cdots, B_{n}$ 中的元素不含 $b_{1}, b_{2}, \cdots, b_{t}$ 的 $B_j$ 至多有 $\dfrac{2+2 z}{2}=1+z$ 个．故至少有 $n-(z+1)=n-z-1$ 个 $B_j$ 含有 $b_{1}, b_{2}, \cdots,b_t$．
不妨设 $B_{1}, B_{2}, \cdots, B_{n-1-z}$ 分别含有 $b_{1}, b_{2}, \cdots, b_{t}$ 中的元素 $\tilde{b}_{1}, \tilde{b}_{2}, \cdots, \tilde{b}_{n-1-z}$（如果这样 $B_{l}(1 \leqslant l \leqslant n-1-z)$ 中有多个只选一个）．
因为 $2(n-1-z)+z=2 n-2-z<2 n-1$，所以必有某个元素 $d$ 不出现在 $B_{1}, B_{2}, \cdots, B_{n-1-z}$ 中且出现在 $B_{n-z}, \cdots, B_{n}$ 中，记 $Y=\left\{a_{1}, a_{2}, \cdots, a_{z}, \tilde{b}_{1}, \tilde{b}_{2}, \cdots, \tilde{b}_{n-1-z}, d\right\}$，则 $Y$ 满足要求．
（1）当 $|X|=2 n-2$ 时不一定存在满足条件的 $Y$．事实上，令 $X=\{1,2, \cdots, 2 n-2\}$，考虑 $X$ 的一个划分 $B_{1}=\{1,2\}, B_{2}=\{3,4\}, \cdots, B_{n-1}=\{2 n-3,2 n-2\}$．因为 $|Y|= n$，因此 $Y$ 中至
少有两个元素属于同一个 $B_j$，故此时 $\left|Y \cap B_{j}\right|>1$，矛盾．
（2）下证 $|X|=2 n-1$ 符合题意．
记 $B=\bigcup\limits_{i=1}^{n} B_{i},|B|=2 n-1-z$，则存在 $z$ 个在所有 $B_i$ 中未出现的元素，记为 $a_{1}, a_{2}, \cdots, a_{z}$．如果 $z \geqslant n-1$，则取 $Y=\left\{a_{1}, \cdots\right.a_{n-1}, d \}, d \in B$ 便可．
下设 $z < n-1$．
设在 $B_{1}, B_{2}, \cdots, B_{n}$ 中仅出现 $1$ 次的元素有 $t$ 个，因 $\displaystyle \sum\limits_{i=1}^{n}\left|B_{i}\right|=2n$，则 $t+2(2 n-1-z-t) \leqslant 2 n$，所以 $t \geqslant 2 n-2-2 z$．
故在 $B_{1}, B_{2}, \cdots, B_{n}$ 中出现的次数 $\geqslant 2$ 的元素至多累计出现了 $2 n-(2 n-2-2 z)=2+2 z$ 次．
考虑在 $B_{1}, B_{2}, \cdots, B_{n}$ 中出现一次的元素 $b_{1}, b_{2}, \cdots, b_{t}$，于是 $B_{1}, B_{2}, \cdots, B_{n}$ 中的元素不含 $b_{1}, b_{2}, \cdots, b_{t}$ 的 $B_j$ 至多有 $\dfrac{2+2 z}{2}=1+z$ 个．故至少有 $n-(z+1)=n-z-1$ 个 $B_j$ 含有 $b_{1}, b_{2}, \cdots,b_t$．
不妨设 $B_{1}, B_{2}, \cdots, B_{n-1-z}$ 分别含有 $b_{1}, b_{2}, \cdots, b_{t}$ 中的元素 $\tilde{b}_{1}, \tilde{b}_{2}, \cdots, \tilde{b}_{n-1-z}$（如果这样 $B_{l}(1 \leqslant l \leqslant n-1-z)$ 中有多个只选一个）．
因为 $2(n-1-z)+z=2 n-2-z<2 n-1$，所以必有某个元素 $d$ 不出现在 $B_{1}, B_{2}, \cdots, B_{n-1-z}$ 中且出现在 $B_{n-z}, \cdots, B_{n}$ 中，记 $Y=\left\{a_{1}, a_{2}, \cdots, a_{z}, \tilde{b}_{1}, \tilde{b}_{2}, \cdots, \tilde{b}_{n-1-z}, d\right\}$，则 $Y$ 满足要求．
答案
解析
备注
