关于不增加组的乒乓球问题先手输赢的判定和取胜策略

sheng_jianguo

　　不增加组的乒乓球问题一般可叙述如下：
　　有m(m≥1)堆东西，每堆东西中有n_i(n_i≥1)(i=1,…,m)个物品。现有甲乙两人玩游戏如下：
甲乙轮流从这m堆东西中任意拿走几个物品，只须满足:
1) 每次至少拿走1个物品，至多拿走K(K>1)个物品。
2) 每次拿走的物品须在同一堆中。
若甲拿完后只剩最后一个物品，则甲胜。若乙拿完后只剩最后一个物品，则乙胜。
问是否存在取胜对策？若有，在何种情况下先拿者必胜？

为使问题便于讨论，条件1)可改为：1) 每次至少拿走1个物品。
因为原来问题可化为改变后n_i(n_i≤K+1)(i=1,…,m)个物品问题。

我仔细分析此问题后发现一个有趣的事实：先手输赢与n_i(i=1,…,m)的二进制异或运算有密切关系。
下面给出此问题的结论（并举例说明），数学证明见我的论文 “剩最后一个”对策问题及其解法.doc (234.5 KB, 下载次数: 0)

2010-12-19 20:06 上传

点击文件名下载附件

令B(n_i)表示n_i的二进制数,lmax=max(n₁,n₂,…,n_m)
b=B(n₁)^B(n₂)^…^B(n_m),其中^为二进制数按位异或(C语言中的^,也即不进位加法)运算符号。
存在取胜对策。当b=0，lmax =1 或b≠0，lmax＞1 时先拿者必胜，当b=0，lmax＞1 或b≠0，lmax=1 时后拿者必胜。
取胜对策：当b=0，lmax =1时为简单情况，随便怎样（按规则）取都赢。
当b≠0，lmax＞1时，分两种情况：
a）只有一个n_j＞1,令b’= B(n₁)^…^B(n_j-1)^ B(n_j+1)^…^B(n_m)  (即i≠j异或运算)
若b’=0，在n_j中取n_j-1个剩下1个。
例：1，7，1，1，1==>1，1，1，1，1
若b’≠0，在n_j中取n_j个剩下0个。
例：1，1，8，1，1，1==>1，1，0，1，1，1
b）至少有两个n_i＞1，令k为b的位数
必有一n_j，满足，B(n_j)的第k位是1，设b”= B(n_j)^b，c是b”的十进制数，则
在n_j中取几个剩下c个。
例：9，8，5，2（十进制）1001，1000，0101，0010(二进制)
b=1001^1000^0101^0010=110
1001，1000，0101，0010中0101的第3位是1
b”= B(n_j)^b=0101^110=011(二进制)=3（十进制）
9，8，5，2==>9，8，3，2。