某公司有 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

建议继续学习：

1. 趣题：2n位平衡01串平均有多少个平衡前缀？    (阅读：2495)
2. UyHiP趣题：限制最苛刻的选票统计程序    (阅读：2031)
3. UyHiP趣题：如果每个人都随大流，结果会怎样？    (阅读：1590)
4. UyHiP趣题：按照盒子的三边长之和来计费有没有漏洞？    (阅读：1599)