本帖最后由 hbghlyj 于 2019-8-10 10:23 编辑
Nim游戏:有n堆石子,每堆石子的个数分别为$a_1,a_2…a_n$.甲乙两人进行取石子的游戏,甲先开始轮流操作,规定每人每次可以选定其中一堆石子,然后在此堆石子中取若干块石子,每次不能不取.能不取.取到最后一块石子者为胜,在什么情况下,甲有必胜策略?
解:将$a_1,a_2…a_n$都表示为二进制${a_i} = \overline {{b_{ik}}{b_{ik - 1}} \cdots {b_{i1}}{b_{i0}}} $,其中$b_{ij}=0,1$,为了位数统一,允许某些$b_{ik}=0.$令$c_j=a_{1j}+a_{2j}+…+a_{nj},0\leq{}j\leq{}k,$即$c_j$为这个数第j位数字之和.我们以下证明:当且仅当所有$c_j$不全为偶数时,甲有必胜策略.
证明:当$c_j$不全为偶数时,不妨设$c_{r_1},c_{r_2},…,c_{r_t}$是其中全部奇数且$r_1>r_2>…>r_t.$由于$c_{r_1}\geq{}1$,必有一个$a_s$使得$b_{{sr_1}}=1$,取$d=\overline{d_kd_{k-1}…d_1d_0}$,其中当$j\not=r_1,…,r_t$时,$d_j=d_{sj}$;当j=$r_1,…,r_t$时,$d_j=1-b_{sj}$
,由于$b_{{sr_1}}=1>0=d_{r_1}$,故$a_s$$>$d,所以甲可以从第s堆中取出$a_s$-d块石子.这样第s堆还剩下d块石子.由d的定义,取完以后$c_j$全变为偶数.
轮到乙取时,$c_j$全变为偶数,假设他在第t堆中取,无论他取多少,都会将$a_i$中的某个$b_{ij}=1$变为$b_{ij}$=0(如果所有的1都不变,则这堆石子没有减少,但是我们规定不能不取)这样相对应的$c_j$变为$c_j-1$,由偶数变成了奇数。
我们将所有$c_j,j=1,2,\cdots,k$都是偶数的状态称为理想状态。综上所述,如果开始不是理想状态,则甲总是可以通过一次操作将之变为理想状态。另一方面,当乙面对理想状态进行操作时,他必然会破坏理想状态。也就是说甲每次取完后肯定是理想状态,乙每次取完后都不是理想状态。而获胜时,所有的$b_{ij}$=0,当然所有的$c_j$=0,也就是说获胜的一方取完后应该是理想状态,加之石子总数不断减少,必然会有人获胜。因此这样进行下去,甲必然获胜。 |