Board logo

標題: 兩人對局遊戲 [打印本頁]

作者: tsyr    時間: 2014-6-29 09:47     標題: 兩人對局遊戲

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

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

圖片附件: 1.png (2014-6-29 09:47, 39.72 KB) / 該附件被下載次數 3875
https://math.pro/db/attachment.php?aid=2429&k=da97a57a6ca114265dc42660d3091040&t=1711710182


作者: hua0127    時間: 2014-6-29 15:51     標題: 回復 1# tsyr 的帖子

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

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

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

[ 本帖最後由 hua0127 於 2014-6-29 06:00 PM 編輯 ]
作者: tsyr    時間: 2014-6-29 16:17

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

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

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

先不提供解答,歡迎有興趣者挑戰看看!
解法超簡單,但需要巧思
作者: thepiano    時間: 2014-6-29 16:57     標題: 回復 2# hua0127 的帖子

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

若在做以上動作之前,這個"另一行"的棋子是有空缺狀態,例如:□●□●□□□●●●......
那以上動作好像做不到
作者: tsyr    時間: 2014-6-29 17:24     標題: 回復 4# thepiano 的帖子

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

或者我誤會您的意思?
作者: thepiano    時間: 2014-6-29 17:35

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

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

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

[ 本帖最後由 thepiano 於 2014-6-29 05:50 PM 編輯 ]
作者: tsyr    時間: 2014-6-29 17:52

對!沒錯!
這樣一來,
(1) 若套用(1),不可能保留
(2) 若套用(2),不可能全取完
(3) 若套用(3),不可能另一行保留至1顆
所以要另想辦法解決。
但如果只解決'出現空缺'的問題,則會影響原本'對稱'的假設
可能要重新用一個新方法了
作者: hua0127    時間: 2014-6-29 17:53     標題: 回復 6# thepiano 的帖子

鋼琴老師的想法是對的~此反例將情況(1)(2)(3)全部打死XD
作者: tsyr    時間: 2014-6-29 17:55

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

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

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

[ 本帖最後由 tsyr 於 2014-6-29 06:06 PM 編輯 ]
作者: cefepime    時間: 2014-6-30 23:20

我借用一下 hua0127 老師的巧思,加上我自己的拙見,得到第一位玩家有必勝策略的結論,請各位高人看看能不能成立:


1. 第一位玩家先將中間的 100x98 矩形拿走,留下第一行跟最後一行。
現將一顆孤立棋子(其兩端皆無棋子)稱為"點",二顆以上棋子連續排列稱為"線",則以下遊戲進行下去,將是"點"與"線"之集合。


2. 此時棋盤上,有 2 條"線"。


3. 以下第一位玩家採取如下策略: 第二位玩家怎麼取棋子,我就取另外一行相同位置的棋子 (那麼"線"的數量在第一位玩家取完後,保持偶數),直至下一步情況(第4點)出現時,改採第5點策略:


4. 棋盤上恰有 2 條"線"時,第二位玩家使棋盤上只剩 1 條"線"。說明: 從第2步 2 條"線"開始,"線"的數量或可增減(兩人分別進行一次後,最多增減2條),但終究隨著取走棋子,"線"的數量會減少,且在第一位玩家執行第3點的策略下,必然發生第二位玩家使棋盤上恰有 2 條"線"成為恰有 1 條"線"的情況。


5. 在第4點中,第一位玩家面對 1 條"線",及若干個(也許0個,亦無妨)"點"。由於1 條"線"可使之化為 0 或 1 個"點",故第一位玩家必可使棋盤上剩下奇數個"點",從而獲勝。









[ 本帖最後由 cefepime 於 2014-6-30 11:27 PM 編輯 ]




歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/) 論壇程式使用 Discuz! 6.1.0