11 12
發新話題
打印

兩人對局遊戲

推到噗浪
推到臉書

兩人對局遊戲

兩人對局遊戲,初始時在100×100 棋盤的每個小方格內都放有一顆棋子。
每一步,輪到的玩家必須移除一塊由小方格組成的矩形區域內所有的棋
子,並且在移除之前這塊區域不能含有空的小方格,移除最後一顆棋子的
玩家為輸家。下圖是在4×4 棋盤上的一局遊戲例子,顯示出第一位玩家輸
了此局。請問第一位還是第二位玩家有必勝的策略?

我不知道答案,附圖在下面

附件

1.png (39.72 KB)

2014-6-29 09:47

1.png

TOP

回復 1# tsyr 的帖子

先手必勝!!
第一位玩家先將中間的100X98的矩形拿走,留下第一行跟最後一行,
然後第二位玩家不論取哪一行的某相鄰棋子,輪到第一位玩家時就是
走模仿棋取走對應的另外一行的相同位置的棋子,
直到第二位玩家取棋出現以下的情況:

(1) 將某一行取完,則第一位玩家將另一行保留至1顆,結束
(2) 將某一行取至剩下1顆,則第一位玩家將另外一行的棋子全取完,結束。
(3) 將某一行取至剩下不相鄰的2顆,則第一位玩家將另一行保留至1顆,則整盤棋會剩下3顆孤立的棋子,結束

感謝鋼琴老師提供反例~~此想法有瑕疵,要再想想XD

[ 本帖最後由 hua0127 於 2014-6-29 06:00 PM 編輯 ]

TOP

好強喔!
竟然想得到利用"對稱"來解題
太巧妙了
應該是沒有漏掉,實際玩一次就知道,沒有其他可能了吧!

這又讓我想到之前做過的另一題,也是要用對稱來解題

在桌上有11堆石子,每堆各10枚。小皮與小貝進行以下遊戲:他們輪流從中取石子,規定小皮每次只能從同一堆中取1、2或3枚石子,而小貝只能從1、2或3堆中各取一枚。小皮先拿,拿到最後一枚石子者勝。無論對手如何應對,請問誰有必勝的策略?

先不提供解答,歡迎有興趣者挑戰看看!
解法超簡單,但需要巧思

TOP

回復 2# hua0127 的帖子

"第一位玩家將另一行保留至 1 顆"或"第一位玩家將另一行的棋子全取完"

若在做以上動作之前,這個"另一行"的棋子是有空缺狀態,例如:□●□●□□□●●●......
那以上動作好像做不到

TOP

回復 4# thepiano 的帖子

"第一位玩家將另一行保留至 1 顆"的前一步,第二位玩家必須將某一行取完
,既然第二位玩家能夠將某一行取完,表示不可能有空缺吧!(因為對稱,所以第一行沒有空缺)

或者我誤會您的意思?

TOP

剩二行,一行在上,一行在下
假設第二位玩家取上行,第一位玩家取下行

第二位玩家一次只取一個,依序取第 1、3、5、7、...、99、2、4、6、8、... 個
第一位玩家若取相同位置的棋子,那就會出現空缺了

然後第二位玩家取第 96 個棋子後,剩第 98 個和第 100 個棋子,這是 hua0127 老師的情況(3)
這時若第一位玩家也取第 96 個棋子,那他就輸了
當然他也無法一次取 2 個棋子,而只保留最後一個棋子,因為有空缺

[ 本帖最後由 thepiano 於 2014-6-29 05:50 PM 編輯 ]

TOP

對!沒錯!
這樣一來,
(1) 若套用(1),不可能保留
(2) 若套用(2),不可能全取完
(3) 若套用(3),不可能另一行保留至1顆
所以要另想辦法解決。
但如果只解決'出現空缺'的問題,則會影響原本'對稱'的假設
可能要重新用一個新方法了

TOP

回復 6# thepiano 的帖子

鋼琴老師的想法是對的~此反例將情況(1)(2)(3)全部打死XD

TOP

對!沒錯!
這樣一來,
(1) 若套用(1),不可能保留
(2) 若套用(2),不可能全取完
(3) 若套用(3),不可能另一行保留至1顆
所以要另想辦法解決。
但如果只解決'出現空缺'的問題,則會影響原本'對稱'的假設
可能要重新用一個新方法了

TOP

給個新想法,若換個方向思考,先想想看若題目要求
"拿到最後一顆棋子就算贏了"
則第一位玩家反而有必贏的可能
這樣好像就和題目成矛盾了

如果能角色互換就好了
這想法說不定是另一個起點

[ 本帖最後由 tsyr 於 2014-6-29 06:06 PM 編輯 ]

TOP

 11 12
發新話題