一道数学难题（英文）6.Nathan and Abi are playing a game.Abi always goe
4个回答
（简称两人为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
相关问题
