这是一个让我纠结许久,又不甘放弃的puzzle。在一个意志力极度薄弱的下午,对不起,我看了答案...所以,这又是一篇马后炮文章。但不是所有马后炮都一文不值。如果在讲解一个解答的时候,我们不能把思考背后的动机讲清楚,于他人和自己的价值就会小很多。每一步推理的过程,每一个构造的细节,不是无迹可寻的。我希望去揭示背后的东西。
一个解答背后包含了大量的探索。解谜高手对于如何避免无效的思考,摸清靠谱的思路,总是有一套自己的办法。遗憾的是,好些同学由于各种原因,没有公开自己的方法。例如,高斯同学,他认为数学家应该隐藏研究背后的脚手架,呈现给读者的是完整的建筑。
波利亚的《How to Solve It--A New Aspect of Mathematical Method》(中文译名《怎样解题--数学思维的新方法》)把思考的过程称为探索法。在解答问题的过程中,灵光一线的瞬间非常奇妙,多少人苦恼于它的时隐时现。又或者,我看到了一个解答。是的,它是正确的,真是巧妙啊。问题是,这是怎么想到的呢?
其实,这些貌似天外飞仙的奇思妙解也是有理可依,有迹可循。波利亚在这本造福人类的书中,对思考的方法做了很好的总结。(陶哲轩15岁时也写过一本《Solving mathematical Problems》)。也就是说,只要我们运用正确的思考方法,不畏险阻,热爱挑战,不断积累思考,终有一天,能够达到我们希望的境界。
回到正题,这个问题来自于Using your Head is Permitted网站。我是从matrix67的博客看到的。
题目摘自matrix67:
“某公司有 n 间办公室。每间办公室都有一盏灯,拉动它的开关即可改变电灯的状态。某些办公室之间存在“业务相关
的关系(这是一个对称的关系)。一个办公室可以和 0 到任意多个办公室相关。愚人节那天,有人在大家上班之前偷
偷对办公室的电灯开关做了手脚:拉动任何一个办公室的电灯开关,都会同时改变该办公室以及所有相关办公室的电
灯状态。初始时,所有灯都是关着的。证明:等到大家来上班后,总能用有限次的开关,最终把所有办公室的灯都打
开。”
解答在以上两个链接当中都有
说说我的思路:
如果把这个问题抽象出来就是一个对称的0、1矩阵,对角线都是1。
选择一些行向量相加,使得结果当中每个数字都为奇数。
例如
1 0 1
0 1 1
1 1 1
选择[1 1 1]
1 0 0
0 1 0
0 0 1
选择[1 0 0] [0 1 0] [0 0 1]
随便取几个较小的n,试验一下,都是成立的。找不到反例,看起来这个结论是对的,但是并不明显。
把条件特殊化。n=1,2,3,都是对的。
从特殊情形推广到一般情形,各位想到了什么呢?
数学归纳法
相信看到这里,很多独立思考的同学都想到了数学归纳法。接下来怎么办呢?
例如从n=3推广到4
1 0 1 0
0 1 1 0
1 1 1 1
0 0 1 1
首先想到的是,如果增加了新列以后,原先选择的向量相应的位置有奇数个1。那么就可以继续选择原先的向量。
原先选择[1 1 1],扩展以后,第4列是1。依然选择[1 1 1 1],所选的向量向加都是奇数,那么问题容易得解。
但是,新的位置在原先的位置有偶数个1怎么办呢?
例如
1 0 0 1
0 1 0 0
0 0 1 1
1 0 1 1
原先选择[1 0 0][0 1 0] [0 0 1],新的向量就是[1 0 0 1] [0 1 0 0] [0 0 1 1],第4列有偶数个1,显然是不对的。
当时的我就是卡在了这个地方。没有更好的思路。
这时候应该怎么办?翻一翻《How to Solve It》,看看有什么好的建议。
镇定一下情绪。
我们是否不该盲目地进行试探,而是要仔细地回顾这个问题,列举一下已知量、条件、结论。思考从什么地方下手,然后制定一个解题策略。(波利亚的思考法则)
结论是什么?存在一种选择方式,使得所选向量中每列的1为奇数个。所有的选择方式有2^n种,所以可能的结果也有那么多。这是一个存在性的结论,因此我们似乎无法从结论入手去逆推过程。
已知量是什么?
对于n=1, 2, 3, ..., n-2, n-1向量,结论都成立
1 0 0 1
0 1 0 0
0 0 1 1
1 0 1 1
而且n=4, n-1=3的对称矩阵不是只有(去掉红色部分)
1 0 0 1
0 1 0 0
0 0 1 1
1 0 1 1
还有
1 0 0 1
0 1 0 0
0 0 1 1
1 0 1 1 如果我们把第2列看作新加入的一列的话
因此n-1 = 3的子对称矩阵(sub sym matrix)实际上有4个。而且这4个矩阵,都符合上面的困境,否则的话只要有一个子矩阵不满足困境,结论即可证明。
而且我们知道这4个矩阵,可以组合成[单 单 单 双] [单 单 双 单] [单 双 单 单] [双 单 单 单]的向量
例如
1 0 0 1
0 1 0 0
0 0 1 1
1 0 1 1 选择1,2, 3向量可以得到新的[1 1 1 2]向量
1 0 0 1
0 1 0 0
0 0 1 1
1 0 1 1 选择4向量得到新的[1 0 1 1]
哈,看到这里,是否有了一些思路了呢?因为我们的已知量增加了,而且这些新的的东西都有很好的特征:
这些新的向量等价于[1 1 ... 0] [1 1 ... 0 1] ...[0 1 ... 1],即n个无重复的向量,其中一列是0,其他都是1。
然后很自然地想到组合这些向量。
如果n=2,4,6,8..., 直接把这些向量相加,就可以得到等价于[1 1 ... 1]。这不就是我们的结论吗。
看来n是偶数的情形,我们已经有了一种构造性的方法,来证明我们的结论了。
如果能搞到这一步,之前一筹莫展的心情已经一扫而空,相信各位都能体会到满满的信心了。有前途啊!
下面就是设法搞定n是奇数的情形了。
一般性问题不好想的时候,从特殊情形考虑。(波利亚的思考法则)
考虑n=5 [1 1 1 1 0] [1 1 1 0 1][ [1 1 0 1 1] [1 0 1 1 1] [0 1 1 1 1]
如果选择偶数个向量,原先全是1的位置变成了0,原先是有0的位置变成了1。例如选[1 1 1 1 0] [1 1 1 0 1],形成[0 0 0 1 1]
如果选奇数个,原先全是1的位置还是1,原先有0的位置变成了0。例如选[1 1 1 1 0] [1 1 1 0 1][ [1 1 0 1 1],得到[1 1 0 0 0]
然后对比下,发现都有奇数个0,偶数个1。
猜想1,无论我们如何组合新的向量,得到的都是奇数个0,偶数个1
例如选[1 1 1 0 1]+[1 0 1 1 1]=[0 1 0 1 0],再试验一下,也是这样。这个猜想的可信度已经比较高了。而且,这个结论是比较容易证明的。
于是我们通过组合新的向量,我们又获得了新的向量在n为奇数的情形下,更一般性的结论。
真的是越来越有希望了!
新的向量好像已经被挖掘到极限了,老的向量是否还有开发的空间呢?
如果我们在n为奇数的对称矩阵中,能找到一个向量,它有奇数个1,偶数个0,就能和新的向量形成互补了
例如
1 0 1 0 1
0 1 1 0 0
1 1 1 0 1
0 0 0 1 1
1 0 1 1 1 中第1行就是这样的向量。
好的,能否证明这个
猜想2,在n为奇数的对称矩阵中,能找到一个向量,它有奇数个1,偶数个0
这个结论也是比较容易证明的,运用反证法。如果我们不能很好地从正面证实它,就尝试从反面找到矛盾。(波利亚的思考法则)
首先,由于矩阵的对称性,他的对角线两边加起来有偶数个1,它的对角线有n个1,所以总共有奇数个1。
如果所有地向量都有偶数个1,那么1的个数加起来就是偶数,与已知矛盾。
证明了猜想2,那么整个命题得到证明。
OK,I can die in peace。至少,在今晚。
uyhip 趣题 拉灯问题总有解吗?,布布扣,bubuko.com
原文:http://blog.csdn.net/kingoverthecloud/article/details/36063601