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
建议继续学习:
- 趣题:2n位平衡01串平均有多少个平衡前缀? (阅读:2517)
- UyHiP趣题:限制最苛刻的选票统计程序 (阅读:2052)
- UyHiP趣题:如果每个人都随大流,结果会怎样? (阅读:1609)
- UyHiP趣题:按照盒子的三边长之和来计费有没有漏洞? (阅读:1621)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:Matrix67 来源: Matrix67: My Blog
- 标签: UyHiP 拉灯游戏
- 发布时间:2011-06-22 00:17:45
- [68] Twitter/微博客的学习摘要
- [64] find命令的一点注意事项
- [63] IOS安全–浅谈关于IOS加固的几种方法
- [62] android 开发入门
- [61] 如何拿下简短的域名
- [61] Go Reflect 性能
- [60] 流程管理与用户研究
- [59] Oracle MTS模式下 进程地址与会话信
- [57] 图书馆的世界纪录
- [57] 读书笔记-壹百度:百度十年千倍的29条法则