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

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

23 条评论

  • 万万没有想到

    线性代数。。。。恨!

  • z1w1j

    前排!

  • z1w1j

    前排!!

  • hanyuwei70

    前排~~~~

  • 挽魇

    巧妙!

  • biohu

    同沙发

  • stryandk

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

  • myxiaoniao

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

  • onion

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

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

    求解释。。。

  • phyxnj

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

  • Chern

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

  • jason

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

  • Chap

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

  • Chap

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

  • Ruki

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

  • wuyuelgb

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

  • zlqiszlq

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

  • 弱弱的说一句

    Even/Odd Town Problem

  • 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 线性无关。

  • cervelo

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

  • qirenrui

    假设可以有至少n+1个这样的集合,记为A[1],A[2],…,A[n+1]
    考虑它们中任意若干个的对称差,共2^(n+1)个
    这些集合都是{1,2,…,n}的子集,所以至多有2^n种取法,所以其中有两个相同
    考虑这两个相同的集合的对称差,它也可以写成两组A[i]一起取对称差,删掉重复的A[i]后,我们得到若干个集合的对称差为空集
    不妨设A[1],A[2],…,A[k]的对称差为空集,由于对称差与交的分配率
    A[1]与A[1],A[2],…,A[k]的对称差的交集,就是A[1]与一些大小为偶的集合的对称差,有奇数个元素,但它又是空集,矛盾

发表评论