一个组合对策问题的解

Solution to a Combinatorial Game

本文求解如下的组合对策问题:设有一堆棋子,总数N 是奇数,甲乙两人轮流取子,每人每次可取一颗、二颗,最多可取s 颗,但不能不取,直至取完后分别来数甲乙两人所取棋子的总数,总数为奇数者获胜。站在甲的立场上考虑获胜的策略,文中解决了如下两个问题:(Ⅰ)总数N 应是什么样的奇数,甲才有获胜策略;(Ⅱ)当N 一定时,甲应采取什么样的策略取子,才能获胜。

Let there be a heap of beans with total number N(odd)and an integers,we difine a 2-person game Γ(N,s)as follows:The first player P_Ⅰ takessome beans from the heap,at least one bean and at most s beans.Player two,P_Ⅱ now picks some beans under the same constraint.The play then reverts toP_Ⅱ and continues in the same way until all beans have been removed.Theplayer with odd number of beans at hand wins.In this paper,we completely solve the game.At first,we give thewinning strategy(if exists)for P_Ⅰ.Theorem Let r be the number of beans P_Ⅰ leaving to P_Ⅱ at any step, and q be the number P_Ⅰ have at the end of the step.Then P_Ⅰ will win ifr≡1 or 0(mod(2s+2))if q is odd,andr≡s+1 or s+2(mod(2s+2)) if q is evenwhen s is odd andr≡1 or 0(mod(s+2))if q is odd,andr≡s+1(mod(s+2))if q is evenwhen s is even.The theorem can be proved by induction.As a by-product of the theoremwe haveCorollary Γ(n,s)is a win for P_(?) iff n≡s+1(mod(2s+2))when s isodd and n≡s+1(mod(s+2))when s is even.