设游戏者是一个女孩和一个男孩。他们在一块1×l 000的棋盘上玩游戏。有n枚铜钱,最初,铜钱都放在靠近棋盘的盒子里,游戏者轮流行动。由女孩开始动手,女孩可以从棋盘中或棋盘外选取17枚或更少的铜钱,然后可将它们放入棋盘上没被占用的格子,使得每一个格子中至多只有一枚铜钱。男孩可以从格子中取走任何多枚铜钱,只要它们是在连成一片的格子中,然后把铜钱放回盒子中。如果女孩能将所有n枚铜钱连成一片地放在棋盘的格子上,她就是赢家。
(1)如果n=98,女孩可以赢;
(2)能使女孩赢的n的最大值是什么?
解 设游戏由女孩先开始动手。
(1)女孩能建立起任何一个用几个或者更少数目的铜钱组成的图案,只要它不含有多于16枚铜钱连在一起的形状。因为她能重新恢复男孩所移走的,并且继续她的建造。这样,她可以有12块每块连续由8枚铜钱所组成,在相邻的两块之间,有一个格子的空隙。在她下一次移动的时候,她可以把图案变为在两块17枚铜钱之间由8块8枚铜钱所组成。在下一步中,她必胜。
如果男孩移走一块由8枚组成的一片,女孩能将它补回去,并且从两边取9枚来补空隙。如果男孩取走17枚的一块,她总可以用8枚来填空,并且把余下的加到两端。如果男孩移走的是一块的一部分,在必要的时候,女孩可以移走余下的部分。
(2)答案是98。设想游戏做过一阵之后,还有多于98枚的铜钱。设想女孩走过她的最后一步之后,棋盘上的图案是
a1-a2-…-ak
这里a1、a2、…、ak为正整数,表示a1枚铜钱占有连续的一片的格子,然后一个空格,接着是a2枚铜钱占有连续的一片的格子,又是一个空格,如此等等。
如果女孩在她下一步动作时总能取胜。为不失一般性,可设所有的铜钱均已在棋盘上。于是a1≤17,且ak≤17。否则男孩从棋盘上取走多于17个的铜钱,这意味着在下一步动作时女孩不会得胜。
因为a1≤17,且ak≤17,存在i满足1<i<k,且
ai(k-2)≥99-17-17=65
因此

因为女孩下一步得胜,但是

得出矛盾。