首页 > 代码库 > 巴什博弈
巴什博弈
们从一道小学奥数题讲起。
甲乙轮流报数至多报 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),接下来每一步随机应变,就可以取得胜利。
巴什博弈
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。