1.11 NIM（1）一排石头的游戏
面试是一个让面试双方互相增进了解的过程，不一定总是你问我答，有时候两人可以玩一些游戏，比如：
N块石头排成一行，每块石头有各自固定的位置（如图1-17所示）。两个玩家依次取石头，每个玩家每次可以取其中任意一块石头，或者相邻的两块石头，石头在游戏过程中不能移位（即编号不会改变），最后能将剩下的石头一次取光的玩家获胜。
图1-17 一排石头的位置
这个游戏有必胜策略吗？
分析与解法
初看这个游戏，感觉输赢似乎只是运气问题。但是我们通过深入分析，还是可以发现一些规律的。
注意游戏中“相连”这个条件，若给N块石头从1到N依次编号，则我们只能取编号相连的两块石头，例如可以同时取编号为1和2的两块石头，但不能同时取编号为1和3的两块石头，以此类推。
当题目中有“N个”之类的字眼出现时，我们往往可以从讨论一些简单的特例出发，进而逐渐掌握解题的规律：
（1）石头的数目N=1或者N=2
即只有一块或者两块石头，先取者即可一次取完所有的石头而获胜。
（2）石头的数目N=3
设三块石头排成一行，其编号依次为1、2、3（如图1-18所示），那么先取者若取走中间的2号石头，后取者只能取左边的1号石头或者右边的3号石头，必将剩下一块石头，先取者将取得最后的那块石头而获胜。
图1-18 编号为1、2、3的石头
（3）石头的数目N=4
设4块石头排成一行，其编号依次为1、2、3、4（如图1-19），那么先取者若取走2号石头、3号石头，后取者只能取最左边的1号石头或者最右边的4号石头，必将剩下一块石头，先取者将取得最后的那块石头而获胜。
图1-19 编号为1、2、3、4的石头
如果先取边上的石头（1或4），那么这个局面就退化成三块石头的情况。
（4）石头的数目N > 4
至此，我们发现了一个对称的规律，从前面对两块和3块石头的讨论中不难看出：如果N > 4，先取者取中间的一个（N为奇数）或者中间相连的两个（N为偶数），确保左右两边的石头数目是一样的，之后先取者只要每次以初始中心为对称轴，在与后取者所取石头位置对称的地方取得数目相同的石头，就可以保证每次都有石头取，并且必将取得最后的石头，赢得游戏。
所以说先取者将有必胜的策略！
扩展问题
经过快速思考，你轻松赢得了这个游戏，不由得松了一口气。但是面试者往往会稍微修改规则，和你再玩下去：
1．若规定最后取光石头的人输，又该如何应对呢？这个问题才是面试者真正想考察的。
2．若两个人轮流取一堆石头，每人每次最少取1块石头，最多取K块石头，最后取光石头的人赢得此游戏。
本题其实上是“拈”（NIM）游戏的一种变形，本书中有关“拈”游戏的趣题还有两题，这道题目仅仅是热身而已。