TOAD 34 - Odd goings on

居然能在站军姿的时候 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\) 。