`
datoplay
  • 浏览: 1614337 次
文章分类
社区版块
存档分类
最新评论

是男人就过8题--A New Stone Game(博弈论之SG函数)

 
阅读更多

题意：小明和小红参加一种新的取石子游戏。游戏开始时有 n 堆石子，参与游戏的两个选手轮流取走和移动石子，游戏从小明开始。在每一轮中，选手选择一个至少有一颗石子的堆，从该堆石子中拿走至少一个石子。接着，该选手可以多次地从该堆中剩下的石子中把任意多的个石子移动到任意的堆中。当然，该选手也可以不移动任何石子。但是，必须注意，选手必须从该选中的堆中取起至少一块石子。因此，随着游戏的进行，石子越来越少。当轮到某选手时，已经没有石子可以取走时，该选手输掉了游戏。小明和小红都极其聪明，总能以最优的策略进行游戏。现在，给定堆数 n 和每一堆的石子数目，请问小明能在游戏中否获胜？

本题中的游戏是一种impartial game，应用Sprague-Grundy定理，可以计算出一些必败状态，从而获得关于一般必败状态的规律。不过，本文打算就题论题，而不涉及较深的博弈理论。

先从 n = 1 开始考虑。这时，小明可以把该堆的所以石子取走，从而必胜无疑。

假设 n = 2。若用 (x,y) 表示某一轮中两堆石子的数目（总假定 x <= y），则 (x,y) 也可以看成游戏中的一个状态。最终态为 (0,0)。这时，轮到的选手落败。当轮到小明时，若此时的状态为 (0, x) 且 x>0，则问题化为 n=1的情况，从而小明必胜。进一步考虑复杂些的状态，例如 (1, x), x>= 1。当 x=1 时，小明必输。其实当状态为 (x,x) 型时（两堆石子数目相同），小明都必败，因为，无论小明如何取走和移动石子，小红都可以通过取走合适数目的石子，把状态重新调整为 (y,y)型。同时也容易看出，若为其它类型的状态，则小明必胜。

再考虑 n = 3。如果小明可以通过取走和移动石子把状态调整成 (0,x,x) 型，则小明可以获得最终的胜利。事实上，小明确实可以做到。证明如下：假设当前状态为 (x,y,z)，并不失一般性，假设 x<=y<=z。则 y-x < y <= z。通过在 z 堆中取走 z-(y-x) >= 1 个石子，并把 y-x 个石子移动到 x 堆上，可以把状态 (x,y,z) 转换成 (0,y,y)。

看来，两堆石子数目相同是个很特殊的状态。然而，现在尚不清楚，对于更多的堆，情况是如何的。于是，接着考虑 n = 4。显然，(1,1,1,1) 是必败状态，(1,1,2,2) 也是如此。可以猜测当小明面对 (x,x,y,y) 型状态时必败。要证明这是必败状态，则需要证明，无论采用什么策略，小明结束该轮之后，状态不是 (x,x,y,y) 型，并且，小红可以在接下来的一轮中，把状态重新调整成 (x,x,y,y) 型。这样，小明最终会被逼面临 (0,0,0,0) 这个终态，从而输掉游戏。简单的思考可以验证" (x,x,y,y)型状态是小明的必败状态" 这一结论。

现在，要把上述的结论推广到任意数目的堆。当 n 为偶数时，我们把状态(x1,x1,x2,x2,...,xm,xm)，即，当有偶数堆，并且可以把这 n 堆分成 n/2 组，每组由两个石子数目相同的堆组成的状态，称为目标状态。现在我们证明，目标状态是小明的必败状态；而其它状态是他的必胜状态。

引理一：当 n 为偶数，且选手面临目标状态，则无论选手采取何种策略，在结束该轮之后的状态一定不是目标状态。

证明：用反证法。假设命题不成立。则结束该轮之后的状态可以写为 (y1,y1,y2,y2,...,ym,ym)，不失一般性，假设 y1<=y2<=...<=ym和x1<=x2<=...<=xm。考虑分组 {xk,xk}中的两个堆。其中至少有一个堆不是被选手选中的堆。显然，这个堆对应(y1,y1,y2,y2,...,ym,ym) 中的某个分组 {yt,yt}中的某个堆。同时，因为这个堆没被选中，其石子的数目不会减少，因此，yt>=xk。由于(x1,x1,x2,x2,...,xm,xm) 和(y1,y1,y2,y2,...,ym,ym) 中的堆存在一一对应的关系，从而对每个 xk，惟一对应着一个yt，并且 有xk<=yt。这说明，2(x1+x2+...+xm) <= 2(y1+y2+...+ym)，即结束该轮后，总的石子数目不减。但这是不可能的。证毕。

注：在上述证明中，可以证明更强的结论：对所有 k， 成立xk<= yk。

引理二：当选手面临的状态不是目标状态时，总是可以采取某个策略，使得该轮结束后，状态为目标状态。

证明：不妨假设面临的状态为 (x1,x2,...,xn)，x1< x2< ... < xn（若有两个数目相同的堆，则无须对它们进行任何操作，因此，可以把任何两个数目相同的堆排除在考虑之外）。当 n=2m 偶数时，选择堆 xn，并进行如下操作：把x2k+1-x2k个石子移到堆x2k，1<=k<= m-1。这样，总共需要从堆 xn中移出 M=(x3-x2)+(x5-x4)+...+(x2m-1-x2m-2)<xn-x1。接着，取走 xn-M-x1>0 个石子。当 n = 2m+1 为奇数时，同样选择堆 xn，并进行如下操作：把 x2k-x2k-1个石子移动到堆 x2k-1，1<=k<=m。这样，总共需要从堆 xn 中移出 M=(x2-x1)+(x4-x3)+...+(x2m-x2m-1)<xn-x1接着，取走剩下的所有 xn-M>0 颗石子。

定理：当 n 为偶数且初始状态为目标状态时，小明必败；否则，必胜。

至此，问题完美解决。代码很简单，只需要检测 n 的奇偶性。当 n 为偶数时，进一步检测每堆的石子数目出现的次数是否为偶数。若采用哈希表，则当 n 为偶数时，时间复杂度为 O(n)；为奇数时，O(1)。

代码如下：



分享到：
| 很有意思的博弈论
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics