转载请注明出处:http://www.klion.0fees.net/?p=6
Dynamic subtraction.
One can enlarge the class of subtraction games by letting the subtraction set depend on the last move of the opponent.Many early example sappear in Chapter12 of Schuh(1968).Here are two other examples.(For a generalization,see Schwenk(1970).) (a)There is one pile of n chips.The first player to move may remove as many chips as desired,at least one chip but not the whole pile.There after,the players alternate moving,each player not being allowed to remove more chips than his opponent took on the previous move.What is an optimal move for the first player if n =44?For what values of n does the second player have a win?
题目大意: 有一堆石子,个数为n,两个人轮流,规则如下 第一个取石子的人至少取一个,至多取n-1个。之后每个人不能比前一个人刚取过的石子数多.没得取了算输,
对于这个我们对比较小的n归纳可知,如果n=2^k(k >=0)的话则是P态,否则是N态. 首先我们可以看到1是P态(先手无法取,因为不能取完),2是P态(只能取1个,后手取剩下的一个) 所有的奇数都是N态,因为每次取一个的话,最后只剩下1颗石子的时候一定是由先手取,所以所有的奇数是N态. 如果是偶数的话,第一次取的石子数不能超过一半,而且必须取偶数.如果取奇数个的话,则后手变成了N态,如果取超过一半的石子数的话,那么后手可以一次取完.先手也输了. 所以4是P态 6只能取2,然后后手达到4这个P态,所以先手必输。 下面我们证明当n = 2^k时为P态, 首先i = 0,1,2时结论成立。现在假设n = 2^i(i>=1)时结论成立,令j = i+1;m = 2^j; 我们知道先手第一次取的石子数一定是小于2^i次的,而且从2^j到2^i和2^i到2^j是一样多的数目. 于是我们可以看成先手可不可能通过取走一些石子使得后手处于2^i.其实这样是不可能的,分析如下: 我们把2^j到2^i这些数都同时减去2^i,我们得到2^i,2^i-1,……,1,0,这样就变成了一个2^i的取石子游戏了.我们可以知道在这里先手是必输的(本文如没有特殊说明,则意味着两个选手都按最优的方案执行)。首先我们得到2^(i-1)次,如果先手取的石子数比这个多的话,那么后手可以取走一定的数目使得先手处于2^i这个P态.也就是说先手必输,如果先手取走的数目比2^(i-1)少的话,那么可以得到取完2^j到2^i+1这个2^i个的时候先手也是必输的,也就是说在这个过程中后手同样可以使得先手处于2^i这个P态,这样的话先手必输,所以无论先手怎样取石子,对于n=2^k(k>=0)必输。 这样的话,易知对于n != 2^k(k>=0)的先手必胜。