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

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。