UyHiP趣题：拉灯游戏总有解吗？

某公司有 n 间办公室。每间办公室都有一盏灯，拉动它的开关即可改变电灯的状态。某些办公室之间存在“业务相关”的关系（这是一个对称的关系）。一个办公室可以和 0 到任意多个办公室相关。愚人节那天，有人在大家上班之前偷偷对办公室的电灯开关做了手脚：拉动任何一个办公室的电灯开关，都会同时改变该办公室以及所有相关办公室的电灯状态。初始时，所有灯都是关着的。证明：等到大家来上班后，总能用有限次的开关，最终把所有办公室的灯都打开。

证明：对 n 施归纳。只有一间办公室时，结论显然成立。下面假设我们已经有办法让任意 n-1 个办公室的灯全部打开。如果把其中某 n-1 个办公室的灯全打开后，发现剩下的那个办公室的灯正好也亮了，问题就解决了。否则，我们就相当于有办法同时改变任意 n-1 个办公室的电灯状态（并且不对剩下的那个办公室造成影响）。

考虑这样的操作：先改变除了办公室 A 以外的所有办公室的电灯状态，再改变除办公室 B 以外的所有办公室的电灯状态。这样下来的结果就是，只有办公室 A 、 B 的电灯状态真的被改变了，其它办公室的电灯状态又都变了回去。也就是说，我们可以同时改变任意两个办公室的电灯状态了（并且不影响其它办公室）。

如果 n 是偶数，两个两个地把它们的灯打开，问题直接就解决了。麻烦的就是，如果 n 是奇数的话，该怎么办呢？要是有一个办公室正好有偶数个相关的办公室就好了，这样的话就可以先拉下它的开关，剩下灯没亮的办公室正好偶数个，问题也就解决了。下面我们就证明，如果 n 是奇数，那么一定存在一个办公室，它正好有偶数个相关办公室。

注意到，把所有办公室的相关办公室数加起来，结果一定是一个偶数（因为每个相关关系都被算了两次）。但是，我们一共有奇数个办公室，如果它们各自的相关办公室数目都是奇数，加起来也还是个奇数。因此，至少有一间办公室，它有偶数个相关办公室。这就完成了整个证明过程的最后一环。

问题来源：http://www.brand.site.co.il/riddles/201103q.html