Bash Game - 巴什博弈
问题
和两人轮流从个物品中取出物品，每次取的物品数限定为（至少取个，至多取个。都是正整数且，显然若则第一个取的人一次就可以把所有物品取走从而获胜）个，最后一个把物品取光的人获胜。
给定和，当我方先手，我方和对方都是高手（在能赢的情况下一定能赢），求我方是否能赢。
巴什博弈还可以描述为：和两人轮流向一个篮子中放入物品，篮子最多能放个物品。每次放的物品数量限定为，最后一个把篮子填满的人获胜。
上面两个问题其实是相同的，只是放和取的过程相反。本章中其他的博弈问题都可以像这样用相反的过程进行颠倒。
解法
若，取个物品，剩下个物品。下一次总能一次取光，获胜。
介绍博弈论中的概念“局势”，当一方做选择时，剩余的物品数量为时，称这一方面对的局势为。对于的情况：
当我方面临局势时，我方必赢，因为我方可以将剩余物品都拿光；
当我方面临局势时，我方必输，因为我方取物品后，必然留给对方局势，对方必赢；
当我方面临局势时，我方必赢，因为我方可以留给对方局势，对方必输；
可以看出，当留给对方个物品时，下一轮对方必然会输，因为对方必然取个物品，留给我方个物品。称这样的物品数量为必赢数量。
当我方取物品时面对的倍数个物品时，我方必输，即。否则对方必输。
该算法的时间复杂度为。