学习笔记 斐波那契博弈

斐波那契博弈

有一堆个数为n的石子,A,B轮流取石子,满足:

(1)先手不能在第一次把所有的石子取完

(2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间
(包含1和对手刚取的石子数的2倍)

同之前的不同点就是:取的规则动态化

约定取走最后一个石子的就是赢家


就连我看博弈名都知道 这必须要使用斐波那契数列

这里需要借助齐肯多夫定理:(证明自己看)

任何正整数可以表示为若干个不连续的斐波那契数之和

对于所有的正整数适应

首先给出3个定理

1$.fib_{n+1}<fib_n*2<fib_{n+2} $这个应该可以明白

(fib_{n+1}=fib_n+fib_{n-1})

并且$fib_n>fib_{n-1} $

$fib_n*2>fib_{n+1} $

同理

(fib_{n+2}=fib_n+fib_{n+1})

并且$fib_{n+1}>fib_n $

所以(fib_{n+2}>fib_n*2)

2.(fib_{n+2}<fib_n*3)

( fib_{n+2})
(=fib_{n+1}+fib_n)
(=fib_n+fib_{n-1}+fib_n)
(=fib_n*2+fib{n-1})
且$fib_{n-1}<fib_n $

所以$fib_{n+2}<fib_n*3 $

3.(3*fib_{n+1}>4*fib_n)

也就是(3*fib_{n-1}>fib_n) 由定理2 成立

数学归纳法证明:

1.若当前只有一颗也就是(i=2) 先手只有一颗可取

显然是必败 成立

2.假设所有(i<=k)均成立

那么(i=k+1)(fib_i=fib_k+fib_{k-1})

那么把石子分为两堆 (fib_k)以及(fib_{k-1})

首先 先手绝顶聪明的话取得石子数一定(<fib_{k-1})

因为(fib_k<fib_{k-1}*2)

对于当前小堆(fib_{k-1})一定可以明白的是

根据假设无论先手如何取 后手总是可以取到最后一颗

分析一下后手最后去了(x)

若先手第一次取了$y>=frac{fib_{k-1}}{3} $

那么剩余小堆(<=2y) 后手可以直接取光

(x=fib_{k-1}-y<=frac{2*fib_{k-1}}{3})

我们比较一下(frac{2*fib_{k-1}}{3})以及(frac{fib_k}{2})

也就是(4*fib_{k-1})以及(3*fib_k)

由定理3可得 后者大于较大

所以先手无法一次性取光(fib_k)这一堆

那么根据之前结论 后手必胜

若先手第一次取了$y<frac{fib_{k-1}}{3} $

由于(fib_{n+2}<3*fib_n)

所以(y<fib_{k-3})

那么感性的理解一下 后手总是可以取走一些石子

然后使先手面临(fib_{k-2})的局面 这样的话后手还是可以取走最后一个

这样的话还是先手必败

所以(i=k+1)时 结论依然成立


不是(Fibonacci)数列时 先分解

分解时尽量取较大(Fibonacci)

例如分解85:

(55<=85<=89)所以就是(85=55+30)

以此类推就是(85=55+21+8+1)

(n=fib_{p_1}+fib_{p_2}+fib{p_3}+......+fib_{p_k}(p_1>p_2>p_3>......>p_k))

又因为各个(fib)之间不连续

所以(p_{k-1}>p_k+1) 所以(fib_{p_{k-1}}>fib_{p_k}*2)

先手先取走(fib_{p_k})

那么后手只可以取(fib_{p_{k-1}})并且不可以取完

那么后手面临这个子问题

(fib_{p_{k-1}})并且是后手先取

那么由上可得先手一定可以取走最后一颗

同理对于以后的每一堆都是如此

得证

模板题

HDU2516

原文地址:https://www.cnblogs.com/LovToLZX/p/13757902.html