取石子游戏问题”的几种变形及其解法探讨长沙市雅礼中学 朱全民 Bash Gameß问题描述：问题描述：只有一堆n个石子，两个人轮流取石子，规定每次至少取1个，最多取m个最后取光者得胜 分析1.n = m+1时，先手显然必败2.n = (m+1)x+y时，先手先取y个，若对手取k个则先手再拿走m+1-k个3.总能保证n能被(m+1)整除，所以最终先手必胜当y为0时，后手必胜 实例ßn = 7,m = 3ß(x,y)表示当前石子数和下次拿走的石子数ß(7,3)->(4,y)->(4-y,4-y):先手获胜ßn = 8, m = 3ß第一步无论先手去什么，后手总可以将石子数变为4，无论先手再下步取什么，后手总能将剩下的石子一次取完 问题变形ß(SLPC2009)ß只有一堆n个石子，两人轮流取石子，规定每次取1到20个后手的策略是：如果当前石子数小于等于20个则全部拿走，否则若先手取了k个，则后手取ak个最后取光者得胜先手是否有必胜策略？ 分析ßn不被21整除 ：使用同样策略，必胜ßn被21整除：Þn=21,必败Þ存在某个k，使得k + ak不被21整除 ：第一步拿掉k个，然后对方会拿掉ak个，剩下n-k-ak个 ，到达n不被21整除的状态，因此必胜。
Þ其它情况，必败 Wythoff Game ß问题描述：问题描述：有两堆各若干个石子，两个人轮流从某一堆或同时从两堆中取同样多的石子，规定每次至少取一个，多者不限，最后取光者得胜 方法1ß动态规划：ß设f(a , b)表示两堆分别剩a颗和b颗石子时的胜负状态则， f(a ,b) = f(a-k ,b) or f(a ,b-k) or f(a-k ,b-k)ß时间复杂度达到了o(n3) 改进因为，Þf(a , a)，先手必胜Þf(a , b)= f(b , a) Þ当f(a , b)为必败态时，对于所有c≠b, f(a ,c)必胜因此，对于n，所有状态中必败的状态是o(n)级别的，我们可以不断寻找必败态，利用这些状态更新其它状态复杂度为o(n2) 小规模情况ß如果甲面对（0，0），那么甲已经输了，这种局势我们 称为必败态前几个必败态是： （0,0） （1,2） （3,5） （4,7） （6,10） （8,13） （9,15） （11,18） （12,20）ß1=2-1, 2=5–3, 3=7–4, 4=10–6, 5=13–8,ß6=15-9,7=18-11, 8=20-12,……, 结论设第i个必败态为(xi , yi)，有， 思考题ß有三堆石子，分别为a, b, c颗。
有两个人在做如下游戏：游戏者任意拿走其中一堆石子，再在剩下的两堆里任取一堆任意分成两堆（每堆至少1颗）两人轮流如此，谁无法这样做就算输了ß输入格式：有n组数据：每一行三个数a, b, c，满足1≤a,b,c≤1,000,000,000ß输出格式：对应n行：“1”——先手赢；“0”——后手赢 递推设f(a,b,c)表示状态(a,b,c)的胜负：f(a,b,c)=1为胜局，表示先手胜，f(a,b,c)=0为败局ßf(a,b,c)可以递推计算：Þ若存在1≤k≤a-1使得f(k,a-k,b)=0或f(k,a-k,c)=0Þ或存在1≤k≤b-1使得f(k,b-k,a)=0或f(k,b-k,c)=0Þ或存在1≤k≤c-1使得f(k,c-k,a)=0或f(k,c-k,b)=0ß那么f(a,b,c)=1否则f(a,b,c)=0 小规模情况f(a, b, c)必败点如下：Þf(1,1,1)，f(1,1,3)，f(1,3,1)，f(1,3,3)；Þf(2,2,2)；Þf(3,1,1)，f(3,1,3)，f(3,3,1)，f(3,3,3)；Þf(4,4,4)；Þf(5,1,1)，f(5,1,3)，f(5,3,1)，f(5,3,3)；Þf(6,2,2)；Þf(7,1,1)，f(7,1,3)，f(7,3,1)，f(7,3,3)； 找出规律ßa=1,3,5,7，(b ,c)=(1,1),(1,3),(3,1),(3,3),…,ßa=2,6，(b ,c)=(2,2),…,ßa=4，(b ,c)=(4,4),…,ß分析a的特点 ：1）a=1,3,5,7都是奇数，b2）a=2,6是偶数，它只含1个23）a=4是偶数，但它含2个2ß分析b,c的特点 ：b ,c特点直接与a的特点相关。
Nimk游戏 ß问题描述：问题描述：ß两人轮流对N堆石子进行操作，每堆分别有Pi颗每人每次可以从最多K堆中取走任意多颗石子，但至少要取走一颗石子谁取到最后一颗谁胜利什么情况下先手必胜，什么情况下后手必胜 预备知识ß定义：如果一个局面先手必胜，就称之为N局面，反之称之为P局面Nimk问题当K=1时就是经典的Nim问题ßXOR运算为对二进制进行逐位不进位加法（对每一位结果mod 2）ßNim问题的解法是：对于一个局面，令S=P1 XOR P2 XOR P3 XOR … XOR Pn若S=0则为P局面，否则为N局面 证明ß若当P1=P2=….=Pn=0时，S=0，满足终状态是P局面ß若S=0，即P1 XOR … XOR Pn=0，若取堆i中的石子，Pi->Pi’， S->S’，Pi>Pi’，则Pi XOR Pi’<>0所以S’ XOR Pi XOR Pi’=S=0，即S’=Pi XOR Pi’<>0满足P局面的所有子局面都是N局面ß若S<>0，设S的二进制位是A1…An，考虑第一位是1的在P中取出该位同是1的，不妨设为P1可知P1 XOR S
即N局面存在至少一个子局面是P局面 推广到k>1ßK=2ß 3—————— 1 1ß 5—————— 1 0 1ß 10—————— 1 0 1 0ß 15————— 1 1 1 1ß 2 2 0 0 (mod 3)ß所以这是N局面，第一步取10->6 15->7可以到达一个P局面3 5 6 7ß 3—————— 1 1ß 5—————— 1 0 1ß 6 —————— 0 1 1 0ß 7 ————— 0 1 1 1ß 0 0 0 0 (mod 3) MisèreNim ß基本规则同Nim Game问题，胜负判定是谁不能继续取石子，谁就赢了 分析1）所有石子堆的数目都为1：显然，若有偶数堆石子堆，则必胜，否则必败。
2）如果恰好只有一堆石子数目大于1我们可以把这堆石子取完或者取得只剩下1，使得只剩下奇数堆数目为1的石子留给对方，由1)，必胜3）如果有至少2堆石子的数目大于1考虑⊕值：若⊕值不为0，则按照NimGame走法取石这样，当对手某次取完石子后，肯定会出现2）的情况，则必胜 证明ß按照NimGame法则取完石子后，必定会给对手留下⊕值为0的局面因此不可能给对手留下2）的局面（容易证明，2）局面的⊕值肯定不为0），而对手一次最多将一堆石子数大于1的石子堆处理掉因此2）的情况肯定会出现ß相反，若⊕值为0，则无论如何走都会给对方留下2）或3）的情况，必败 实例ßn = 4, {1,1,2,2}ß第一步若拿掉一堆为2的石堆，则只剩一堆>1的石堆ß若拿掉一堆为1的石堆，对方也拿掉一堆为1的石堆，无论我们接下来怎么取，都只剩一堆>1的石堆ß在一堆为2的石堆中拿掉一颗石子，只剩一堆>1的石堆ßn = 4,{1,1,2,3}ß我们可以在3的石堆中拿掉一颗石子，变为一个xor值为0的必败状态，所以必胜 A stone gameß一堆石子有n颗，两个人轮流从中取石子，第一个人第一步最多取n-1颗，接下来每一步，假设上一步取了x颗，当前取石子的人最多可以取k*x颗，当然一个人不能一颗石子也不取。
取走最后一颗石子的人获胜假设两个人都使用最优策略，请问对于给定的n,k先手能否获胜？ 分析 ß定义x为绝对必败态，当且仅当无论何种情况下只要走到了这个状态，那么先手必然失败的状态 ß假设前1..i-1个绝对必败态p[1]..p[i-1](p[1]=1)ßp[i-1]+1,p[i-1]+2,…,p[i-1]+m都是必胜态的充分条件是：k*m
而128 = 115 + 13 则成为了必败态，因为无论是转移到127还是126它都使下一个状态必胜，这里的p[j] = 13 , p[i-1] = 115 ,所以 p[i] =128 SGU429ß有n堆石子，将这n堆石子摆成一排游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了ß问：对于任意给出一个初始一个局面，是否存在先手必胜策略 分析ß设fleft[l][r]表示对于Al,…Ar当Al取多少时（其余的A值不变），这个状态是必败的同理可设fright[l][r] ß只考虑(Al,Ar)的组合，我们说(X,Y)是个必败态当且仅当X,Al+1,..,Ar-1,Y是一个先手必败的状态 分析ß首先得到2个初始的必败态，即(0,fright[l+1][r])和(fleft[l][r-1], 0),同时必败态应满足以下条件：ß每行有且仅有一个必败态ß每列有且仅有一个必败态ß这是因为如果（p,x）,(p,y)都是必败态，不妨设x<=y,那么(p,y)可以转移到（p,x）去，矛盾 计算ß设L=fleft[i][j-1]，R=fright[i][j-1]，x=Aj，则fleft [i][j]由以下方式确定：不妨设L≥R，Þ当xL时，fleft[i][j]=x。
ß同理可确定fright[i][j] 实例ßfright[l+1][r]=8，fleft[l][r-1]=6ß失败状态为：(0,8),(6,0),(1,1),(2,2),..,(7,6),(8,7),(9,9),(10,10) SPOJ4060 ß有n个石子放成一堆A和B轮流操作，A先手操作为投掷一枚硬币，如果正面朝上、则从石子堆中取出一枚石子A有P的概率投出他想投的面，B有Q的概率投出他想投的面P,Q≥0.5）问A赢的期望 分析ßA先手，双方都希望投正面，A，B得到石子的概率分别是：PR1 = p/(1-(1-p)(1-q)); （等比求和）PR2 = (1-p)q/(1-(1-p)(1-q))ßB先手，双方都希望投正面，A，B得到石子的概率分别是：PR3 =(1-q)p/ (1-(1-p)(1-q)) PR4 = q/(1-(1-p)(1-q));ß 分析ßA先手，双方都希望投反面，A，B得到石子的概率分别是：ßPR5 = (1-p)/(1-pq);ßPR6 = P(1-q)/(1-pq);ßB先手，双方都希望投反面，A，B得到石子的概率分别是：ßPR7 = q(1-p)/(1-pq);ßPR8 = (1-q)/(1-pq); 分析ß设f[n]表示剩n个石子，A先手，A获得胜利的概率，g[n]为B先手，A获得胜利的概率。
ßf[n-1] >= g[n-1]时，双方都希望投反面（都希望下步自己先手），ß f[n] = PR6*f[n-1] + PR5*g[n-1]ß g[n] = PR8*f[n-1] + PR7*g[n-1]ßf[n-1] < g[n-1]时，ß f[n] = PR2*f[n-1] + PR1*g[n-1]ß g[n] = PR4*f[n-1] + PR3*g[n-1] Staircase Nim ß问题描述：问题描述：ß游戏开始时有N堆石子排成一排，从左至右编号为1到n游戏者在每次操作时可以将编号为j(1<=j<=n)上的1个以上的石子移动到编号为j-1的石子堆上游戏者轮流操作，将最后一枚石子移至编号为0的石子堆的人获胜 一个很有趣的性质ß偶数编号堆中的棋子个数不会影响局面的输赢状态因为如果一个棋手将一些棋子从偶数编号堆移到奇数编号的堆中，那么他的对手总是可以将相同数目的棋子从这个奇数编号的堆中移动到编号更小的偶数编号堆中移动偶数编号堆中的棋子并不会让对手无法移动因此，一旦有棋子从奇数编号的堆中移动到偶数编号的堆中，那么这些棋子是不会影响局面的胜负状态的。
结论ßStaircase Nim中的一个局面(H0, H1, …Hm)是先手胜局面，当且仅当其奇数编号棋子堆在Nim游戏中是一个先手胜局面ß因为根据上面的分析可知，在Staricase Nim中从奇数编号的堆中移动一些棋子到偶数编号的堆中，相当于在Nim游戏中将一些棋子从堆中拿走因此判断Staircase Nim的一个局面是否是先手必胜局面，只需要判断奇数堆异或是否大于0，如果大于0，那么先手必胜，否则先手必败 Take&break ß问题描述：问题描述：有n堆石子，每次可以拿走一堆石子，然后放入两堆规模更小的石堆（可以为0），谁不能继续操作就输了 分析ßf[i]表示还剩一堆i颗的石子堆的状态，f(i,j)表示两堆的状态，依次类推ß根据SG函数的定义有f[i] = min{n∈N | n ≠ f (p,q) for i > p≥ 0 且 i > q ≥ 0}ß我们可以递推求得子游戏任意状态的SG函数值用SG定理可以求得和游戏的任意状态的SG函数值 思考题 ß如果多堆的nimk游戏，第2k次操作只能拿走偶数标号堆的石子，第2k+1次操作只能拿奇数标号堆的石子问题要如何解决？ß如果例题1中的堆数扩展到m堆，问题要如何解决。
ß想出几个关于take&break模型的转化问题ACM ICPC 2006 beijing a funny stone game是个经典的此问题的转化）ß想出几个关于staircase nim模型的转化问题如POI2006 Stage） A Funny Stone Gameß David 玩一个石子游戏游戏中，有n堆石子,被编号为0..n-1两名玩家轮流取石子每一轮游戏，每名玩家选取3堆石子i, j, k (i