移动棋子

constant

难度：+++www.ddhw.com

四个黑色围棋子和四个白色围棋子排列如下：
●●●●○○○○
如果每次只能移动相邻两子，如何移动四次将其变成黑白相间的排列：
○●○●○●○●

更一般地，N个黑子和N个白子（N>=3）：
●●●…●○○○…○
如何移动N次将其变成黑白相间的排列
○●○●○●…○●

www.ddhw.com

 

新用户

N=3  ●●●○○○ 第一次： ●●○●○○   第二次 ●○●●○○  www.ddhw.com 第三次 ●○●○●○     N=4   ●●●●○○○○   我猜第一次必须为：●●●○●○○○   还有三次，好像无论如何都不行？

constant

  移动是指在一条直线上平移，不能把两个棋子颠倒过来。

sean9991

XXXXOOOO X--XOOOOXX XOOX--OOXX XOOXOXO--X --OXOXOXOX www.ddhw.com

有空想想

考虑棋子间距足够大，即交换棋子等同于移动一枚棋子。考虑白棋子坐标为 1，2，3，4，如图 x x x x o o o o            1 2 3 4 黑棋子均在坐标O点（因为我们考虑相对位置）。 那么一枚黑棋子将移动 3，一枚移动 2，一枚移动 1，一枚不移动。总共 6 步。   一般说， 两枚黑棋子, 2－1＝1： 1＝1 三枚黑棋子, 3－1＝2： 1＋2＝3 四枚黑棋子, 4－1＝3： 1＋2＋3＝6 . . . n－1：     1＋2＋...＋（n －1）＝n*（n－1）/ 2 似乎是二项式（polynomial）。   www.ddhw.com     本贴由[有空想想]最后编辑于：2006-4-28 22:44:49

huxlnn

●●●●○○○○      0 ●●●○○●○○      1 ○○●●●○○●      2 ○●●○○●○●      3www.ddhw.com ○●○●○●○●      4   ●●●●○○○○      0 ●●●○●○○○      1 ●●○○●○●○      2 ●○●○●○●○      3     www.ddhw.com     本贴由[huxlnn]最后编辑于：2006-4-29 10:37:21

有空想想

如果是这样的话。。。。www.ddhw.com   我们一共有n 对。从中间挪起，挪 n－1 次。 www.ddhw.com     本贴由[有空想想]最后编辑于：2006-4-29 13:33:13

新用户

  啊，这个解法有创意，高手！看来，不需要N次？N-1次即可？

constant

相邻两子是相邻没有空格的两子。唉，真累。   sean9991已经解了N=4。

huxlnn

●●●●●●○○○○○○   0 ●●●●●○○○○●○○   1        最后一黑和第一白移至最后一白之前www.ddhw.com ○○●●●●●○○○○●   2        最后两白移至最前 ○●●●●○○○○●○●   3        前面一黑一白移至最后 ○●○○●●●○○●○●   4        中间两白移至前部两黑前 ○●○●●○○●○●○●   5        前部两白两黑中取中间○●移至最后www.ddhw.com ○●○●○●○●○●○●   6        中部两黑两白取●○移至最后○中间●   对于任意的n,这种操作次序都能在N次把顺序调整到规定的次序

有空想想

  抱歉

constant

  都不对。见下面说明

huxlnn

上面的移动已经是把相邻两子作为一个单元来处理了 www.ddhw.com

tan6y

四个黑色围棋子和四个白色围棋子排列如下： ●●●●○○○○ 1 2 3 4 5 6 7 8 ================================================ 解答: 第1次移动45 结果如下 ●●●○○○●○ 1 2 3 6 7 8 4 5 第2次移动36 结果如下 ●●○○●○●○ 1 2 7 8 4 5 3 6 第3次移动27 结果如下 ●○●○●○●○ 1 8 4 5 3 6 2 7 移动3次已经可以了. www.ddhw.com

constant

  怎么没人能看懂题 ？算了，这题收回了。

新用户

其实我觉得sean9991也不符合要求，因为最终还是有空格出现 回过头来想一想，我觉得有空想想® 的解答很妙，很容易理解。   所以，如果题目修改成 “.... 如何移动N-1次将其变成黑白相间的排列”，而没有必须填满空格的限定。也是一道好题呀！ www.ddhw.com

sean9991

www.ddhw.com It just need to be a row of alternating stones.  Shifting couple space is OK. Here is solution for more stones. XXXXXOOOOO X--XXOOOOOXX XOOXXOO--OXX XOOX--OXOOXX XOOXOXOXO--X --OXOXOXOXOX   XXXXXXOOOOOO X--XXXOOOOOOXX XOOXXXO--OOOXX XOO--XOXXOOOXX XOOXOXOX--OOXX XOOXOXOXOXO--X --OXOXOXOXOXOX   Basically, the first step will always be moving the second and third stones to the end.  Then move proper 2 whites left to fill the empty spots.  So on... The following two patterns are important in getting the result. XOOX, especially useful to solve the first 4 positions. OOXX (or XXOO), replace the middle two with the opposite pattern to get the alternating results.   The result will always be shifting two spots to the right. www.ddhw.com

有空想想

原题并没有说明有多少空间可以利用。那么这样，我们就可以假设有无穷（一维）空间可以利用。 如果按 sean9991 的解法，我们需要 2n+2 空间。可原题并没有说只能用 2n+2 空间。   那么一般我们会理解要么有 2N （一维）空间，那么我们根本做不到，如我前边证明的； 要么有无穷（一维）空间（我们只需要 N^2＋N 空间就够了），那样我们就只需要 N－1 步。  www.ddhw.com 有朋友提到 shift，但严格讲 shift 也是对子粒的移动，不应不算在移动步数之内。如 tan6y 朋友解的，他的第一步，我就不知道是算移动两子还是移动五子。原题说“每次只能移动相邻两子”，被 shift 的子显然不是 “相邻两子”。   如果谁有只用 2N 空间（N>3），不 shift 子粒的 N 步解法，快贴上来呀。我把我的钱全给他。 www.ddhw.com

ob

4 black and 4 white is not very hard. I have one question, is there a general proof for this problem? I know you can move N times to change ●●●…●○○○…○ to 黑白相间的排列 ○●○●○●…○● Is there a proof?

ob

●●●●○○○○ ○○●●●●○     ○ ○○●●     ○●●○ ○     ●○●○●●○ ○●○●○●○●   www.ddhw.com