当前位置: 代码迷 >> 综合 >> Bash博弈
  详细解决方案

Bash博弈

热度:75   发布时间:2024-01-25 06:35:55.0

例题:有一堆n个石子。AB两人轮流拿石子,且A先拿。如果某人没有石子可以拿则他输。每个人能拿的石子最少为1,最多为k。假设A和B都很聪明且不会有失误,请问谁能赢。

这是Bash博弈中的最基础的模型。

因为每次拿的石子数的取值区间都在 $ [1,n] $ 之间,所以我们可以考虑将每一轮取走的总石子数控制在(n+1)个,此时无论对面每次拿走多少我都可以把局势扳回到取走之前的样子。

然后事情就变得很简单了,我们只要控制每次我们拿走后石子的总数量刚好可以被(k+1)整除

比如说 $ n=p*(k+1)+r $,A先手拿走r个石子

然后b假如拿走了t个石子,我就可以拿走(k+1-t)个石子,这样就又回到了石子总数被(k+1)整除的局势。

然后显然b是不能拿走k+1个石子的,所以我们必赢。

所以综上所述  关于这个问题,我们只需要判断这堆石子的总数是不是被(k+1)整除,如果被整除,则先手必输,否则先手必赢。

此处附一道练手题:Bash博弈

  相关解决方案