题目
假设你面前有一组灯泡，每个灯泡由一些开关控制。
每个开关会翻转某个子集内所有灯泡的状态——即把该子集中灭掉的灯泡点亮，点亮的灭掉。
已知对于任意非空的灯泡集合，总存在一个开关，它翻转了该集合中的奇数个灯泡（当然，它也可能同时翻转集合之外的灯泡）。
证明：无论灯泡的初始状态如何，你总能用这些开关把所有灯泡关掉。
分析
设灯泡数为\(n\)。开关按下的顺序无关紧要——只需关心每个开关被按了奇数次还是偶数次。
\(n=1\)时结论显然成立。假设\(n\ge 2\)且结论对\(n-1\)个灯泡成立（IHOP）1。
对每个灯泡\(i\)，考虑去掉\(i\)后的系统。由归纳假设，存在一组开关\(S_i\)，它们能关掉除\(i\)之外的所有灯泡。 若某个\(S_i\)同时也关掉了\(i\)，则已得证。故下设所有\(S_i\)均不能关掉\(i\)。
任取两个不同的灯泡\(i\)和\(j\)，依次执行\(S_i\)和\(S_j\)。结果：
- 除\(i\)和\(j\)外，每个原本灭着的灯泡保持灭，每个原本亮着的灯泡被翻转为灭再翻转为亮，回到原状态；
- \(i\)和\(j\)各被翻转一次。
因此，若\(i\)和\(j\)都亮着，则\(S_i\cup S_j\)可将它们同时关掉而不影响其他灯泡。 于是，若有偶数个灯泡亮着，可以两两配对将其全部关掉。
若有奇数个灯泡亮着，则利用已知条件——取全体灯泡为那个“非空集合”——找到一个翻转了奇数个灯泡的开关，将其按下，亮着的灯泡数即变为偶数，再用上述配对操作即可全部关掉。QED。
注意：上面的证明看起来似乎只在一种特殊情况下用到了已知条件（即取全体灯泡为那个集合），难道这就够了？不对，如果条件只对“全体灯泡”成立，对两个灯泡且只有一个翻转一个灯泡的开关的情形就不成立——无法关掉另一个灯泡。
问题的关键在于：归纳法需要一个能“向下传递”的条件，即在去掉一个灯泡后该条件仍然成立，否则无法应用归纳假设。事实上，已知条件确实需要对所有非空子集都成立。如果存在某个灯泡集合\(S\)，没有开关能翻转其中的奇数个灯泡，那么一开始只点亮\(S\)中的一个灯泡，我们就无法把它关掉。
-
Induction HyPOthesis，即归纳假设。 ↩