在集合 {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
一个非常类似的问题：选取最多的子集使得任两子集恰有一个公共元素
更多线性代数的妙用：一个图论问题、一个不动点数量问题、盒子的三边和问题
线性代数。。。。恨！
ym!
前排！
前排！！
前排~~~~
巧妙！
同沙发
刚刚学了线性代数
看起来在神牛的手里能衍生出无数变化的样子……
这最后一步真是跳跃性思维阿
ai是互质的，最后一步将表明任一ai是偶数，矛盾，因此均为0
楼上，ai不一定是互质的吧？这里只是假设如果存在一组数 a1, a2, …, an，并没用说ai是互质的。。。
最后一步确实没用太看懂。。。难道假设了ai’*aj=0, ai*ai=1?不过这样的话，就只证明了子集只有1个元素，交集是空集的情况。。。
求解释。。。
回LS：
是所有数的最大公约数为1
应该是这m个向量在(F2)^n上线性无关吧。
不是特别明白，至少这里的证明还缺少足够的细节。a1, a2, …, an可以是实数的，所谓互质和奇偶对实数是没有意义的。但我还是比较相信这个结论的：对角线为奇数，其他元素为偶数的对称阵是满秩的。
最後一步看不懂..為什麼可以全部消除？
“对角线为奇数，其他元素为偶数的对称阵是满秩的”
有没有大牛可以证明上面的结论
最后代进去之后发现ai都应为偶数。那么将a1v1+a2v2+…+amvm=0两边除2.再代进去还能推出是偶数……是这样？
线代实在神奇。。。
看了几个线代的证明都是这种感觉，看答案都很容易，就是怎么也想不出答案。。。
都说过在F2域上了
+、-定义成异或
*、/定义成和运算
满足有单位元，封闭
自然就可以成为数域了
Even/Odd Town Problem
把 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 线性无关。
写的很不错。
不是特别明白，至少这里的证明还缺少足够的细节
假设可以有至少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]与一些大小为偶的集合的对称差，有奇数个元素，但它又是空集，矛盾