趣题：选出最多的大小为奇数的子集，使得两两的交集大小都是偶数
icon2 Brain Storm | icon4 2011-11-16 13:11| icon322 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com

    在集合 {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
一个非常类似的问题：选取最多的子集使得任两子集恰有一个公共元素
更多线性代数的妙用：一个图论问题、一个不动点数量问题、盒子的三边和问题

Posted in Brain Storm
Tags: , , ,
Trackback: http://www.matrix67.com/blog/archives/4750/trackback
我猜您可能还喜欢：

22 条回复

  • 楼层: 沙发 | 2011-11-16 13:42 | 万万没有想到 说：

    线性代数。。。。恨！

  • 楼层: 板凳 | 2011-11-16 16:30 | Seter 说：

    ym!

  • 楼层: 地毯 | 2011-11-16 17:07 | z1w1j 说：

    前排！

  • 楼层: 地板 | 2011-11-16 17:08 | z1w1j 说：

    前排！！

  • 楼层: 地下室 | 2011-11-16 18:42 | hanyuwei70 说：

    前排~~~~

  • 楼层: 地基 | 2011-11-16 20:43 | 挽魇 说：

    巧妙！

  • 楼层: 地壳 | 2011-11-17 18:08 | biohu 说：

    同沙发

  • 楼层: 地幔 | 2011-11-18 7:58 | stryandk 说：

    刚刚学了线性代数
    看起来在神牛的手里能衍生出无数变化的样子……

  • 楼层: 地核 | 2011-11-19 18:33 | myxiaoniao 说：

    这最后一步真是跳跃性思维阿
    ai是互质的，最后一步将表明任一ai是偶数，矛盾，因此均为0

  • 楼层: 10楼 | 2011-11-20 16:36 | onion 说：

    楼上，ai不一定是互质的吧？这里只是假设如果存在一组数 a1, a2, ..., an，并没用说ai是互质的。。。

    最后一步确实没用太看懂。。。难道假设了ai'*aj=0, ai*ai=1?不过这样的话，就只证明了子集只有1个元素，交集是空集的情况。。。

    求解释。。。

  • 楼层: 11楼 | 2011-11-21 12:27 | phyxnj 说：

    回LS：
    是所有数的最大公约数为1

  • 楼层: 12楼 | 2011-11-22 12:25 | Chern 说：

    应该是这m个向量在(F2)^n上线性无关吧。

  • 楼层: 12a楼 | 2011-11-25 13:38 | jason 说：

    不是特别明白，至少这里的证明还缺少足够的细节。a1, a2, ..., an可以是实数的，所谓互质和奇偶对实数是没有意义的。但我还是比较相信这个结论的：对角线为奇数，其他元素为偶数的对称阵是满秩的。

  • 楼层: 14楼 | 2011-12-07 23:21 | Chap 说：

    最後一步看不懂..為什麼可以全部消除？

  • 楼层: 15楼 | 2011-12-09 0:32 | Chap 说：

    "对角线为奇数，其他元素为偶数的对称阵是满秩的"
    有没有大牛可以证明上面的结论

  • 楼层: 16楼 | 2011-12-15 9:43 | Ruki 说：

    最后代进去之后发现ai都应为偶数。那么将a1v1+a2v2+...+amvm=0两边除2.再代进去还能推出是偶数……是这样？

  • 楼层: 17楼 | 2011-12-16 2:04 | wuyuelgb 说：

    线代实在神奇。。。
    看了几个线代的证明都是这种感觉，看答案都很容易，就是怎么也想不出答案。。。

  • 楼层: 18楼 | 2012-01-04 12:08 | zlqiszlq 说：

    都说过在F2域上了
    +、-定义成异或
    *、/定义成和运算
    满足有单位元，封闭
    自然就可以成为数域了

  • 楼层: 19楼 | 2012-01-07 2:14 | 弱弱的说一句 说：

    Even/Odd Town Problem

  • 楼层: 20楼 | 2012-02-28 23:03 | Ernest-ZTG 说：

    把 v1,v2,v3,...,vn 这 n 个列向量并排成为 n*n 矩阵 V，
    W = (V转置) * V，
    则 W 的第 i 行第 j 列正好就是第 i 个和第 j 个集合的交集的元素个数(mod 2)。
    由题目要求，W(i,j) = ( (i==j)?1:0 ) ，亦即 W = I （n*n 单位矩阵），
    显然要求 V 是满秩方阵，亦即 v1,v2,v3,...,vn 线性无关。

  • 楼层: 21楼 | 2012-03-12 15:04 | 台州整形医院 说：

    写的很不错。

  • 楼层: 22楼 | 2012-12-13 11:02 | cervelo 说：

    不是特别明白，至少这里的证明还缺少足够的细节

您也随便说几句吧：

您可以在 Gravatar 设置您的头像。