就是在一排棋盤上有n個X,和n個O,
如n=3時,就是:
XXXOOO
希望可以依下列的規則移成:
OXOXOX ( O在前面唷 )
且不在乎最後移到的位置在哪裡.
移動的規則就是:
每次必須移動相鄰的兩個棋子到兩個空位中,且不能單獨移動其中一個.
希望可以求出一個移動步數最少的解.
對n=3時,移動步數最少的解為:
XXXOOO
XOOOXX
XOO XOX
OXOXOX
共3步.
據說有通解,最多只需要n步..
到底要怎麼做呢?
--
一位拓撲學家不能說出炸麵餅圈和他的咖啡杯之間的差別....
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: 1-3.cc1.ck.tp.edu.tw
> -------------------------------------------------------------------------- <
作者: JKD (妙手基金經理人) 看板: puzzle
標題: Re: 一個問題!
時間: Mon May 15 16:26:01 2000
※ 引述《zxcmnb (從陡坡斜倚下來)》之銘言：
: 就是在一排棋盤上有n個X,和n個O,
: 如n=3時,就是:
: XXXOOO
: 希望可以依下列的規則移成:
: OXOXOX ( O在前面唷 )
: 且不在乎最後移到的位置在哪裡.
: 移動的規則就是:
: 每次必須移動相鄰的兩個棋子到兩個空位中,且不能單獨移動其中一個.
: 希望可以求出一個移動步數最少的解.
: 對n=3時,移動步數最少的解為:
: XXXOOO
: XOOOXX
: XOO XOX
: OXOXOX
: 共3步.
: 據說有通解,最多只需要n步..
: 到底要怎麼做呢?
這個遊戲叫做"鴛鴦戲水",用數學歸納法可以證明n組只要移動n次即可.
這個證明很有趣,是證明true(n) => true(n+4)
--
★
｜ ╭╮
● ╰╯ ●
｜◥██◤
██ 來! 變個魔術瞧瞧......。 我是妙手宗!
http://crypto.ee.ntu.edu.tw/~magic/PuzzleWorld.html
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: h140.s28.ts30.hinet.net
> -------------------------------------------------------------------------- <
作者: zxcmnb (從陡坡斜倚下來) 看板: puzzle
標題: Re: 一個問題!
時間: Tue May 16 21:06:58 2000
※ 引述《JKD (妙手基金經理人)》之銘言：
: ※ 引述《zxcmnb (從陡坡斜倚下來)》之銘言：
: : 嗯嗯..
: : 我已經知道要怎麼推廣了,
: : 可是在n=5和n=6的時候,
: : 要怎麼搬,真是想破頭也想不出來丫..
: 很難記說,我也記不住...
: 不過你能靠提示就想到歸納的方法,倒是不簡單...
四的拼法:
XXXXOOOO
X XOOOOXX
XOOX OOXX
XOOXOXO X
OXOXOXOX
所以推廣成n就是
XXXXx....xo....oOOOO
X Xx....xo....oOOOOXX
XOOXx....xo....o OOXX
^^^^^^^^^^^^^^用這裡拼出n-4的部分
.
.
.
XOOX..............OOXX
^^ ^^最後再把這兩個掉回該放的位置就行了
--
一位拓撲學家不能說出炸麵餅圈和他的咖啡杯之間的差別....
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: 195.c178.ethome.net.tw
> -------------------------------------------------------------------------- <
作者: arist (這實在是太複雜了) 看板: puzzle
標題: 益智遊戲
時間: Sat May 20 03:13:46 2000
如上次那一題戲水鴛鴦(之前我有聽過不同的說法 不過我忘了)
現在在來一題類似題 不過名字我也忘了
○○○ ●●●
初始情況 左邊 三個黑色棋子 右邊三個白色棋子
操作 將一個棋子往左或往右搬為一次操作
另一種操作方法為跳過一個棋子 也算是一次操作
目的 將黑色棋子和白色棋子對調 及左邊三顆白子 右邊三棵黑子
○○○● ●●
○○ ●○●●
○ ○●○●●
○●○ ○●●
○●○●○ ●
○●○●○●
○●○● ●○
○● ●○●○
●○●○●○
● ○●○●○
●●○ ○●○
●●○●○ ○
●●○● ○○
●● ●○○○
●●● ○○○
共15步 且很簡單就可證明其為最少步數
當然也可以推到一般的n個的狀態 只要抓住3個的搬動原則即可
關於此問題的一些補充 我再過幾天再po上來
若有網友想對此問題的一般型式補充也很歡迎
依所po的內容 板主會給100~300的ptt幣 當然要有談到較深的內容時 板主才發
必竟本人不是站長 ptt幣也是有限的
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: arist.m7.ntu.edu.tw