









Uyhip2016 December
有一个议会里面有n个人,有一些委员会,要求:
- 对任意两个委员会,有恰好一个人同时在这两个委员会中。
- 任何一个人在至少两个委员会中
- 任何一个委员会里至少有两个人
求最多有多少个委员会。将答案表示为n的函数。
话说。。有一天我在波士顿的街头漫步,突然看到天空中飞过一只白鸽,她以不同的方向穿越了天空。(捂着胸口说)对呀,为什么我不使用新的方法呢
手算n=4的情况发现可以{1,2},{1,3},{1,4},{2,3,4},于是猜想答案就是n。
接下来就是证明了。发现第一个条件特别强,相当于两个向量的内积是1。考虑从线性代数的角度分析此题。
令Aij表示成员j是否在第i个委员会中,是就是1,不是就是0。假设有m个委员会,那么A的大小是m×n的。分析一下会发现,条件1相当于AAT的非对角元素都是1,条件3相当于AAT的对角元素都>1,条件2是来卖萌的。
然后爆算一发(见我的pdf)就知道det。换句话说\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了。。
2017年1月01日 08:33
%%%%%%%%%%%%%%