Author Topic: 移动棋子  (Read 20930 times)

Anonymous

  • Guest
移动棋子
« on: 十二月 07, 2004, 08:34:32 am »
四个黑色围棋子(B)和四个白色围棋子(W)排列如下:
BBBBWWWW
如果每次只能移动相邻两子,如何移动四次将其变成黑白相间的排列:
BWBWBWBW

八子不太难,有意思的是N个黑子和N个白子:
BBB。。。BWWW。。。W
如何移动N次将其变成黑白相间的排列
BWBWBW。。。BW

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
移动棋子
« Reply #1 on: 十二月 07, 2004, 09:42:34 am »
This is a very fun game to play. I often give this problem to people in a party (when there's no other interesting event going on). The most attractive one is when N=3. It is interesting and yet simple enough for a party.  N=4 is a little hard for general public, and people lost interest after several try.

As for the general case, I think there's a theorem which shows if you can do N=4, you can do any N.  I'll leave this problem for other people since I've seen this one before.

Wondering

  • Guest
移动棋子
« Reply #2 on: 十二月 07, 2004, 10:20:28 am »
Please explain: "每次只能移动相邻两子".

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
移动棋子
« Reply #3 on: 十二月 07, 2004, 10:33:38 am »
By moving two neighboring pieces, it means you have to move two pieces that is next to each other. Can't move two non-connected together. Here's a case of N=3, you will see what he meant by moving two neighboring together.


●●●●●● ------ move the first and second together to the right, you have
●●●●● ------ move the fourth and fifth together to the right, you have
●●●●●--- move the first and second together to the right, you have
● ------ done.

I spent 10 minutes on this post just want to see how the color would work out, so that we can have future problems posted nicely.

zzzzzz

  • Guest
移动棋子
« Reply #4 on: 十二月 07, 2004, 10:45:51 am »
I'm not sure if I understood this question correctly, the answer seems simple (that's why I think I might have missed something):

Start with BBB..BWW..W, nB's and nW's.

Move the middle 2 to the far right, now you have
BB..BWW..WBW.

Move the middle 2 to the far right again, you get

BB..BWW..WBWBW.

Repeat this n-1 times, you end up with BWBWBW ... BW.

The only problem with this I can see is that if I move the middle two pieces, I can't push the remaining pieces together to fill the gap, and get another BW pair.  Is that true?  Can someone please clarify?  Thanks.

1+1=2?

  • Guest
移动棋子
« Reply #5 on: 十二月 08, 2004, 07:49:05 am »
No, you are not allowed to push the remaining pieces together, should there be any space between, and that's the fun of the game. Remember, you can move two connected and only two connected pieces. Any other moves shall be considered illegal.

fzy

  • Hero Member
  • *****
  • Posts: 520
移动棋子
« Reply #6 on: 十二月 10, 2004, 10:44:23 am »
Is swapping allowed? If so, here is a solution:

Let's denote the stones by their position as from 1 to 8.

1) move 7 and 8 to 9 and 10
2) move 1 and 2 to 7 and 8
3) swap 4 and 5
4) swap 8 and 9

