【科网大学（2）】：华罗庚给物理学家出的一道智力题

 

话说上回，在二傻的博文中： 《怀念【郭汉英】先生》 精选

提到了下面这段故事：

记得大约是1992年夏天，在南开大学举办了一场“量子群国际会议”。在会议期间，郭老师给我们出了一道智力题，说是华罗庚老先生在1970年给“相对论批判小组”（其实是理论物理所的前身）的年轻人出的。郭老师认为这道智力题与当时国际上正热门的“辫子群”也许会有一些深刻的关联。。。

题目是这样的：有N个黑棋子和N个白棋子，挨个摆成一条直线，黑子全部在一边，而白子全部在另一边。如果每次移动一对互相挨着的棋子并摆放到直线上（这对棋子移动时不能颠倒），如何在N次移动之后将全部棋子变成黑白相间的次序？

为了这道题，我和戴建辉（昵称：阿呆）两人，足足忙了三天三夜！终于找到了通解！在常哲的监督下，我们将一付围棋顺着地面一溜儿摆上，在规定的N次之后，果然实现了黑白相间！大家赶紧向郭老师汇报战果，郭老师笑笑：当时他只用了一个下午就解决了华老的这道智力题。。。

应大家的强烈要求，二傻就在这里将答案解秘了啊？哈哈！

 

首先，要解决这类问题，没有捷径可走，必须从最简单的特例开始探索。。。

于是，我们开始试2个黑白子的情况，这个、这个。。。无解！太简单啦！

然后，我们开始试3个黑白子（奇数）的情况（费时3分钟）：

3

0

○

○

○

●

●

●

1

○

●

●

●

○

○

2

○

●

●

○

●

○

3

●

○

●

○

●

○

 

然后，我们开始试4个黑白子（偶数）的情况（费时15分钟）：

 

4

0

○

○

○

○

●

●

●

●

1

○

○

●

●

●

●

○

○

2

○

●

●

○

●

●

○

○

3

○

●

●

○

●

○

●

○

4

●

○

●

○

●

○

●

○

 

没看出有啥规律？那，我们开始试5个黑白子的情况（费时60分钟）：

 

5

0

○

○

○

○

○

●

●

●

●

●

1

○

○

○

●

●

●

●

●

○

○

2

○

●

●

○

○

●

●

●

○

○

3

○

●

●

○

●

○

●

●

○

○

4

○

●

●

○

●

○

●

○

●

○

5

●

○

●

○

●

○

●

○

●

○

 

我们发现，5个黑白子的情况与3个黑白子的情况，虽然都是奇数情况，它们却没有类似的操作规律！

真麻烦嘢！那，我们再继续试试6个黑白子的情况（费时3小时）：

 

6

0

○

○

○

○

○

○

●

●

●

●

●

●

1

○

○

○

○

●

●

●

●

●

●

○

○

2

○

●

●

○

○

○

●

●

●

●

○

○

3

○

●

●

○

●

○

○

●

●

●

○

○

4

○

●

●

○

●

○

●

○

●

●

○

○

5

○

●

●

○

●

○

●

○

●

○

●

○

6

●

○

●

○

●

○

●

○

●

○

●

○

 

到此，我们再分析一下，可以发现：除了3的情况特殊之外，其它4、5、6的情况都有如下共性：

（1）    第一步都是一样的！

（2）    最后一步也是一样的！

（3）    最后结果都是向右整体平移2格！

 

但是，最最关键的第二步，到底应该挪动哪两个黑子，却没有规律可循。。。。。。

真麻烦嘢！那，我们只好再继续试试7个黑白子的情况（费时6小时）：

 

7

0

○

○

○

○

○

○

○

●

●

●

●

●

●

●

1

○

○

○

○

○

●

●

●

●

●

●

●

○

○

2

○

●

●

○

○

○

○

●

●

●

●

●

○

○

3

○

●

●

○

○

●

●

●

○

○

●

●

○

○

4

○

●

●

○

●

○

○

●

●

○

●

●

○

○

5

○

●

●

○

●

○

●

○

●

○

●

●

○

○

6

○

●

●

○

●

○

●

○

●

○

●

○

●

○

7

●

○

●

○

●

○

●

○

●

○

●

○

●

○

 

哎呀！最最关键的第二步，到底应该挪动哪两个黑子，还是没有规律可循。。。。。。

