巴什博弈|你总能赢

巴什博弈一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,至多取m个,最后取光者得胜。就针对这个问题,讨论先取(物品)玩家是否能获胜。为了方便说明,先取玩家和后取玩家都很有头脑。

假设1:如果n<=m,那么先取玩家可以一次取光所有的物品,获胜;

假设2:如果n>m,那么设n=a(m+1)+b,其中a>0,b<=m+1。

:假设2.1:如果b==m+1,那么n=(a+1)(m+1),此时先取玩家已回天乏力,因为先取玩家取玩过后,后取玩家会故意给先取玩家留下(m+1)倍数个物品,直到取光所有的物品为止(即倍数为0),所以先取玩家输定了。

:假设2.2:如果b<m+1,那么先取玩家可以先取b个物品,故意留下a(m+1)个物品;在以后的每一轮中,先取玩家都会故意留下(m+1)倍数个物品给后取玩家,直到去光所有物品为止(即倍数为0),所以先取玩家获胜。

if n <= m
	先取玩家获胜;
if n%(m+1) > 0
	先取玩家获胜;
else
	后取玩家获胜;

并不像标题表述的那样,在这样的问题你作为先取玩家总能获胜,但如果明白这个问题,而“后取玩家很有头脑”假设又不总成立,所以先取玩家获胜的几率很大。

本文完 2012-10-2

捣乱小子 http://www.daoluan.net/

02 October 2012

disqus 可能被墙~