- 注册时间
- 2009-6-4
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 11282
- 在线时间
- 小时
|
马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。
您需要 登录 才可以下载或查看,没有账号?欢迎注册
×
不增加组的乒乓球问题一般可叙述如下:
有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)的二进制异或运算有密切关系。
下面给出此问题的结论(并举例说明),数学证明见我的论文
“剩最后一个”对策问题及其解法.doc
(234.5 KB, 下载次数: 0)
令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。 |
|