一道数学难题（英文）6.Nathan and Abi are playing a game.Abi always goe

一道数学难题（英文）
6.Nathan and Abi are playing a game.Abi always goes rst.The players take turns changing a
positive integer to a smaller one and then passing the smaller number back to their opponent.
On each move,a player may either subtract one from the integer or halve it,rounding down if
necessary.Thus,from 28 the legal moves are to 27 or to 14; from 27,the legal moves are to 26
or to 13.The game ends when the integer reaches 0.The player who makes the last move wins.
For example,if the starting integer is 15,Abi might move to 7,Nathan to 6,Abi to 3,Nathan
to 2,Abi to 1,and now Nathan moves to 0 and wins.(However,in this sample game Abi could
have played better!)
(a) Assuming both Nathan and Abi play according to the best possible strategy,who will win
if the starting integer is 1000?2000?Prove your answer.
(b) As you might expect,for some starting integers Abi will win and for others Nathan will
win.If we pick a starting integer at random from all the integers from 1 to n inclusive,
we can consider the probability of Nathan winning.This probability will uctuate as n
increases,but what is its limit as n tends to in nity?Prove your answer.
请您提供一些步骤
but what is its limit as n tends to infinity
n趋向于无穷的时候 求极限。

（简称两人为A与N）定义函数f(n)如下：
游戏的起始数为n时,若A必胜,则f(n)=0,若N必胜,则f(n)=1.
于是容易发现,f 满足如下规律：f(n) = (1-f(n-1))(1-f([n/2])),其中[n/2]是n/2的整数部分.这是因为从n开始时,N能获胜当且仅当n-1与[n/2]都是先手的必胜局,否则A可选择留给N的起始数为n-1或[n/2],使先手必败.
于是我们先证明f(2n+1)=0,即起始数为奇数时,A必胜.n=0时显然成立.对一般的n,如果f(2n+1)=1,则
f(2n+1) = (1-f(n))(1-f(2n)) = 1 => f(n) = f(2n) = 0
f(2n) = (1-f(n))(1-f(2n-1)) = 1-f(2n-1) = 0 => f(2n-1) = 1
=> …… => f(1) = 1
矛盾.
那么,对于偶数n,设n=m*2^d,其中m是奇数.则
f(n) = (1-f(m*2^{d-1}))(1-f(m*(2^d - 1))) = 1-f(m*2^{d-1})
即,当n是偶数时,对于以n与n/2开始的游戏,A的胜负情况恰好相反.于是,当d是奇数的时候,A必败；反之A必胜.
于是：1000=125*2^3 => A必败,2000=125*2^4 => A必胜.
此外,当n->∝时,N获胜的概率为：
lim_{n->∝}1/n{[n/2] - [n/4] + [n/8] - ...- (-1)^d[n/2^d] - ...} = 1/3