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

在集合 {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 向量 v₁, v₂, …, v_m分别表示这 m 个子集。例如，当 n = 4 时，子集 {1, 2, 4} 就表示成向量 (1, 1, 0, 1) 。我们用 v^T来表示矩阵的转置。注意到， v_i^T· v_j正好等于这两个向量所对应的子集的交集的元素个数。根据要求，这些向量必须满足，对于任意一个 i ，v_i^T· v_i都是奇数，而对于任意两个不同的 i 和 j ， v_i^T· v_j都是偶数。下面，我们证明这 m 个向量在模 2 的有限域 F₂上是线性无关的，从而说明 m 一定小于等于 n 。

只需要注意到，如果存在一组数 a₁, a₂, …, a_n使得

a₁v₁+ a₂v₂+ … + a_nv_n= 0

那么对于任意一个 i ，都有

0 = (a₁v₁+ a₂v₂+ … + a_iv_i+ … + a_nv_n)^Tv_i

= a₁v₁^Tv_i+ a₂v₂^Tv_i+ … + a_iv_i^Tv_i+ … + a_nv_n^Tv_i

= a_i

因此，这 m 个向量是线性无关的。

题目来源：http://mathoverflow.net/questions/33911/why-linear-algebra-is-funor

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

更多线性代数的妙用：一个图论问题、一个不动点数量问题、盒子的三边和问题