0%

TOAD-puzzle-34

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