This basic idea (make a sequence in the form BBWWBBWW... in n/2 moves and do n/2 swaps) works for any n.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
移动棋子
« Reply #7 on: 十二月 10, 2004, 10:50:10 am »
No, swap is not allowd. :(

wang tao

  • Newbie
  • *
  • Posts: 2
Answer
« Reply #8 on: 十二月 12, 2004, 03:01:26 am »
In fact the 4 white/4 black question is not very tough, but it is key to the solution of N white/N black. I post the solution here for the 4W/4B, sure someone will find a solution to any number. We tried this game years back in grad school, still remembered the funs...

Start:
WWWWBBBB (Note as 1,2,3,4,5,6,7,8, 9,10 (9,10 are positions to be used))
S1:
W      WBBBBWW (Move 2,3 to 9,10)
S2:
WBBW      BBWW (Move 5,6 to 2,3)
S3:
WBBWBWB      W (Move 8,9 to 5,6)
S4:
     BWBWBWBW (Move 1,2 to 8,9)
1+1=2?

wang tao

  • Newbie
  • *
  • Posts: 2
Rework
« Reply #9 on: 十二月 12, 2004, 03:08:21 am »
Oops....., the computer ate up my spaces. I will use "S" for space left by one moved piece, hope it is not too confusing:
Start:
WWWWBBBB
S1
WSSWBBBBWW
S2
WBBWSSBBWW
S3
WBBWBWBSSW
S4
SSBWBWBWBW
1+1=2?

fzy

  • Hero Member
  • *****
  • Posts: 520
移动棋子
« Reply #10 on: 一月 01, 2005, 01:07:08 pm »
Here are solutions for 5, 6, and 7 pairs. Together with 4 pairs, they can be extended to any number.

5 pairs:

BBBBBWWWWW
WWBBBBBWWSSW
WWBSSBBWWBBW
WWBBWBSSWBBW
WSSBWBWBWBBW
WBWBWBWBWB

6 pairs:

BBBBBBWWWWWW
WWBBBBBBWWWSSW
WWBBBSSBWWWBBW
WWBBBWWBWSSBBW
WWBBSSWBWBWBBW
WSSBWBWBWBWBBW
WBWBWBWBWBWB

7 pairs:

BBBBBBBWWWWWWW
WWBBBBBBBWWWWSSW
WWBBSSBBBWWWWBBW
WWBBWWBBBWSSWBBW
WWBBWSSBBWWBWBBW
WWBBWBWBSSWBWBBW
WSSBWBWBWBWBWBBW
WBWBWBWBWBWBWB

I have not found a unified way to describe all the solutions.

mars15

  • Newbie
  • *
  • Posts: 8
Re: 移动棋子
« Reply #11 on: 十一月 28, 2005, 06:15:02 pm »
 
這種問題我老早(大約西元1960年)就用試誤法解開了
A:
1 2 3 4 5 6
黑黑黑白白白 3黑 + 3白3/2=1...1
空空黑白白白黑黑 同色移動一次
空空黑白白空空黑白黑
空空空空白黑白黑白黑
B:
1 2 3 4 5 6 7 8
黑黑黑黑白白白白4黑 + 4白 (整除,商為偶數)
黑空空黑白白白白黑黑
黑白白黑空空白白黑黑同色移動二次
黑白白黑白黑白空空黑
空空白黑白黑白黑白黑
C:
1 2 3 4 5 6 7 8 9 10
黑黑黑黑黑白白白白白 5黑 + 5白5/2=2...1 (有餘數)
黑空空黑黑白白白白白黑黑
黑白白黑黑白白空空白黑黑 同色移動二次
黑白白黑空空白黑白白黑黑
黑白白黑白黑白黑白空空黑
空空白黑白黑白黑白黑白黑
D:
1 2 3 4 5 6 7 8 9 101112
黑黑黑黑黑黑白白白白白白 6黑 + 6白6/2=3 (整除,商為奇數)
黑空空黑黑黑白白白白白白黑黑
黑白白黑黑黑白空空白白白黑黑
黑白白空空黑白黑黑白白白黑黑同色移動三次
黑白白黑白黑白黑空空白白黑黑
黑白白黑白黑白黑白黑白空空黑
空空白黑白黑白黑白黑白黑白黑
 

102黑 + 102白同色移動五十一次用規律 D 即可解之
 
 B 規律適用於 n=4m 之所有 m>=1 之正整數n=4,8,12,16,20,...
 C 規律適用於 n=2m+3 之所有 m>=1 之正整數 n=5,7,9,11,13,15,...
D 規律適用於 n=2(2m+1) 之所有 m>=1 之正整數 n=6,10,14,18,22,...
B, C , D(A)規律都有很簡單的口訣,如[1,2,...2],[1,2,...1],[1,2,...3,0]

口訣解說:如n=8 則套口訣 B[1,2,2,2]

1 2 3 4 5 6 7 8 910111213141516
黑黑黑黑黑黑黑黑白白白白白白白白
第一個1,代表從最左點右邊留一個黑(1),移動2與3到白子16的右邊
第二個2,代表從最右點左邊留二個白(15,16),移動13與14到前面空下來的2,3位
第三個2,代表從2,3位點右邊留二個黑(4,5),移動6與7到前面空下來的13,14位
第四個2,代表從13,14位點左邊留二個白(11,12),移動9與10到前面空下來的6,7位

接下來的四次移動都是黑白或是白黑, 左右填補,應該沒有問題.
1 13144 5 9 108 1112 6 7 1516 2 3

黑白白黑黑白白黑空空白白黑黑白白黑黑

黑白白黑黑白白黑白黑白白黑黑白空空黑 第五次移動16,2
黑白白黑空空白黑白黑白白黑黑白黑白黑 第六次移動5,9
黑白白黑白黑白黑白黑白空空黑白黑白黑 第七次移動12,6
空空白黑白黑白黑白黑白黑白黑白黑白黑 第八次移動1,13

 有興趣的朋友不妨試試看

« Last Edit: 十一月 28, 2005, 06:29:49 pm by mars15 »

idiot94

  • Sr. Member
  • ****
  • Posts: 484
Re: 移动棋子
« Reply #12 on: 十一月 29, 2005, 10:03:00 am »
wow, your memory is as admirable as your solution :)
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

