珍珠湾ART

标题: 移动棋子 [打印本页]

作者: constant 时间: 2006-4-28 17:52
标题: 移动棋子

难度：+++www.ddhw.com

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

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

作者: 新用户 时间: 2006-4-28 21:44
标题: 想了半天，好像觉得N=4不可能 [:-D]

N=3 ●●●○○○

第一次：

●●○●○○

第二次

●○●●○○

第三次

●○●○●○

N=4 ●●●●○○○○

我猜第一次必须为：●●●○●○○○

还有三次，好像无论如何都不行？

作者: constant 时间: 2006-4-28 23:29
标题: 移动是指在一条直线上平移，不能把两个棋子颠倒过来。

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

作者: sean9991 时间: 2006-4-29 01:37
标题: 回复：移动棋子

XXXXOOOO

X--XOOOOXX

XOOX--OOXX

XOOXOXO--X

--OXOXOXOX

作者: 有空想想 时间: 2006-4-29 06:44
标题: 胡乱想想

考虑棋子间距足够大，即交换棋子等同于移动一枚棋子。考虑白棋子坐标为 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）。

本贴由[有空想想]最后编辑于：2006-4-28 22:44:49

作者: huxlnn 时间: 2006-4-29 18:25
标题: 回复：移动棋子

●●●●○○○○ 0

●●●○○●○○ 1

○○●●●○○● 2

○●●○○●○● 3

○●○●○●○● 4

●●●●○○○○ 0

●●●○●○○○ 1

●●○○●○●○ 2

●○●○●○●○ 3

www.ddhw.com

本贴由[huxlnn]最后编辑于：2006-4-29 10:37:21

作者: 有空想想 时间: 2006-4-29 21:10
标题: 每次只能移动相邻两子, 每次只能移动相邻[两子]...（图）

如果是这样的话。。。。

我们一共有n 对。从中间挪起，挪 n－1 次。

www.ddhw.com

本贴由[有空想想]最后编辑于：2006-4-29 13:33:13

作者: 新用户 时间: 2006-4-29 22:23
标题: 啊，这个解法有创意，高手！看来，不需要N次？N-1次即可？

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

作者: constant 时间: 2006-4-29 22:50
标题: 不可以。移动时只能向有空格的地方移。移出来的空格要用别处移来的棋子填上。

相邻两子是相邻没有空格的两子。唉，真累。

sean9991已经解了N=4。

作者: huxlnn 时间: 2006-4-30 04:32
标题: 回复：回复：移动棋子

●●●●●●○○○○○○ 0

●●●●●○○○○●○○ 1 最后一黑和第一白移至最后一白之前

○○●●●●●○○○○● 2 最后两白移至最前

○●●●●○○○○●○● 3 前面一黑一白移至最后

○●○○●●●○○●○● 4 中间两白移至前部两黑前

○●○●●○○●○●○● 5 前部两白两黑中取中间○●移至最后

○●○●○●○●○●○● 6 中部两黑两白取●○移至最后○中间●

对于任意的n,这种操作次序都能在N次把顺序调整到规定的次序

作者: 有空想想 时间: 2006-4-30 05:00
标题: 抱歉

抱歉

作者: constant 时间: 2006-4-30 22:01
标题: 都不对。见下面说明

都不对。见下面说明

作者: huxlnn 时间: 2006-5-1 07:08
标题: 回复：都不对。见下面说明

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

作者: tan6y 时间: 2006-5-1 10:59
标题: 回复：移动棋子

四个黑色围棋子和四个白色围棋子排列如下：

●●●●○○○○
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次已经可以了.

作者: constant 时间: 2006-5-1 19:39
标题: 怎么没人能看懂题[:X]？算了，这题收回了。

怎么没人能看懂题

？算了，这题收回了。

作者: 新用户 时间: 2006-5-2 00:19
标题: haha,,其实我觉得

其实我觉得sean9991也不符合要求，因为最终还是有空格出现

回过头来想一想，我觉得有空想想® 的解答很妙，很容易理解。

所以，如果题目修改成 “.... 如何移动N-1次将其变成黑白相间的排列”，而没有必须填满空格的限定。也是一道好题呀！

作者: sean9991 时间: 2006-5-2 00:39
标题: 回复：haha,,其实我觉得

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.

作者: 有空想想 时间: 2006-5-2 17:07
标题: 我们有多少空间可以利用？

原题并没有说明有多少空间可以利用。那么这样，我们就可以假设有无穷（一维）空间可以利用。

如果按 sean9991 的解法，我们需要 2n+2 空间。可原题并没有说只能用 2n+2 空间。

那么一般我们会理解要么有 2N （一维）空间，那么我们根本做不到，如我前边证明的；

要么有无穷（一维）空间（我们只需要 N^2＋N 空间就够了），那样我们就只需要 N－1 步。

有朋友提到 shift，但严格讲 shift 也是对子粒的移动，不应不算在移动步数之内。如 tan6y 朋友解的，他的第一步，我就不知道是算移动两子还是移动五子。原题说“每次只能移动相邻两子”，被 shift 的子显然不是 “相邻两子”。

如果谁有只用 2N 空间（N>3），不 shift 子粒的 N 步解法，快贴上来呀。我把我的钱全给他。

作者: ob 时间: 2006-5-2 23:44
标题: I did this game before. It's very interesting[:-M]

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 时间: 2006-5-3 08:35
标题: 回复：移动棋子

●●●●○○○○

○○●●●●○ ○

○○●● ○●●○

○ ●○●○●●○

○●○●○●○●

欢迎光临珍珠湾ART (http://66.160.158.134/)