兩人對局遊戲
兩人對局遊戲，初始時在100×100 棋盤的每個小方格內都放有一顆棋子。每一步，輪到的玩家必須移除一塊由小方格組成的矩形區域內所有的棋
子，並且在移除之前這塊區域不能含有空的小方格，移除最後一顆棋子的
玩家為輸家。下圖是在4×4 棋盤上的一局遊戲例子，顯示出第一位玩家輸
了此局。請問第一位還是第二位玩家有必勝的策略？
我不知道答案，附圖在下面
回復 1# tsyr 的帖子
先手必勝!!第一位玩家先將中間的100X98的矩形拿走，留下第一行跟最後一行，
然後第二位玩家不論取哪一行的某相鄰棋子，輪到第一位玩家時就是
走模仿棋取走對應的另外一行的相同位置的棋子，
直到第二位玩家取棋出現以下的情況：
(1) 將某一行取完，則第一位玩家將另一行保留至1顆，結束
(2) 將某一行取至剩下1顆，則第一位玩家將另外一行的棋子全取完，結束。
(3) 將某一行取至剩下不相鄰的2顆，則第一位玩家將另一行保留至1顆，則整盤棋會剩下3顆孤立的棋子，結束
感謝鋼琴老師提供反例~~此想法有瑕疵，要再想想XD
[[i] 本帖最後由 hua0127 於 2014-6-29 06:00 PM 編輯 [/i]] 好強喔!
竟然想得到利用"對稱"來解題
太巧妙了
應該是沒有漏掉，實際玩一次就知道，沒有其他可能了吧!
這又讓我想到之前做過的另一題，也是要用對稱來解題
在桌上有11堆石子，每堆各10枚。小皮與小貝進行以下遊戲：他們輪流從中取石子，規定小皮每次只能從同一堆中取1、2或3枚石子，而小貝只能從1、2或3堆中各取一枚。小皮先拿，拿到最後一枚石子者勝。無論對手如何應對，請問誰有必勝的策略？
先不提供解答，歡迎有興趣者挑戰看看!
解法超簡單，但需要巧思
回復 2# hua0127 的帖子
"第一位玩家將另一行保留至 1 顆"或"第一位玩家將另一行的棋子全取完"若在做以上動作之前，這個"另一行"的棋子是有空缺狀態，例如：□●□●□□□●●●......
那以上動作好像做不到
回復 4# thepiano 的帖子
"第一位玩家將另一行保留至 1 顆"的前一步，第二位玩家必須將某一行取完，既然第二位玩家能夠將某一行取完，表示不可能有空缺吧!(因為對稱，所以第一行沒有空缺)
或者我誤會您的意思? 剩二行，一行在上，一行在下
假設第二位玩家取上行，第一位玩家取下行
第二位玩家一次只取一個，依序取第 1、3、5、7、...、99、2、4、6、8、... 個
第一位玩家若取相同位置的棋子，那就會出現空缺了
然後第二位玩家取第 96 個棋子後，剩第 98 個和第 100 個棋子，這是 hua0127 老師的情況(3)
這時若第一位玩家也取第 96 個棋子，那他就輸了
當然他也無法一次取 2 個棋子，而只保留最後一個棋子，因為有空缺
[[i] 本帖最後由 thepiano 於 2014-6-29 05:50 PM 編輯 [/i]] 對!沒錯!
這樣一來，
(1) 若套用(1)，不可能保留
(2) 若套用(2)，不可能全取完
(3) 若套用(3)，不可能另一行保留至1顆
所以要另想辦法解決。
但如果只解決'出現空缺'的問題，則會影響原本'對稱'的假設
可能要重新用一個新方法了
回復 6# thepiano 的帖子
鋼琴老師的想法是對的~此反例將情況(1)(2)(3)全部打死XD 對!沒錯!這樣一來，
(1) 若套用(1)，不可能保留
(2) 若套用(2)，不可能全取完
(3) 若套用(3)，不可能另一行保留至1顆
所以要另想辦法解決。
但如果只解決'出現空缺'的問題，則會影響原本'對稱'的假設
可能要重新用一個新方法了 給個新想法，若換個方向思考，先想想看若題目要求
[b][u]"拿到最後一顆棋子就算贏了"[/u][/b]
則第一位玩家反而有必贏的可能
這樣好像就和題目成矛盾了
如果能角色互換就好了
這想法說不定是另一個起點
[[i] 本帖最後由 tsyr 於 2014-6-29 06:06 PM 編輯 [/i]] [size=3]我借用一下 hua0127 老師的巧思，加上我自己的拙見，得到第一位玩家有必勝策略的結論，請各位高人看看能不能成立:[/size]
[size=3]
[/size]
[size=3]1. 第一位玩家先將中間的 100x98 矩形拿走，留下第一行跟最後一行。[/size]
[size=3]現將一顆孤立棋子(其兩端皆無棋子)稱為"點"，二顆以上棋子連續排列稱為"線"，則以下遊戲進行下去，將是"點"與"線"之集合。[/size]
[size=3]
[/size]
[size=3]2. 此時棋盤上，有 2 條"線"。[/size]
[size=3]
[/size]
[size=3]3. 以下第一位玩家採取如下策略: 第二位玩家怎麼取棋子，我就取另外一行相同位置的棋子 (那麼"線"的數量在第一位玩家取完後，保持偶數)，直至下一步情況(第4點)出現時，改採第5點策略:[/size]
[size=3]
[/size]
[size=3]4. 棋盤上恰有 2 條"線"時，第二位玩家使棋盤上只剩 1 條"線"。說明: 從第2步 2 條"線"開始，"線"的數量或可增減(兩人分別進行一次後，最多增減2條)，但終究隨著取走棋子，"線"的數量會減少，且在第一位玩家執行第3點的策略下，必然發生第二位玩家使棋盤上恰有 2 條"線"成為恰有 1 條"線"的情況。[/size]
[size=3]
[/size]
[size=3]5. 在第4點中，第一位玩家面對 1 條"線"，及若干個(也許0個，亦無妨)"點"。由於1 條"線"可使之化為 0 或 1 個"點"，故第一位玩家必可使棋盤上剩下[/size][size=3]奇數個"點"，從而獲勝。[/size]
[size=3]
[/size]
[size=3]
[/size]
[size=3]
[/size]
[size=3]
[/size]
[[i] 本帖最後由 cefepime 於 2014-6-30 11:27 PM 編輯 [/i]]
頁:
[1]