Board logo

標題: 兩人對局遊戲 [打印本頁]
作者: tsyr    時間: 2014-6-29 09:47     標題: 兩人對局遊戲

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

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

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

作者: 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