一维反Nim游戏

medie2005

一条线上连续地放有n个棋子, 两个人轮流拿1个或者相邻的2个棋子(拿走后两边的棋子就不相邻了) 拿最后一颗棋子者为输，对方胜。 问n为多少时先拿的输?

mathe

这个是/thread-513-1-1.html 的一个特例 ===================================== 最终答案可以参考79#和84# 以及命令行判断先后手胜以及先手胜的方案的windows程序: cnext.rar (5.98 KB, 下载次数: 3)

2011-3-22 10:15 上传

点击文件名下载附件

medie2005

拿最后一颗棋子者为输。 反Nim游戏。 要是Nim游戏就简单了。

mathe

据说等价于某个特定大小的Nim游戏。

无心人

Σ	先手必胜	先手必输
1		1
2	2，1□1
3	3，1□2	1□1□1
4	1□3，1□1□2,1□1□1□1	4,2□2

无心人

Σ	先手必胜	先手必输
5	5,4□1,3□2,3□1□1,2□2□1,2□1□1□1	1□1□1□1□1
6	6,4□2,2□2□2,3□1□1□1,2□1□1□1□1	5□1,4□1□1,3□3,3□2□1,2□2□1□1

无心人

n = 7 看上表可知先手胜，因可以做成3□3或者5□1 n = 8 看上表可知先手胜，因可以做成3□3或者5□1

mathe

你改得好快嘛

无心人

呵呵 你来分析7以上的情况吧 定理 如果n先手必输，则n ＋ 1， n ＋ 2先手必赢 [ 本帖最后由 无心人 于 2008-9-10 11:37 编辑 ]

shshsh_0510

这类问题一弄不好就NPC了，只有某些可以很简单的判别。 这个问题感觉还有可能有较简单的方法，我分析了一下初始的情况： 对一个分划 n=n1+n2+n3+...+nk, n1≥n2≥n3≥...≥nk≥1, Count(x)表示其中等于x的ni数量。 称每个先手必败局势为"奇异的"。 1、n1=1时，所有奇异局势为：k为奇数 2、n1=2时，所有奇异局势为：k为偶数，并且Count(1)、Count(2)皆为偶数.