投石子游戏

来自计算思维百科
跳转至: 导航搜索
投石子游戏.jpg

有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。举个例子,比如给出两堆石子的数目是2、1,那么你是败者,因为如果你只拿走两个石头的一个,那么对方同时拿走一个就赢了,如果你同时拿走一个,那么还剩下一个,对方拿走最后一个就赢了。

那么现在有两堆石头,一堆有8个石头,另一堆有13个石头,你先取,判断谁输谁赢?

解决方案

首先考虑哪些情况是一定输的(称为必败态),比如(0,0)那么你一定输了,因为别人已经取完了所有的石头;此外还有(1,2),因为如果你只拿走第一堆的最后一个石头,对方只需要拿走第二堆的2的石头就获胜了,如果你只拿第二堆的一个石头,那么对方只需从两堆拿走一个石头就获胜了。所以(1,2)是必败态。我们可以再推敲出一下几个必败态:

(3,5)、(4,7)......我们发现第K个必败态为(a,b),其中a是前面未出现过的最小自然数,b=a+k;所以8是第5个必败态,13=8+5;所以如果遇到(8,13)的局势是一定输的。

运用的计算思维

其实这是我国民间很古老的一个游戏,别看这游戏极其简单,却蕴含着深刻的数学原理。,可以用威佐夫博奕的理论来做,威佐夫博弈的问题是有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。穷举法是很难判断输赢的,因为物品数量可能很大。所以我们应该从一些比较简单的特例中发现规律,从而把问题解决,体现了一种学习的计算思维。