3. 在一個雙人對局遊戲中，最初有n>2堆石子，每堆都恰好有一顆石子。兩人輪流進行以下操作：任選石子數量互質的二堆，將它們合併為一堆，無法依上述規則再繼續操作者為輸方。對於任意n>2，無論對手如何應對，請問玩家有無必勝的策略？（六分）
高中

回應

abc831128

2009-02-06 22:01
後者有必勝方法
社共有m堆當m為偶數堆時

(i)當初全為11111111.....1共偶數個
先手者只能合併為21111111111奇數個1
後者2211111111偶數個1
當2人如此下去 先手 後者永遠一直加1 則後者最能使全部變為2
後者贏
若有奇數個先者後者永遠把1變2後者亦有必勝法
(ii)先手第一步21111111111...1
若先者永遠的只把1變2 那是情況1
此時後者可把何數都加1
先令前m-1個(奇數) 都是1 第m個是2

此時若要使每個數經過+1後最後相等
必須有等式m+am-1=b (a b是自然數 此式是指經過b次加1個球 使的前(m-1)個1加了a+1個 第m個2加a個
m是偶數 所以b為奇數 後者勝

當m為奇數時
則1+1+1.....1=m(奇數)
所以只能分成奇數堆 所以a是奇數

此時b為奇數 後者勝

故後者有必勝策略