mars15

  • Newbie
  • *
  • Posts: 8
Re: 移动棋子
« Reply #13 on: 十一月 29, 2005, 02:25:34 pm »
此地都是專家,這個[玻璃杯問題]一般只有討論到最多7+7就跳過去了,區區一點心得分享同好.
謝謝鼓勵.
補充說明:
規則中,僅表示[n/2]q (n之半數取整數)次移動同色棋子部分,除了頭尾之1,2,3,0外,
不足之數均為2.

n=3 [rule: 0]故第一次移最左邊兩子.(實際上左或右均可,依個人習慣用法)

例如n=9(黑白棋子各9個),規則為[1,2,2,1]

10+10 [Rule: 1,2,2,3,0]

01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22
黑,黑,黑,黑,黑,黑,黑,黑,黑,黑,白,白,白,白,白,白,白,白,白,白,空,空

1. move 02,03 to 21,22
黑,空,空,黑,黑,黑,黑,黑,黑,黑,白,白,白,白,白,白,白,白,白,白,黑,黑

2. move 17,18 to 02,03
黑,白,白,黑,黑,黑,黑,黑,黑,黑,白,白,白,白,白,白,空,空,白,白,黑,黑

3. move 06,07 to 17,18
黑,白,白,黑,黑,空,空,黑,黑,黑,白,白,白,白,白,白,黑,黑,白,白,黑,黑

4. move 12,13 to 06,07
黑,白,白,黑,黑,白,白,黑,黑,黑,白,空,空,白,白,白,黑,黑,白,白,黑,黑

5. move 08,09 to 12,13 above are moving 2 of same colors
黑,白,白,黑,黑,白,白,空,空,黑,白,黑,黑,白,白,白,黑,黑,白,白,黑,黑

6. move 13,14 to 08,09
黑,白,白,黑,黑,白,白,黑,白,黑,白,黑,空,空,白,白,黑,黑,白,白,黑,黑

7. move 16,17 to 13,14
黑,白,白,黑,黑,白,白,黑,白,黑,白,黑,白,黑,白,空,空,黑,白,白,黑,黑

8. move 05,06 to 16,17
黑,白,白,黑,空,空,白,黑,白,黑,白,黑,白,黑,白,黑,白,黑,白,白,黑,黑

9. move 20,21 to 05,06
黑,白,白,黑,白,黑,白,黑,白,黑,白,黑,白,黑,白,黑,白,黑,白,空,空,黑

10. move 01,02 to 20,21
空,空,白,黑,白,黑,白,黑,白,黑,白,黑,白,黑,白,黑,白,黑,白,黑,白,黑

記憶法:
3(0);4(1,2);5(1,1);6(1,3,0);7(1,2,1);8(1,2,2,2);9(1,2,2,1);10(1,2,2,3,0);
11(1,2,2,2,1);12(1,2,2,2,2,2);13(1,2,2,2,2,1);14(1,2,2,2,2,3,0);....

歸納結論:
1.凡相同黑白棋子數各不小於3均有解.
2.一次移動同色棋子之移動次數必為單色棋子數之半(取整數).
3.移動相隔2子之先後次序可變動.(如棋子數多,規則為...2,2,2,2...,可以跳取2,4,6,...間隔)
4.N黑加N白之棋子必定需移動N次,才能夠由兩邊分色排成相間格雜色.
5.如排完後中間留空或次數超過單色棋子數均為失敗.

請多多指教.