数学研发论坛

 找回密码
 欢迎注册
查看: 21034|回复: 113

[转载] 棋子游戏

[复制链接]
发表于 2008-9-10 10:15:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
精华
一条线上连续地放有n个棋子, 两个人轮流拿1个或者相邻的2个棋子(拿走后两边的棋子就不相邻了)
不允许把棋子拿光, 不允许不拿. 谁不能行动就输了.

问n为多少时先拿的输?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 10:35:11 | 显示全部楼层
这个是
http://bbs.emath.ac.cn/thread-513-1-1.html
的一个特例

=====================================
最终答案可以参考79#84#
以及命令行判断先后手胜以及先手胜的方案的windows程序: cnext.rar (5.98 KB, 下载次数: 3)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-10 10:42:58 | 显示全部楼层
和Nim游戏不一样。
“不允许把棋子拿光”,很关键啊。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:07:42 | 显示全部楼层
等价于拿到最后一个输
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:26:23 | 显示全部楼层
1 2
状态下后手必输
1 2 3
后手必输
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:29:25 | 显示全部楼层
因为n=4先手必输
所以n = 5后手必输
n = 6后手必输

[ 本帖最后由 无心人 于 2008-9-10 11:30 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:32:27 | 显示全部楼层
n = 7就复杂了
如果从边缘拿,要先手输
所以要考虑从中间拿的方案
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:34:05 | 显示全部楼层
你改得好快嘛
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:36:11 | 显示全部楼层
呵呵
你来分析7以上的情况吧

定理  如果n先手必输,则n + 1, n + 2先手必赢

[ 本帖最后由 无心人 于 2008-9-10 11:37 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 13:32:08 | 显示全部楼层
7是必败的。
这类问题一弄不好就NPC了,只有某些可以很简单的判别。
这个问题感觉还有可能有较简单的方法,我分析了一下初始的情况:
对n的一个分划,按子集大小表示为{n1,n2,n3,...,nk},使n1>=n2>=n3...>=nk>0
称每个必败局势为"奇异的"。
1、|ni|<=1时,所有奇异局势为:k为奇数
2、|ni|<=2时,所有奇异局势为:(1) k为奇数时:|ni|=1 ;(2) k为偶数时:满足|ni|=1的ni有偶数个 ;
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2017-12-11 11:57 , Processed in 0.063502 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表