数学逻辑游戏05:NIM游戏(解答1)
(2009-03-17 10:51:48)
标签:
幽魂之家数学逻辑游戏文化 |
分类: 休闲娱乐类 |
NIM游戏(见《数学逻辑游戏05:NIM游戏》)是一种有限双人零和(没有平局的)游戏,有限是说在有限步内结束,零和是说没有和局(必有输赢)。
这种游戏的必胜策略就是逼使对方处于必输的状态。
先讨论<3,5,7>游戏。任何一种状态可以用来表示,a,b,c分别表示三堆小棍的个数,注意小棍的堆是对称的,所以这仅有次序不同的三个数表示同一种状态(如<3,0,4>,<3,4,0>和<0,4,3>)。
① <0,a,a>就是必输状态,我只要仿照对方(他在一堆中拿多少,我在另一堆也拿多少)就必赢。
② <1,2,3>也是必输状态。不管对方在哪堆拿多少,我总可以有办法使对方处于状态①。
③ <1,4,5>也是必输状态。不管对方在哪堆拿多少,我总可以有办法使对方处于状态①或②。
④ <2,4,6>也是必输状态。不管对方在哪堆拿多少,我总可以有办法使对方处于状态①或②或③。
⑤ <3,4,7>也是必输状态。不管对方在哪堆拿多少,我总可以有办法使对方处于状态①或②或③或④。
因此,<3,5,7>游戏有必胜策略,我只要在5根小棍的堆里拿掉1根,留给对方<3,4,7>就可以了。
实际上,<2,5,7>和<3,5,6>也是必输状态。所以随便在哪堆中拿1根,都能产生必胜策略。
(未完)