有一堆硬币,开始时有9枚。A、B两人轮流从中取硬币,每次取硬币时,可以取1枚或者2枚或者3枚,拣起最后一枚硬币者为输方。试用博弈树证明;后开始取硬币者总能获胜,或者先开始取硬币者总是会输。
时间: 2023-06-25 08:04:02 浏览: 110
这个问题可以用博弈树来分析。
首先,我们把硬币数量作为根节点,9个硬币是初始状态。然后,我们列出所有可能的决策,也就是A和B可以拿1个、2个或3个硬币,因此根节点下面有3个子节点,分别表示拿1、2、3个硬币。
接下来,我们对每个子节点重复相同的过程,列出所有可能的决策,直到最后只剩下1个硬币。因为无论是A还是B拿最后1个硬币,都会输掉比赛。
在博弈树中,叶节点表示游戏结束的状态,而非叶节点表示的是游戏的中间状态,这些中间状态可以通过反复的考虑转移到叶节点上。
通过分析博弈树,我们可以发现,在初始状态下,无论A和B如何取硬币,最后一个硬币一定是B拿到的,因此B是必输的。反过来,如果先开始取硬币的一方(也就是A)总是会输,那么初始状态下,无论A如何取硬币,最后一枚硬币都应该是A拿到,这是矛盾的。
因此,先开始取硬币的一方总是能获胜,而后开始取硬币的一方总是会输。
相关问题
用c++写一个程序,有一堆硬币,开始时有9枚。A、B两人轮流从中取硬币,每次取硬币时,可以取1枚或者2枚或者3枚,拣起最后一枚硬币者为输方。试证明;后开始取硬币者总能获胜,或者先开始取硬币者总是会输。
这是一个经典的博弈问题,可以用数学归纳法来证明。
首先考虑硬币数为1、2、3的情况,显然后手必胜。
当硬币数为4时,先手无论拿几枚硬币,后手都可以将剩下的硬币取完,所以先手必败。
当硬币数为5、6、7时,先手可以先取1/2/3枚硬币,然后根据上述情况,后手必败。
当硬币数为8时,先手无论拿几枚硬币,后手都可以将剩下的硬币取完,所以先手必败。
当硬币数为9时,先手可以先取1/2/3枚硬币,然后根据上述情况,后手必败。
综上所述,先开始取硬币的人在任何情况下都可以获胜。
2021枚硬币,小张小王轮流取
假设小张先取,每次最多可以取的硬币数为5枚,问小张是否有必胜策略?
这个问题可以通过数学方法来解决。我们先看一下比较简单的情况,如果只有100枚硬币,每次最多取5枚,那么小张可以通过以下策略保证必胜:
1. 如果剩下的硬币数模6等于1或2,小张先取1或2枚,然后每次取硬币数与对手取的上一次硬币数之和为6,这样小张一定可以在最后一次取完后取到最后一枚硬币。
2. 如果剩下的硬币数模6等于3或4或5,小张先取4或3或2枚,然后每次取硬币数与对手取的上一次硬币数之和为6,这样小张也可以在最后一次取完后取到最后一枚硬币。
接下来我们考虑2021枚硬币的情况。我们可以先通过模6来进行分类讨论:
1. 如果剩下的硬币数模6等于1或2,小张可以采用与100枚硬币相同的策略,即先取1或2枚,然后每次取硬币数与对手取的上一次硬币数之和为6。
2. 如果剩下的硬币数模6等于3,小张可以先取2枚,然后每次取硬币数与对手取的上一次硬币数之和为6。这样小张可以在最后一次取完后留下4枚硬币,从而取胜。
3. 如果剩下的硬币数模6等于4,小张可以先取1枚,然后每次取硬币数与对手取的上一次硬币数之和为6。这样小张可以在最后一次取完后留下3枚硬币,从而取胜。
4. 如果剩下的硬币数模6等于5,小张可以先取4枚,然后每次取硬币数与对手取的上一次硬币数之和为6。这样小张可以在最后一次取完后留下1枚硬币,从而取胜。
5. 如果剩下的硬币数模6等于0,小张可以先取5枚,然后每次取硬币数与对手取的上一次硬币数之和为6。这样小张可以在最后一次取完后留下1枚硬币,从而取胜。
因此,小张有必胜策略。