趣题:选出最多的大小为奇数的子集,使得两两的交集大小都是偶数
在集合 {1, 2, ..., n} 中选出尽可能多的子集,使得每个子集所含的元素个数都是奇数,但是任意两个子集的交集都含有偶数个元素。那么,我们最多能够选出多少个这样的子集来?
容易看出,我们至少可以选出 n 个子集。例如,当 n = 4 时, {1} 、 {2} 、 {3} 、 {4} 就满足要求。我们还能选出更多的子集来吗?简单地尝试后,你会觉得似乎不行。不过,这却并不是显然的,因为存在一些不那么平凡的方案,也能让子集的数量达到 n ,例如 {1, 2, 3} 、 {1, 2, 4} 、 {1, 3, 4} 、 {2, 3, 4} 这 4 个子集也是满足要求的。看来,证明最多只能选出 n 个子集,好像并不那么容易。
不过,借助线性代数,我们有一个几乎是秒杀的证明方法。假如说我们可以从集合 {1, 2, ..., n} 中选出 m 个满足要求的子集,并且用 m 个 n 维 01 向量 v1, v2, ..., vm 分别表示这 m 个子集。例如,当 n = 4 时,子集 {1, 2, 4} 就表示成向量 (1, 1, 0, 1) 。我们用 vT 来表示矩阵的转置。注意到, viT ・ vj 正好等于这两个向量所对应的子集的交集的元素个数。根据要求,这些向量必须满足,对于任意一个 i ,viT ・ vi 都是奇数,而对于任意两个不同的 i 和 j , viT ・ vj 都是偶数。下面,我们证明这 m 个向量在模 2 的有限域 F2 上是线性无关的,从而说明 m 一定小于等于 n 。
只需要注意到,如果存在一组数 a1, a2, ..., an 使得
a1 v1 + a2 v2 + ... + an vn = 0
那么对于任意一个 i ,都有
0 = (a1 v1 + a2 v2 + ... + ai vi + ... + an vn)T vi
= a1 v1T vi + a2 v2T vi + ... + ai viT vi + ... + an vnT vi
= ai
因此,这 m 个向量是线性无关的。
题目来源:http://mathoverflow.net/questions/33911/why-linear-algebra-is-funor
一个非常类似的问题:选取最多的子集使得任两子集恰有一个公共元素
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:Matrix67 来源: Matrix67: My Blog
- 标签: 偶数 奇数
- 发布时间:2011-11-16 23:42:01
- [46] 界面设计速成
- [40] 视觉调整-设计师 vs. 逻辑
- [40] Oracle MTS模式下 进程地址与会话信
- [38] IOS安全–浅谈关于IOS加固的几种方法
- [37] android 开发入门
- [36] 程序员技术练级攻略
- [36] 如何拿下简短的域名
- [35] 图书馆的世界纪录
- [35] 【社会化设计】自我(self)部分――欢迎区
- [32] 读书笔记-壹百度:百度十年千倍的29条法则