Question

一道数学难题（英文）

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.
请您提供一些步骤
做出来再追加100分啊

but what is its limit as n tends to infinity ?
n趋向于无穷的时候 求极限。

Answer 1

（简称两人为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

Answer 2

朋友
我先帮你翻译一下

Nathan 和 Abi 在玩一个游戏, Abi总是第一个先来. 玩家们将轮流把1个正数转换成更小的正数(比如将27转换成26)然后再把这个转换后的正数传给其他玩家, 在每次行动时, 玩家可以将那个正数减1或除2 如果是分数要把它改换成正数(比如得到的数字是14.5就要将它换成14),
因此, 有个正数是28你可以(28-1)就是27 或 (28除2)就是14 或 如果整数是27那么也还是(27-1)就是26 或 (27除2)就是13.5 但要将它改成13

当这个整数一直延伸到0时这个游戏就结束了, 赢家将会是最后一个行动的玩家(就是最后将整数转换到0的玩家)

比方: 这个整数是15 先从Abi开始 他可能将用(15/2)然后得到7 接着把这个7传给Nathan 然后Nathan可能用(7-1)得到6 再接着传给Abi 然后Abi 可能用(6/2)得到3 在然后 把3传给 Nathan 这样接着接着 之到最后一个玩家得到0也就是Nathan 最后从Abi哪得到1后再将1-1就等于0) Nathan 得到0赢了

接下来的是问题:

1. 如果Abi 和 Nathan 两个人都用最好的战略 谁将会赢如果这个整数是 1000? 或 2000?(Abi总是第1个先来) 证实你的答案

楼主 请你把第2题的问题 but what is its limit as n tends to in nity 打清楚好吗? 有个字你好像打错了

我帮你做做吧

Answer 3

这题很无聊啊，又是什么竞赛的题吧，那些老头老太太就会胡闹！

Answer 4

谁出的，是英语还是数学