上回写了个“继貂《华罗庚给物理学家出的一道数学题》”，却没把继貂的狗尾巴露出来。现解释如下：

(1)          关于k种颜色的情况：以搬动如下三色棋子为例，由归纳法，通解显然。(B-M stands for Dr. Bao’s method.)

Original:             BBBBGGGGRRRR

Using B-M:        BBBB_ _ RGRGRGRG

Ignore empty:      BBBBRGRGRGRG

RG:=S:           BBBBSSSS

Using B-M:        SBSBSBSB *

* 这一步每次需移动3个棋子。

这样，总共移动(k-1)N次即可。

 (2)          关于 k=2^s的情况：

Original: A_k A_{k …} A_k A_k-1 A_{k-1 …} A_{k-1 ……} A₂ A_{2 …} A₂ A₁ A_{1 …} A₁

Using B-M to A₂ A₁ first, then A₃ A_4, and so on. Then consider

B₁ = A₁A₂ , B₂ = A₃A₄ and so on.

这时，没有空格出现。因重排A₁ A₂时右移两格正好被重排A₃ A₄ 所占，等；重排B₁ B₂时右移四格正好被重排B₃ B₄ 所占；等等。

有趣的是：这时的总移动次数为

2^s-1N+2^s-2N+…+N=(2^s - 1)N=(k-1)N.

(3)          基于上述结果，我猜(k-1)N次是必要的。具体一写发现原来的证明不对。如果用逆序方法判断，只得到：1+2(x-1)≧ kN-1。这样可得：x≧kN/2。当 k>2 时，这比(k-1)N少。因此，(k-1)N次是否必要还不知道。

(4)          这个问题很容易推广到平面甚至立体的情况 (甚至n维欧氏空间)。例如：平面上有四种不同颜色的棋子各n²个，摆成正方形

                         A B

                         C D

这里小正方形A由n²个a组成，B由n² 个b组成，等等。允许每次移动2×2的方块，证明经2n²次移动可将其摆成全部由a,b,c,d组成的2×2的方块拼成的正方形。

(5)          这个问题如果能用动态演化的方式来描述应当会更有意思。它或许对生物体的演化有关。上周收到一位朋友的来信 (他是 IEEE Fellow, 南非科学院院士)，提出一个有趣的想法。我现在尚未想明白，有兴趣的朋友，可以帮我一起想一想。(信附后)

 

代展：
你在http://blog.sciencenet.cn/blog-660333-587039.html中“二傻”关于“移棋换位”的问题可以用我们在下文中的Delta  Modulation建摸描述。至少在k=2时可以。k=2时还可以推广：

有2种颜色棋子各N枚，任意排成一行。若允许每次移动相邻的2枚棋，试证，经少于N次移动，可将其排成以2种颜色为周期的一行。

我想对一般情况（any k and r)，方法上也是可行的。没有细想。

R. Gai, X. Xia and G. Chen, Complex dynamics of systems under Delta-modulated feedback, IEEE Transactions on Automatic Control, vol. 51, no. 12, 1888-1902, December 2006.

小华（路过BJ)

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

上一篇：继貂《华罗庚给物理学家出的一道数学题》
下一篇：我看“国家自然科学基金”