真麻烦嘢！那，我们只好再继续试试8个黑白子的情况（费时18小时）：

 

8

0

○

○

○

○

○

○

○

○

●

●

●

●

●

●

●

●

1

○

○

○

○

○

○

●

●

●

●

●

●

●

●

○

○

2

○

●

●

○

○

○

○

○

●

●

●

●

●

●

○

○

3

○

●

●

○

○

○

●

●

●

●

○

○

●

●

○

○

4

○

●

●

○

○

●

●

○

●

●

○

○

●

●

○

○

5

○

●

●

○

○

●

●

○

●

○

●

○

●

●

○

○

6

○

●

●

○

●

○

●

○

●

○

●

○

●

●

○

○

7

○

●

●

○

●

○

●

○

●

○

●

○

●

○

●

○

8

●

○

●

○

●

○

●

○

●

○

●

○

●

○

●

○

 

哎呀！最最关键的第二步，到底应该挪动哪两个黑子，还是没有规律可循。。。。。。

真麻烦嘢！

那，我们再继续试试9个黑白子的情况？？？

 

阿呆和阿瓜

。。。

这时候，阿呆突然冒出灵光：

--- 我们总是这么试，可能很难找到通解。。。也许应该观察系统中那些【不动点】，

--- 等找到所有【不动点】位置的规律之后，也许剩下的就好办了？

 

找【不动点】？嘢！这个二傻是强项！立马发现以下规律：

（1）3个子的情况，由于有太多异常，肯定是特例。

（2）4个子的情况，不动点是【白1】&【黑3】

（3）5个子的情况，不动点是【白2】&【黑2】

（4）6个子的情况，不动点是【白1】&【黑1】【黑5】

（5）7个子的情况，不动点是【白4】&【黑2】【黑6】

（6）8个子的情况，不动点是【白1】【白5】&【黑3】【黑7】

 

看着这些规律，看着看着。。。惚兮恍兮、恍兮惚兮，二傻脑袋突然大冒傻气！

原来真是有规律的！

但是规律不是按照奇数、偶数（【模2】）来分类的，而是按照【模4】来分类的！

这就是说：

--- 8个子的情况与4个子的情况是一类的！

--- 9个子的情况与5个子的情况是一类的！

。。。。。。

 

而且，各【不动点】也是按照【模4】的规律一直排下去的。。。

比如，我们可以猜到：

--- 对于9个子的情况，可以按照5个子的规律，其不动点应该是【白2】【白6】&【黑2】【黑6】。。。

 

哈哈哈！哈哈哈哈！

既然已经发现了这么多【不动点】，剩下的允许移动的成对的东东就很有限了。。。

其规律就很好找了。。。嘢！

 

当初和阿呆整出通解之后，二傻很是得意！用密码将操作步骤记录在一个崭新的笔记本上，

美其名曰【南谊密宗】！（因为当时我们是在南开大学的谊园里找到通解的）。。。

可惜，后来，这本密宗被二傻弄丢了！通解也忘得一干二净了!

 

一晃十几年过去，去年在郭先生追悼会期间，又见到阿呆，

二傻问他是否还记得郭先生给的那道华罗庚的黑白子问题的解法？

他大眼一瞪：啊？忘记了！好像是【模4】和【不动点】规律，云云。。。

 

今年，在写郭老纪念文章的时候，二傻又想起这道题，下决心非得把【南谊密宗】重新找回来不可！

于是求助著名的【鬼门派】高手（鬼王、想尔、无维等），请他们用计算机程序把4、5、6、7、8、9、10、11个子的低阶情况帮二傻整出来，二傻就能重新发现通解！

二傻还发誓答应与他们分享“知识产权”。。。。。。

 

结果，结果。。。【鬼门派】在网上竟帮二傻找到了一个高人：【姑苏寒士】！

按照【姑苏寒士】自己的说法，他也是在1970年听到华罗庚的这道题目，当时他还在蹲牛棚呢。。。

二傻估计这位【姑苏寒士】现在也是理论物理学界的老高手吧？到底是谁呢？

在网上看到他给出的极其简洁的证明，二傻觉得自己的【南谊密宗】立马失去存在的价值！

真郁闷焉！所谓“天外有天、人外有人”也！

【姑苏寒士】说了：他的证明可以自由传播，但是不能用于算命牟利。。。

