Uyhip2016 December

题目

有一个议会里面有$n$个人，有一些委员会，要求：

• 对任意两个委员会，有恰好一个人同时在这两个委员会中。
• 任何一个人在至少两个委员会中
• 任何一个委员会里至少有两个人

求最多有多少个委员会。将答案表示为$n$的函数。

话说。。有一天我在波士顿的街头漫步，突然看到天空中飞过一只白鸽，她以不同的方向穿越了天空。(捂着胸口说)对呀，为什么我不使用新的方法呢

手算$n=4$的情况发现可以$\{1,2\},\{1,3\},\{1,4\},\{2,3,4\}$，于是猜想答案就是$n$。

接下来就是证明了。发现第一个条件特别强，相当于两个向量的内积是$1$。考虑从线性代数的角度分析此题。

令$A_{ij}$表示成员$j$是否在第$i$个委员会中，是就是$1$，不是就是$0$。假设有$m$个委员会，那么$A$的大小是$m\times n$的。分析一下会发现，条件1相当于$AA^T$的非对角元素都是$1$，条件3相当于$AA^T$的对角元素都$>1$，条件2是来卖萌的。

然后爆算一发(见我的pdf)就知道$\det(AA^T)>0$。换句话说$\text{rank}(AA^T)=m$(因为$AA^T$是$m\times m$矩阵)。被线性代数虐傻的我印象深刻地记得$\text{rank}(A)=\text{rank}(A^T)=\text{rank}(AA^T)=\text{rank}(A^TA)$，于是就有$\text{rank}(A)=m$。然而$A$是$m\times n$矩阵，那就意味着$m\le n$。

我们证明了答案不超过$n$，那么只需要给出答案为$n$的栗子就可以QED啦!栗子就是：编号为$1$的集合包含$1$除外的所有人；编号为$i(i>1)$的集合包含$1$和$i$。可以验证这个是满足所有条件的。

故答案为$n$。Q.E.D

标答给出来了。。我还没看，看了之后可能会更新一下这个blog。

然而，包括我在内的前若干人都是用的上面这一种比标答简单很多的方法。。

2017年的第一个题怎么这么垃圾啊。。超级原题啊。。

ps.

所以很久以前就知道了答案的人就不能发答案给Michael了。。