首页 > 代码库 > 开关灯问题

开关灯问题

设 $G=(V,E)$ 是一个有限连通图,在每个顶点 $v\in V$ 处放置有一盏灯和一个开关,按下开关以后会改变 $v$ 以及与 $v$ 相邻顶点处的灯的状态。开始时所有灯都是亮的,问能否经过有限次操作把所有灯都熄灭?


答案是肯定的,对任何连通的有限图 $G$ 总是可以办到的。

我们可以假定 $G$ 是简单图(任何两个顶点之间之多只有一条边),这对讨论没有影响。

记 $N[v]$ 为顶点 $v$ 以及与 $v$ 相邻的顶点组成的集合。如果能够证明下面的定理:


定理:存在顶点集 $V$ 的子集 $S$ 使得对任何 $v\in V$,$|S\cap N[v]|$ 都是奇数。


假设存在定理中所述的集合 $S$,那么只要把 $S$ 中的顶点处的开关分别按下一次即可,这样每盏灯都被改变了奇数次状态,从而都熄灭了。


定理的证明:设 $V=\{v_1,\ldots,v_n\}$,对 $V$ 的子集 $S$,定义集合 $S$ 的示性向量 \[1_S=(a_1,\cdots,a_n)\] 为:若 $v_i\in S$ 则 $a_i=1$,否则 $a_i=0$。如果 $T$ 是 $V$ 的另一个子集,$T$ 的示性向量为 \[1_T=(b_1,\cdots,b_n),\]那么 $1_S$ 和 $1_T$ 的内积为

\[1_S\cdot 1_T=\sum_{i=1}^n a_ib_i=|S\cap T|.\]

其中 $|S\cap T|$ 为 $S$ 和 $T$ 的交集的元素个数。

如果我们的运算是在有限域 $\mathbb{F}_2$ 上进行的,那么 $1_S\cdot1_T=1$ 当且仅当 $|S\cap T|$ 为奇数。从现在起,我们都在 $\mathbb{F}_2$ 上考虑问题。

上面这些分析虽然很简单,但却是我们证明的关键。


现在设 $1_{v_1},\cdots,1_{v_n}$ 分别是集合 $N[v_1],\cdots,N[v_n]$ 的示性向量,把它们作为列向量依次排列为矩阵 $A$:

\[A=(1_{v_1}^T,\cdots,1_{v_n}^T).\]

现在我们还不知道应该怎样选取集合 $S$,但是根据前面的叙述我们知道 $|S\cap N[v]|$ 对每个 $v$ 都是奇数这个条件等价于(注意是二元域上的运算)\[1_S A=(1,1,\cdots,1).\]

因此我们只要证明向量 $p=(1,1,\cdots,1)$ 可以被矩阵 $A$ 的行向量线性表出即可。


记 $W$ 为 $A$ 的行向量生成的线性空间,$W^\bot$ 为 $W$ 在 $\mathbb{F}_2^n$ 中的正交补空间,$W$ 和 $W^\bot$ 满足下面的关系:

\[\dim W+\dim W^\bot=n,\quad (W^\bot)^\bot=W.\]

所以要证明 $p\in W$,只要证明 $p$ 和 $W^\bot$ 正交即可。然而 $W^\bot=\ker A$,因此只要证明对任意行向量 $x\in\mathbb{F}_2^n$,若 $Ax^T=0$,则 $(x,p)=0$。或者等价地说,若 $(x,p)\ne0$,则 $Ax^T\ne0$。


$(x,p)\ne0$ 说明 $x$ 的分量中有奇数个 1,$Ax^T$ 是 $A$ 的一些行向量的和,这些行向量与 $x$ 中的那些 1 相对应,因此我们需要说明 $A$ 的任何奇数个行向量的和不会是 0。


若不然,不妨假设 $A$ 的前 $r$ 行之和为 0,这里 $r$ 是一个奇数。考虑由顶点 $v_1,\cdots,v_r$ 以及它们之间的边组成的子图 $H$,于是 $H$ 的每个顶点的度数是奇数(想一想,为什么?)。然而\[\sum_{i=1}^r \deg v_i=2|E(H)|.\]奇数个奇数的和等于偶数,这不可能,这就完成了证明。

开关灯问题