技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 趣题:选出最多的大小为奇数的子集,使得两两的交集大小都是偶数

趣题:选出最多的大小为奇数的子集,使得两两的交集大小都是偶数

浏览:908次  出处信息

     在集合 {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

     一个非常类似的问题:选取最多的子集使得任两子集恰有一个公共元素

QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1