首页 > 代码库 > 巴什博弈

巴什博弈

们从一道小学奥数题讲起。

甲乙轮流报数至多报 7 个数,至少报 1 个数,从 1 开始,谁先报到 50 谁就胜利。甲先报,有无必胜策略?

甲有必胜策略,先报 2 个数;接下来乙报 x 个数,甲都会报 (8-x)(8−x) 个数。因为8∣48,故一定是甲先报到 50。

同理,在巴什博奕中,当物品的总量 n=(m+1)r+s(r 为任意自然数,s≤m≤m) 时,先取的人先拿走 s个物品,当后取的人拿走 k 个时,只要先取的人再拿走(m+1−k) 个物品,使得剩下的物品总量为(m+1)(r−1),并且在之后一直维持这个取法,使得给对手剩下的物品数量是 (m+1)的倍数,就一定能获得胜利。当然,如果物品的总数 n=m+1,那无论先拿的人先取走多少个,后拿的人都一定能拿走剩余的全部物品取得胜利。

综上,只有 n=0(mod(m+1)),即 n 被 (m+1) 整除时,后手必胜;否则,先手第一步取 n \% (m+1),接下来每一步随机应变,就可以取得胜利。

 

巴什博弈