Uyhip2016 December

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

题目

有一个议会里面有$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了。。

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

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


登录 *


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