medie2005提出了一个问题:

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

问n为多少时先拿的输?

这个问题咋一看就是一个典型的Nim游戏。事实上，如果我们把"不允许把棋子拿光"这个限制去掉，问题马上转化为 一个非常简单的Nim游戏。先手只要拿走最中间的一个或两个棋子，接下去只要选择和对手上一轮选择的对称方案即可 保证胜利（拿走最后一颗棋子）。

而这个不允许把棋子拿光的游戏的最终结果也非常奇怪，当且仅当n为1,4,9,12,20之一时先手输。

详细内容

这个问题的复杂之处在于每次每人经过一次选择以后，会把一段连续的棋子分成两段，这使得游戏进行过程中，问题逐步由一段连续的棋子变为多段连续的棋子，而每一次我们都只能从其中一段中选择1个或2个相邻的棋子。

如果我们先考察允许把棋子拿光的情况，那么就是一个典型的Nim游戏。而[Mim游戏]之所以容易解决是在于我们可以对于最简单的状态（n个连续棋子）定义一个状态函数$s_n$。于是对于复合状态:也就是存在k段长度分别为$(n_1,n_2,...,n_k)$的连续棋子的状态，其对应的状态函数值就是$s_{n_1}\oplus s_{n_2}\oplus\dots\oplus s_{n_k}$， 其中$\oplus$代表按二进制比特位进行异或运算。 而一个状态只有在它对应的状态函数取值为0时才先手输，不然先手总可以做出一种选择使得留给对手的局面状态函数取值为0.

而允许取光棋子情况对应的Nim游戏的状态函数取值如下

s[1]=1
s[2]=2
s[3]=3
s[4]=1
s[5]=4
s[6]=3
s[7]=2
s[8]=1
s[9]=4
s[10]=2
s[11]=6
s[12]=4
s[13]=1
s[14]=2
s[15]=7
s[16]=1
s[17]=4
s[18]=3
s[19]=2
s[20]=1
s[21]=4
s[22]=6
s[23]=7
s[24]=4
s[25]=1
s[26]=2
s[27]=8
s[28]=5
s[29]=4
s[30]=7
s[31]=2
s[32]=1
s[33]=8
s[34]=6
s[35]=7
s[36]=4
s[37]=1
s[38]=2
s[39]=3
s[40]=1
s[41]=4
s[42]=7
s[43]=2
s[44]=1
s[45]=8
s[46]=2
s[47]=7
s[48]=4
s[49]=1
s[50]=2

于是即使对于存在多条线的复合初始状态，如果允许取光棋子，我们还是可以非常容易的判断出先手能否取胜，以及如何取胜。

对于不允许取光棋子的情况，使用计算机统计各种局面下两种模型下的胜负情况，发现大部分局面竟然胜负情况是相同，胜负不同的局面只占了极小的部分。 如果我们能够把所有胜负情况不同的局面都找出来，那么就可以很好的解决本题。

为了描述对于两种模型胜负不同的局面，我们先定义一些符号描述一些局面集合。 我们分别用字母A,E,O代表任意非负整数，非负偶数和非负奇数。 于是我们就可以使用$3+O*1$代表正好包含一个长度为3的线和奇数个长度为1的线的状态。 同样用$E*(1+4+9)$代表长度为1、4或9的线的总数是偶数但是不包含其它长度的线的状态（包含全空的状态） 同样用$A*5+O*(4+1)$代表可以包含任意多个长度为5的线以及长度为1或4的线的总数是奇数但是不包含其它长度的线的状态。

而最终通过半人工半计算机分析得出两种模型不同的所有状态如下:

O*9+E*(4+1)
12+E*(4+1)
O*5+O*(4+1)
E*5+A*(4+1)
A*20+E*(17+12+9)+A*(4+1)
25+O*(20+4+1)+E*(17+12+9)
25+O*9+O*(4+1)

而由于对于允许取走最后一个棋子的模型，开始只有一行的情况总是先手赢的。利用上面表格容易得出，对于开始只有一行的局面，只有长度为1、4、9、12、20的局面才会先手输。