于是，二傻决定在【科网大学】给大家讲讲！只是不要用于骗钱哦？嘿嘿！

 

根据4、5、6、7子特例的结果分析，我们知道，他们是有解的；

而且，最终结果都是“系统整体最终向右平移2个空格”。

 

现在我们开始运用数学归纳法入下：

 

【假设】：当N=Ｋ时，系统“有解”（指在Ｋ次移动之后完成从初始状态到最终状态的转化），而且最终结果是“系统整体都是最终向右平移2个空格”（这个假设至少对4、5、6、7子的特例是正确的），参看以下蓝色图示，假设黑白子各为Ｋ个：

 

初始状态：○○○○○○●●●●●●

中间状态： 。。。。。。。。。。。。

最终状态：    ●○●○●○●○●○●○

 

则我们可以证明：在Ｎ＝Ｋ＋４的情况下，系统也一定“有解”。

 

证明过程如下：

【１】初始态：○○○○○○○○○○●●●●●●●●●●

【２】第一步：○　　○○○○○○○●●●●●●●●●●○○

【３】第二步：○●●○○○○○○○●●●●●●　　●●○○

【４】然后大家注意中间蓝色部分，根据假设，可以用Ｋ步完成转变：

○●●○　　●○●○●○●○●○●○●●○○　　

【５】倒一步：○●●○●○●○●○●○●○●○●○●　　○

【６】最终态：　　●○●○●○●○●○●○●○●○●○●○

 

于是，在Ｋ＋４＝Ｎ步时，确实完成了系统的转变！

而且，最终结果也还是“系统整体最终向右平移2个空格”！

所以，以上操作，可以对所有自然数成立！

（证毕！）

 

。。。。。。

。。。

。

 

【后记】

 

大家千万不要浅尝辄止哦？

--- 这可是华罗庚给物理学家们出的题目也！

其深刻含义或其在物理学的潜在应用价值，正如【四色定理】一样，目前尚未得到充分的认识。。。

 

不过，考虑到这种过程其实是一种双线【辫子】的编织过程，其中的操作元，既不是对易的，也不是反对易的。。。其实，它是一种特殊的【辫子群】结构！二傻喜欢称之为【天狼星辫子群】。

 

直觉上，【天狼星辫子群】似乎可以有以下几方面的物理应用前景：

--- 【有序系统向无序系统的过渡】（比如：黑白墨水扩散模型）的直白演示。。。

--- 【离散系统最小作用量原理】（统计力学）的一维演示。。。

--- 【铁磁性物质ISING模型的解析解钥匙】。。。

--- 【超导原理的某种可能机制】。。。

--- 【DNA双螺旋结构的最优解构法】。。。

 

二傻老了！不中用了！不像你们，还年轻！

希望【科网大学】的同学们，能够高举【天狼星辫子群】的旗帜，奋勇前进！

。。。

。。

。

【补记】

清华大学物理教授【文克玲】先生对该问题亦是早有研究，

还借用量子力学中的【量子数】概念，非常简洁地证明了：

“N阶【移棋换位】问题，最少需要N步才能实现”

其证明过程，实在值得在此大力宣传！

文先生的证明过程如下：

定义：相邻两个棋子颜色不同，称为一个“反序”。

显然，初始状态有一个反序，最终状态有（2N-1）个反序。

目标：n次移动需要增加（2N-2）个反序。

而第一次移动，至多增加一个反序；以后的每次移动，至多增加两个反序。

所以，n次移动至多增加（2n-1）个反序。

因为要求：2n-1>=2N-2

所以必须：n>=N-1/2

而且由于: n是正整数

于是结果：n(minimum)=N。 （证毕）

如此一来，华老的问题就全部而且完备地得到解决了！

【1】N阶【移棋换位】问题，N步一定可以解决！（而且可以给出具体算法）

【2】N阶【移棋换位】问题，最少必须N步才能解决。

。。。。。。

。。。

。

【参考文献】：

《辫子群,纽结理论及统计力学》（杨振宁、葛墨林著）

 

转载本文请联系原作者获取授权，同时请注明本文来自鲍得海科学网博客。
链接地址：https://blog.sciencenet.cn/blog-5190-585336.html

上一篇：【胡言乱语】上帝可以吃肉，二傻为何不可以吃肉？
下一篇：【微博】大家知道“陈辉”哪里去了吗？