轉(zhuǎn)載請(qǐng)注明出處: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?

題目大意: 有一堆石子,個(gè)數(shù)為n,兩個(gè)人輪流,規(guī)則如下 第一個(gè)取石子的人至少取一個(gè),至多取n-1個(gè)。之后每個(gè)人不能比前一個(gè)人剛?cè)∵^(guò)的石子數(shù)多.沒(méi)得取了算輸,

對(duì)于這個(gè)我們對(duì)比較小的n歸納可知,如果n=2^k(k >=0)的話則是P態(tài),否則是N態(tài). 首先我們可以看到1是P態(tài)(先手無(wú)法取,因?yàn)椴荒苋⊥?,2是P態(tài)(只能取1個(gè),后手取剩下的一個(gè)) 所有的奇數(shù)都是N態(tài),因?yàn)槊看稳∫粋€(gè)的話,最后只剩下1顆石子的時(shí)候一定是由先手取,所以所有的奇數(shù)是N態(tài). 如果是偶數(shù)的話,第一次取的石子數(shù)不能超過(guò)一半,而且必須取偶數(shù).如果取奇數(shù)個(gè)的話,則后手變成了N態(tài),如果取超過(guò)一半的石子數(shù)的話,那么后手可以一次取完.先手也輸了. 所以4是P態(tài) 6只能取2,然后后手達(dá)到4這個(gè)P態(tài),所以先手必輸。 下面我們證明當(dāng)n = 2^k時(shí)為P態(tài), 首先i = 0,1,2時(shí)結(jié)論成立。現(xiàn)在假設(shè)n = 2^i(i>=1)時(shí)結(jié)論成立,令j = i+1;m = 2^j; 我們知道先手第一次取的石子數(shù)一定是小于2^i次的,而且從2^j到2^i和2^i到2^j是一樣多的數(shù)目. 于是我們可以看成先手可不可能通過(guò)取走一些石子使得后手處于2^i.其實(shí)這樣是不可能的,分析如下: 我們把2^j到2^i這些數(shù)都同時(shí)減去2^i,我們得到2^i,2^i-1,……,1,0,這樣就變成了一個(gè)2^i的取石子游戲了.我們可以知道在這里先手是必輸?shù)?本文如沒(méi)有特殊說(shuō)明,則意味著兩個(gè)選手都按最優(yōu)的方案執(zhí)行)。首先我們得到2^(i-1)次,如果先手取的石子數(shù)比這個(gè)多的話,那么后手可以取走一定的數(shù)目使得先手處于2^i這個(gè)P態(tài).也就是說(shuō)先手必輸,如果先手取走的數(shù)目比2^(i-1)少的話,那么可以得到取完2^j到2^i+1這個(gè)2^i個(gè)的時(shí)候先手也是必輸?shù)?也就是說(shuō)在這個(gè)過(guò)程中后手同樣可以使得先手處于2^i這個(gè)P態(tài),這樣的話先手必輸,所以無(wú)論先手怎樣取石子,對(duì)于n=2^k(k>=0)必輸。 這樣的話,易知對(duì)于n != 2^k(k>=0)的先手必勝。