两道题

溦澜居士

求严谨证明

战巡

1、

先明确一下标记，令$\mu(*)$表示计数测度，即$\mu(A)$表示集合$A$的元素个数

先来看一些极端情况

情况一：
如果$\mu(A_1\cap A_2\cap...\cap A_t)=0$，那么必然会存在集合$A_k$，$k\in\{1,2,...,t\}$，使得
\[A_k\cap(A_1\cup A_2\cup ... A_{k-1}\cup A_{k+1}\cup ...\cup A_t)=\emptyset\]
这样如果甲选了$A_k$里的元素，鉴于$n\ge 2$，乙只要马上选一个$A_k$里另一个元素，就可以彻底阻止甲通过获全$A_k$集合而获胜，这等于帮乙排除了一个集合，直接变成了$(n,t-1)$的问题，对乙而言更简单了，因此这种情况没啥好讨论的。

情况二：
如果$\mu(A_1\cap A_2\cap...\cap A_t)\ge 2$，那么乙无论如何都能选到$A_1\cap A_2\cap...\cap A_t$里面的一个元素，从而彻底让甲没戏，这种情况也没啥好讨论的。

那唯一值得讨论的，就是$\mu(A_1\cap A_2\cap...\cap A_t)=1$的情况。
此时甲为了不让乙占领这个交集的唯一元素，必然会先手占领。
现在不妨把这个交集的唯一元素整个踢出去，定义集合
\[A_{k}^n=A_k,A_{k}^{n-1}=A_k^n-(A_1\cap A_2\cap ...\cap A_t)\]
得到集合
\[A_1^{n-1},A_2^{n-1},...,A_t^{n-1}\]
由于唯一的交集元素被踢，剩下的这些玩意里面，肯定会有
\[A_1^{n-1}\cap A_2^{n-1}\cap...\cap A_t^{n-1}=\emptyset\]
这意味着这些集合里面，必然可以拆成若干个独立部分，假设总共能拆成$M$个部分$(M\le t)$，每个部分分别有$t_1,t_2,...,t_M$个集合，令
\[B_1=A_1^{n-1}\cap A_2^{n-1}\cap...\cap A_{t_1}^{n-1}\]
\[B_2=A_{t_1+1}^{n-1}\cap A_{t_1+2}^{n-1}\cap...\cap A_{t_1+t_2}^{n-1}\]
\[...\]
\[B_M=A_{t_1+t_2+...t_{M-1}}^{n-1}\cap A_{t_1+t_2+...+t_{M-1}+1}^{n-1}\cap...\cap A_t^{n-1}\]
为每个部分，且可以满足
\[\mu(B_k)>0, k\in\{1,2,...,M\}\]

此时到乙了，乙为了尽可能阻止甲获胜，必然会选择$t_1,t_2,...,t_M$里面最大那个（即涵盖集合最多的那个），假设为$t_m$好了（即$\max\{t_1,t_2,...,t_M\}=t_m$），然后在对应的$B_m$里面抽一个元素，从而让甲失去最多个数的集合。

此时重新轮到甲，而场上的情况，变成：
剩下可用的集合分为$M-1$个独立部分，即$B_1,B_2,...,B_{m-1},B_{m+1},...,B_M$，每个部分集合数$t_k\le t_m$，每个集合$n-1$个元素。

甲要在这$M-1$个部分里面选一个来完成，假设选了$B_q$好了，此时游戏变成了$t_q$个集合，$n-1$个元素，如果此时乙能够在这种游戏里阻止甲，那原版游戏里乙也能阻止甲。

且注意$t_q\le t_m$，有
\[2t_q\le t_q+t_m\le t_1+t_2+...+t_M=t\]
翻译翻译，就是说，如果乙能在一场$\frac{t}{2}$个集合，每集合$n-1$个元素的游戏里阻止甲，那他就能在$t$个集合，每个集合$n$个元素的游戏里阻止甲。

最后就是归纳的事情了，$n=2$时，$t$的最大上限为$1$，归纳出来就是$t<2^{n-1}$。