问题描述
题意：现在有 \(n\) 个人要成立若干个社团（一个人可以属于多个社团）满足
- 每个社团的人数均为奇数；
- 任意两个不同的社团所共有的成员数量为偶数。
求证：所能成立的社团数量不超过 \(n\) 个。
提示：形式化地说，记 \(U=\{1,2,\dots,n\}\)，已知集簇 \(S\subseteq 2^U\) 满足对于任意 \(A,B\in S\)，\(|A\cap B|\) 为奇数当且仅当 \(A=B\)。求证 \(|S|\leq n\)。
设 \(A\) 是一个集合，记号 \(2^A\) 表示由 \(A\) 的所有子集组成的集簇（集合的集合）。
容易发现，只要每个人均成立一个只包含自己的社团，就可以成立恰好 \(n\) 个社团，满足每个社团的人数均为奇数（\(1\) 个），任意两个不同的社团所共有的成员数量为偶数（\(0\) 个）。
解答
假设已经确定了某种成立 \(m\) 个社团的方案，第 \(i(1\leq i\leq m)\) 个社团包含的成员的集合记作 \(C_i\)。
我们考虑一个二元域 \(\mathbb Z_2\)，包含 \(\{0,1\}\) 两个元素，在域上定义模 \(2\) 意义下的加法和乘法。构造 \(\mathbb Z_2^{m\times n}\) 上的矩阵 \(A\)，满足
\[A_{i,j}=\begin{cases}1 & j\in C_i\\0 & j\not\in C_i\end{cases} \]我们用 \(\dim V\) 表示线性空间 \(V\) 的维数（线性基的个数），\(\mathrm{range\ } T\) 表示线性变换 \(T\) 的值域。由于 \(A\) 是 \(\mathbb Z_2^n\to\mathbb Z_2^m\) 的线性变换，其值域的维数一定满足不等式
\[\dim\mathrm{range\ }\boldsymbol A\leq n \]考虑 \(AA^{\mathsf T}\) 这两个矩阵的乘积，是一个 \(m\times m\) 的矩阵，根据其第 \(i\) 行第 \(j\) 列的值所代表的组合意义，容易看出
\[(AA^{\mathsf T})_{i,j}=\begin{cases}1 & |C_i\cap C_j| \text{是奇数}\\0 & |C_i\cap C_j| \text{是偶数}\end{cases} \]根据题目的约束条件，\(|C_i\cap C_j|\) 是奇数当且仅当 \(i=j\)，所以对角线上的数均为 \(1\)，其余位置的数均为 \(0\)，于是
\[AA^{\mathsf T}=\mathbf I \]其中 \(\mathbf I\) 表示 \(m\) 阶单位矩阵，这意味着
\[\dim\mathrm{range\ }\mathbf I=m \]另一方面，显然有 \(\mathrm{range\ }AA^{\mathsf T}\subseteq \mathrm{range\ }A\)，于是
\[\dim\mathrm{range\ }AA^{\mathsf T}\leq\dim\mathrm{range\ }A \]联立上述结果，得到
\[m=\dim\mathrm{range\ }\mathbf I=\dim\mathrm{range\ }AA^{\mathsf T}\leq\dim\mathrm{range\ }A\leq n \]这表明 \(m\leq n\) 始终成立，原命题得证。
2022年12月9日 于东莞松山湖
标签：dim,组合,选讲,leq,range,mathsf,社团,杂题,mathrm From： https://www.cnblogs.com/szdytom/p/combinatorial-misc-3.html