Processing math: 51%

Uyhip2016 December

r_64 posted @ 2016年12月31日 14:17 in 未分类 with tags uyhip , 1281 阅读

题目

有一个议会里面有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^Tm\times m矩阵)。被线性代数虐傻的我印象深刻地记得\text{rank}(A)=\text{rank}(A^T)=\text{rank}(AA^T)=\text{rank}(A^TA),于是就有\text{rank}(A)=m。然而Am\times n矩阵,那就意味着m\le n

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

故答案为n。Q.E.D


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

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


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

ps.

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

Chenyao 说:
2017年1月01日 08:33

%%%%%%%%%%%%%%


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter