4. 甲、乙二人在1×n（其中n>1）方格表的小方格內輪流填入「○」和「╳」記號。甲全填入「╳」，乙全填入「○」，每個小方格內只可填入一個記號，任何兩個相鄰的小方格內不可以填入相同的記號，無法再繼續填入記號者輸。若由甲先開始填，請問哪一個人有必勝的策略？（七分）
國中

回應

arsene996655

2007-12-16 17:34
乙有必勝策略
讓我們作以下定義:
對於某一人
不能填的位置稱為死格
而填任何符號的型態只有7種
其中2種會讓自己的死格相對於對方增加2格
另5種相對於對方增加1格
乙必須避免上述2種
則死格數永遠少於或等於甲
(因甲第一步必定損失1或2個死格)
最後一步時
若總共有奇數格
甲因死格數較多而無法填入
若總共有偶數格
甲最好狀況則是全部填完
仍不能填入
因此乙勝
(省略其證明過程)