关于不增加组的乒乓球问题先手输赢的判定和取胜策略
不增加组的乒乓球问题一般可叙述如下：有m(m≥1)堆东西，每堆东西中有ni(ni≥1)(i=1,…,m)个物品。现有甲乙两人玩游戏如下：
甲乙轮流从这m堆东西中任意拿走几个物品，只须满足:
1) 每次至少拿走1个物品，至多拿走K(K>1)个物品。
2) 每次拿走的物品须在同一堆中。
若甲拿完后只剩最后一个物品，则甲胜。若乙拿完后只剩最后一个物品，则乙胜。
问是否存在取胜对策？若有，在何种情况下先拿者必胜？
为使问题便于讨论，条件1)可改为：1) 每次至少拿走1个物品。
因为原来问题可化为改变后ni(ni≤K+1)(i=1,…,m)个物品问题。
我仔细分析此问题后发现一个有趣的事实：先手输赢与ni(i=1,…,m)的二进制异或运算有密切关系。
下面给出此问题的结论（并举例说明），数学证明见我的论文
令B(ni)表示ni的二进制数,lmax=max(n1,n2,…,nm)
b=B(n1)^B(n2)^…^B(nm),其中^为二进制数按位异或(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）只有一个nj＞1,令b’= B(n1)^…^B(nj-1)^ B(nj+1)^…^B(nm)(即i≠j异或运算)
若b’=0，在nj中取nj-1个剩下1个。
例：1，7，1，1，1==>1，1，1，1，1
若b’≠0，在nj中取nj个剩下0个。
例：1，1，8，1，1，1==>1，1，0，1，1，1
b）至少有两个ni＞1，令k为b的位数
必有一nj，满足，B(nj)的第k位是1，设b”= B(nj)^b，c是b”的十进制数，则
在nj中取几个剩下c个。
例：9，8，5，2（十进制）1001，1000，0101，0010(二进制)
b=1001^1000^0101^0010=110
1001，1000，0101，0010中0101的第3位是1
b”= B(nj)^b=0101^110=011(二进制)=3（十进制）
9，8，5，2==>9，8，3，2。
页:
[1]