某公司有 n 间办公室。每间办公室都有一盏灯，拉动它的开关即可改变电灯的状态。某些办公室之间存在“业务相关”的关系（这是一个对称的关系）。一个办公室可以和 0 到任意多个办公室相关。愚人节那天，有人在大家上班之前偷偷对办公室的电灯开关做了手脚：拉动任何一个办公室的电灯开关，都会同时改变该办公室以及所有相关办公室的电灯状态。初始时，所有灯都是关着的。证明：等到大家来上班后，总能用有限次的开关，最终把所有办公室的灯都打开。
证明：对 n 施归纳。只有一间办公室时，结论显然成立。下面假设我们已经有办法让任意 n-1 个办公室的灯全部打开。如果把其中某 n-1 个办公室的灯全打开后，发现剩下的那个办公室的灯正好也亮了，问题就解决了。否则，我们就相当于有办法同时改变任意 n-1 个办公室的电灯状态（并且不对剩下的那个办公室造成影响）。
考虑这样的操作：先改变除了办公室 A 以外的所有办公室的电灯状态，再改变除办公室 B 以外的所有办公室的电灯状态。这样下来的结果就是，只有办公室 A 、 B 的电灯状态真的被改变了，其它办公室的电灯状态又都变了回去。也就是说，我们可以同时改变任意两个办公室的电灯状态了（并且不影响其它办公室）。
如果 n 是偶数，两个两个地把它们的灯打开，问题直接就解决了。麻烦的就是，如果 n 是奇数的话，该怎么办呢？要是有一个办公室正好有偶数个相关的办公室就好了，这样的话就可以先拉下它的开关，剩下灯没亮的办公室正好偶数个，问题也就解决了。下面我们就证明，如果 n 是奇数，那么一定存在一个办公室，它正好有偶数个相关办公室。
注意到，把所有办公室的相关办公室数加起来，结果一定是一个偶数（因为每个相关关系都被算了两次）。但是，我们一共有奇数个办公室，如果它们各自的相关办公室数目都是奇数，加起来也还是个奇数。因此，至少有一间办公室，它有偶数个相关办公室。这就完成了整个证明过程的最后一环。
sf?
这个有意思
第一步不理解。为什么可以“假设我们已经有办法让任意 n-1 个办公室的灯全部打开”呢？
楼上，这不是标准的数学归纳法吗？
其实证明还好理解，困难的是如何针对给定的相关性初始条件，算出具体解法。
归纳法啊，真难想到
但是这道题不一样啊，n=1成立不能说明n-1成立啊
其实最后一个问题的证明思路就是图论里面的握手定理。。。
额…归纳的…
这个其实比较简单吧。方法都是常见的方法。
但是确实是好题。把趣题常见的方法综合到了一起。
这个是加拿大全国数学竞赛某年的题目（加拿大这儿数学竞赛比较水）
哦…很有意思…
挺巧妙的证明
话说回来，只要先证明对小于等于n-1时都成立，那么随便拉一盏灯不都可以把n盏灯转换为已经证明过的情况了吗？
我错了，没亮的灯还可以和亮了的关联啊。
证的真精采,佩服
“考虑这样的操作：先改变除了办公室 A 以外的所有办公室的电灯状态”，这个不一定能做到吧？假设只有两盏灯，并且两盏灯是关联的
“如果把其中某 n-1 个办公室的灯全打开后，发现剩下的那个办公室的灯正好也亮了，问题就解决了。否则，我们就相当于有办法同时改变任意 n-1 个办公室的电灯状态（并且不对剩下的那个办公室造成影响）。”是怎么样从某n-1个推广到任意n-1个的啊?
这个归纳很牛！！
厉害
第一步我看不出来是数学归纳法，可以把它写的再细一点么。。
厉害！
可不可以利用關係對稱的條件,
証明所有辦公室可分類成互不相交的Class
然後直接証明?
看來我弄錯了..忽略我樓上的說話吧
牛
对于这个拉灯问题，Matrix67的证明方法有漏洞。
我用以下的方式简单的说明以下。
如果修改原题的2个地方：
1.把业务关系必须对称，改为“不一定对称”。
2.添加一个条件：所有房间中至少有一个房间与偶然个房间关联或与所有房间关联。
然后再看原题的证法（以下复制Matrix67的原文）：
【证明：对 n 施归纳。只有一间办公室时，结论显然成立。下面假设我们已经有办法让任意 n-1 个办公室的灯全部打开。如果把其中某 n-1 个办公室的灯全打开后，发现剩下的那个办公室的灯正好也亮了，问题就解决了。否则，我们就相当于有办法同时改变任意 n-1 个办公室的电灯状态（并且不对剩下的那个办公室造成影响）。
考虑这样的操作：先改变除了办公室 A 以外的所有办公室的电灯状态，再改变除办公室 B 以外的所有办公室的电灯状态。这样下来的结果就是，只有办公室 A 、 B 的电灯状态真的被改变了，其它办公室的电灯状态又都变了回去。也就是说，我们可以同时改变任意两个办公室的电灯状态了（并且不影响其它办公室）。
如果 n 是偶数，两个两个地把它们的灯打开，问题直接就解决了。麻烦的就是，如果 n 是奇数的话，该怎么办呢？要是有一个办公室正好有偶数个相关的办公室就好了，这样的话就可以先拉下它的开关，剩下灯没亮的办公室正好偶数个，问题也就解决了。】
=====
可以发现，原题的证法同样能够证明“修改后的题目”是成立的。
但问题就在这里，“修改后的题目”其实并不成立。
简单的反例：
ABC三个房间，A房间关联AC,B房间关联BC C房间关联CA。
17楼注意这段文字：【如果把其中某 n-1 个办公室的灯全打开后，发现剩下的那个办公室的灯正好也亮了，问题就解决了。】
26楼，修改后的题目不能证明【有一个办公室正好有偶数个相关的办公室】
证的真精采,佩服
从偶数 n 变为 n-2 的步骤，不能保证解 n-2 的方法不再次影响 A、B 的电灯状态。
反例： 4间办公室关系成一个环形
Ａ─Ｂ
│ │
Ｄ─Ｃ
拉 C、D 的开关，点亮 A、B 而其他不变。
剩下 C-D 的解决方法是拉 C、D 的其中一个开关，但是会影响 A 或 B的电灯状态。
——–
既然有解的 n-1 加上 n 后，可能是 n 直接点亮（n-1 的解影响 n），也可能 n 不亮（不影响）；那么怎么证明随意去掉 A 或 B 后 n-1 的解不影响 A 或 B？
即“我们就相当于有办法同时改变任意 n-1 个办公室的电灯状态（并且不对剩下的那个办公室造成影响）”这个结论没有证明。
一般归纳法中，所有的 n-1 都是等价的；而这里因为图的差异，去掉 A 的 n-1 和去掉 B 的 n-1 不等价。
除非你能证明：对任意 n 的关系图，去掉任意一个 A 的 n-1，总存在一个解，不会影响 A 的电灯状态。