居然能在站军姿的时候 YY 出一道题……

Problem

有 $n$ 个人，对于任意一个非空子集 $S$ ，都存在一个人使得他在 $S$ 中有偶数个朋友。求证 $n$ 是偶数。

Solution

证明逆反命题。当 $n$ 是奇数时，存在一个非空集合 $S$ ，使得每个人在 $S$ 中都有偶数个朋友。也就是证明这个图的邻接矩阵某几个行向量线性相关，也就是证明这个矩阵的行列式为 0 。

直接考虑行列式的定义。由于是在 $F_2$ 下，所以 -1 的存在是毫无意义的：

$$det = \sum_{p} \Pi M_{i, p_i}$$

我们考虑排列 $p$ 以及 $p^{-1}$ 。如果 $p \neq p^{-1}$ ，那么我们将 $p$ 和 $p^{-1}$ 匹配，得到的结果一定是 0 。于是我们只需要所有 $p = p^{-1}$ 的情况。

注意到 $p = p^{-1}$ 意味着 $p$ 中每个环的长度要么是 1 要么是 2 。由于 $n$ 是奇数，所以必有大小为 1 的环，由于 $M$ 对角线上所有元素均为 0 ，所以此时的 $\Pi M_{i, p_i}$ 一定是 0 ，就可以得到 $det(M) = 0$ 。