事实上我也不知道这算是哪个类型的博弈

是在复习$NOIP$初赛的时候看到的一个挺有趣的博弈

所以就写出来分享一下

 

$upd \ on \ 2018.10.12$忽然发现这个其实就是$Fibonacci Nim$...

 

题目:有n张纸牌,A,B两人轮流按照以下规则取牌。

规则一:A先取,但是不能在第一次将纸牌全部取完,而且至少要取一张;

规则二:每次所取纸牌张数必须大于或等于1,且小于等于对手刚取的纸牌张数的两倍。取到最后一张牌者为胜者。

输入纸牌的张数n,判断A是否必胜,如果必胜,输出”win”,否则输出”lose”。

 

问题分析:当n较小时,可以归纳如下:

⑴2张牌时,先拿的人必输;

⑵3张牌时,先拿的人必输;

⑶我们先看5张牌的情况,假如我们把取5张牌分成两个步骤:先取前面2张,再取后面3张,为什么可以这样分成两个步骤?因为后取者有这个权力!先者只能取第一张,后者可以取到第二张,这样,后者就必可以取到第5张牌,先者必输。

同样,如果是8张牌时,可以分为:先取前面3张,再取后面5张,后者胜,先者必输。

结论:⑴如果牌的张数$n$是$Fibonacci$数时,先取牌者必败。 ⑵对所有非$Fibonacci$数都是先取人必赢,反之,必败。


下面给出一般性证明:

假设$n<=k$,且牌数为$Fibonacci$数时,都是取牌者必输。

那么$n=k+1$时,因为$F(k+1)=F(k)+F(k-1)$,即要取完$F(k+1)$张牌,可以分成两步:先取完$F(k-1)$张牌,再取完$F(k)$张牌。对于$F(k-1)$张牌,先取A者输!意味着对于$F(k)$张牌,A还得必须先取,所以A输。

那么,牌数为非$Fibonacci$数时,先取牌者有没有必胜的策略呢?

引用一个定理:当一个数不是$Fibonacci$数时,这个数必然等于若干个$Fibonacci$数之和,并且这些$Fibonacci$数在$Fibonacci$数列中都不相邻。

比如:$78=55+23=55+21+2$(其中55,21,2都是$Fibonacci$数);

对于非$Fibonacci$数$a0$,设f(n)是小于4a0$的最大$Fibonacci$数。

$a0=f(n)+…+f(i)+f(j)$,其中$f(j)$是式中最小的$Fibonacci$数,$f(i)$是第二小的$Fibonacci$数。由于$f(i)$、$f(j)$在$Fibonacci$数列中并不是相邻的,所以$f(i)>2*f(j)$。所以先取者可以直接取走$f(j)$张牌,后取者无法一次取走$f(i)$张牌,$f(i)$是$Fibonacci$数,由前面的分析,后取者必败。

结论:对所有非$Fibonacci$数都是先取人必赢,反之,必败。