从女儿的桌游想到的两道集合问题

证明 考虑每个子集所对应的𝑛维01向量，容易看出，两个子集的交集的元素个数恰为其对应向量的内积．下面证明：满足要求的一组子集所对应的向量一定是线性无关的，从而直接得到向量个数不超过𝑛的结论．

记𝑚个子集𝐴_(1)，𝐴_(2)，⋯，𝐴_(𝑚)所对应的向量分别为𝑣_(1)^(⃗)，𝑣_(2)^(⃗)，⋯，𝑣_(𝑚)^(⃗)．于是对于𝑖≠𝑗，𝑣_(𝑖)^(⃗)⋅𝑣_(𝑗)^(⃗)=1．以及𝑣_(𝑖)^(⃗)⋅𝑣_(𝑖)^(⃗)=|𝐴_(𝑖)|．

令𝑠^(⃗)=∑_(𝑖=1)^(𝑚)𝑎_(𝑖)𝑣_(𝑖)^(⃗)为𝑣_(1)^(⃗)，𝑣_(2)^(⃗)，⋯，𝑣_(𝑚)^(⃗)的任意一个线性组合．
于是

公式：\begin{aligned} \vec{s}\cdot\vec{s}=&\sum\limits_{i=1}^m\sum\limits_{j=1}^ma_ia_j(\vec{v_i}\cdot\vec{v_j})\\ =&(\sum\limits_{i=1}^ma_i)^2+\sum\limits_{i=1}^ma_i^2(|A_i|-1) \end{aligned}

当𝑠^(⃗)=∑_(𝑖=1)^(𝑚)𝑎_(𝑖)𝑣_(𝑖)^(⃗)=0时，𝑠^(⃗)⋅𝑠^(⃗)=0．而上式的每一项均为非负，故只能是所有的𝑎_(𝑖)均为0．由此证明这𝑚个向量线性无关．

思考了一会，我发现两个问题其实并不完全一致．一方面，上面的题目中对每个子集的元素个数未作要求，而每张卡片上的图案均为8．是否因为加上了每个子集元素个数均相同这一条件，导致了卡片数量为54（略少于图案数量57）这一结果？于是有了以下的问题．

分析
首先考虑最简单的情况，即所有集合均有一个相同的元素，而其余元素均不同．此时所有集合的并集有1+54×7=379个元素，这显然不是最佳的．

如果存在某个集合（不妨设为𝐴_(0)），有𝑎_(1),𝑎_(2),⋯,𝑎_(𝑘)∈𝐴_(1)（𝑘≥2），使得𝑎_(1)，𝑎_(2)，⋯，𝑎_(𝑘)还在其它集合中．不妨设𝑎_(1)所在的集合（除𝐴_(0)外）个数是最多的，记为s．下证：𝑠≤7．

设这𝑠个集合为𝐴_(1)，𝐴_(2)，⋯，𝐴_(𝑠)．考虑某个𝑎_(2)所在的集合（不妨设为𝐴_(𝑠+1)）．由于𝐴_(𝑠+1)与𝐴_(1)，𝐴_(2)，⋯，𝐴_(𝑠)均有一个公共元素，而𝐴_(1)，𝐴_(2)，⋯，𝐴_(𝑠)均不含𝑎_(1)以外的公共元素，𝐴_(𝑠+1)中还有7个剩余元素．于是𝑠≤7．

将除𝐴_(0)外的53个集合按照与𝐴_(0)的公共元素分为8组，每一组的集合个数均不超过7．容易知道其中至少有一组恰好有7个集合．这7个集合与𝐴_(0)有同一个公共元素．

因此这些集合的并集元素个数至少为8+7×7=57．

构造略．