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

晚上陪女儿玩了她喜爱的桌游Crazy Matching（疯狂对对对）．

核心规则比较简单，就是找出任意两张卡片里的相同图案，玩家人数不同时玩法略有不同．

在玩过几次之后，我发现任意两张卡片上相同的图案恰好是一个，这样能在保证一定难度的同时避免无解的情况出现．于是我想到了一道集合中的经典题目，为了确认自己的想法，我拿出说明书把游戏中的元素重新确认了一遍．

这个桌游中共有个不同的图案，张卡片，其中每张卡片上有个不同的图案．

首先想到的是这样一道题（出自matrix67博客）：

题目1 在中选取尽可能多的子集，使得任意两个子集的交集有且仅有一个元素．

用一些较小的简单尝试之后发现此题答案恰好为．下面进行证明．

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

记个子集，，，所对应的向量分别为，，，．于是对于，．以及．

令为，，，的任意一个线性组合．
于是

当时，．而上式的每一项均为非负，故只能是所有的均为．由此证明这个向量线性无关．

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

题目2 有个元集合，其中任意两个集合的交集恰有一个元素，则这些集合的并集至少有几个元素？

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

如果存在某个集合（不妨设为），有（），使得，，，还在其它集合中．不妨设所在的集合（除外）个数是最多的，记为s．下证：．

设这个集合为，，，．考虑某个所在的集合（不妨设为）．由于与，，，均有一个公共元素，而，，，均不含以外的公共元素，中还有个剩余元素．于是．

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

因此这些集合的并集元素个数至少为．

构造略．