轉載請注明出處: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 ?rst 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 ?rst 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時結論成立?，F在假設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)的先手必勝。