取数游戏

noski

首先，有个对称性取数策略：
结论A. 如果轮到某一方下子时，剩下奇数个数字，那么该方就可以通过下在正中间，然后对称下子的方法取胜。
由结论A可推出：n为奇数时，先取方必胜。

而当n为偶数时，先取方有三种策略：
策略1. 取最边上的数字，这样还剩下n-2个数字可取；
策略2. 取边上第二个数字，这样还剩下n-3个数字可取；
策略3. 取中间的某个数字，这样将数字序列分成两段，一段为奇数一段为偶数。
由结论A可知，此时先取方采用策略2则必输，因此，先取方只可选用策略1和策略3。

假设双方只采用策略1，就成了一个递归的过程，数字序列长度不断减2，最后谁拿到最后两个谁赢，因此：
n = 4k 时，先取方输；
n = 4k+2 时，先取方赢。
但是，足够聪明的双方不会只采用策略1。

而考虑策略3，先取方如何把这个数字序列截成两段，才能使自己赢呢？
继续。。

noski

我想，对于先手将数字序列分成两段这种情况，还需要进一步进行抽象。
先手记为A，后手记为B，下面将站在A的角度看如何取胜：

定义：
先手制胜权  X(n) 操作序列形如[ABABA]，对于连续的n个数，如果先手A能确保必胜，则称该n具有先手制胜权。
先手保留权  Y(n) 操作序列形如[BABAB]，对于连续的n个数，如果让B先下时，A能有策略确保最后一子仍被B取得，那么称该n具有先手保留权。

比如：
先手制胜权：
对于所有的奇数，X(n)=1；
对于偶数，
X(2)=1
X(4)=0
X(6)=1
X(8)=0
……
这个X(n)就是lulijie要找的答案。

先手保留权：
Y(1)=1
Y(2)=1
Y(3)=0
Y(4)=1
Y(5)=0
Y(6)=1
Y(7)=1
Y(8)=1
……
比如n=1或6，先手方既有先手制胜权，又有先手保留权。那么就可以推出n=10的情况，让先手方取的数把序列分隔成长度为1和6的两段，于是先手方必胜，X(10)=1。

对于任一个n的情况，先手方A下在中间，把n分隔成i和j两个序列，如果存在i和j，使得X(i)、Y(i)、X(j)、Y(j)同时为1，那么X(n)=1。
好像可以递推，大家可以验证一下。。

noski

其实我这个先手保留权，就是你的问题的兄弟篇——谁取了最后一个数谁输。。

另外，有个简单推断法：
如果n为奇数，X(n)=1
如果n为偶数，且X(n-2)=0，则X(n)=1
如果n为偶数，且X(n-2)=1，那么先手的策略就是把n分成一个奇数i和一个偶数j，并使X(j)=1。不过这个情况还没想通如何判断能不能赢。。