英文解析

9. Rosencrantz plays n ≤ 2015 games of question, and ends up with a win rate i.e. of

of games playedk . Guildenstern has also played several games, and has a win rate less than k . He realizes that if,

after playing some more games, his win rate becomes higher than k , then there must have been somepoint in time when Rosencrantz and Guildenstern had the exact same win-rate. Find the product ofall possible values of k .
Proposed by: Alexander Katz
Answer:1
2015
Write k = , for relatively prime integers m, n . For the property not to hold, there must exist integersmna and b for whicha m a + 1 < <
b n b + 1
(i.e. at some point, Guildenstern must ”jump over” k with a single win)
⇐⇒ an + n − m > bm > anhence there must exist a multiple of m strictly between an and an + n − m .
If n − m = 1, then the property holds as there is no integer between an and an + n − m = an +1. We nowshow that if n − m 6 = 1, then the property does not hold. By Bzout’s Theorem, as n and m are relativelyprime, there exist a and x such that an = mx − 1, where 0 < a < m . Then an + n − m ≥ an +2 = mx +1,
so b = x satisfies the conditions. As a result, the only possible k are those in the form .nn +1
We know that Rosencrantz played at most 2015 games, so the largest non-perfect winrate he could
2014 1 2 20141
possibly have is . Therefore, k ∈ { , , . . . , } , the product of which is .
2015 2 3 2015
2015
101