Problem 366
Stone Game III
Two players, Anton and Bernhard, are playing the following game.
There is one pile of
The first player may remove any positive number of stones, but not the whole pile.
Thereafter, each player may remove at most twice the number of stones his opponent took on the previous move.
The player who removes the last stone wins.
E.g.
If the first player takes anything more than one stone the next player will be able to take all remaining stones.
If the first player takes one stone, leaving four, his opponent will take also one stone, leaving three stones.
The first player cannot take all three because he may take at most
So
For some winning positions there is more than one possible move for the first player.
E.g. when
Let
Find
取石子游戏(三)
两名玩家安东和伯恩哈德正在玩下面这个游戏。
有一堆共
先手玩家可以从堆中取走任意正数枚石子,但不能全部拿走。
此后,每名玩家可以从堆中取走的石子数目最多是其对手上一轮取走石子数目的两倍。
取走最后一枚石子的玩家获胜。
例如,若
如果先手玩家取走多于一枚石子,后手玩家总能取走剩下的全部石子。如果先手玩家取走一枚石子,他的对手将同样取走一枚石子,留下三枚石子。
先手玩家不能取走全部三枚石子,因为他最多只能取走
因此
在某些必胜态时,先手玩家可能有不止一种可行操作。
例如,若
对于先手玩家的必胜态,记
对于所有
对于所有
译注:“取石子游戏(二)”参见第325题。
Gitalking ...