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

of games played

k . 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 some point in time when Rosencrantz and Guildenstern had the exact same win-rate. Find the product of all possible values of k . Proposed by: Alexander Katz 1 Answer: 2015 m Write k = , for relatively prime integers m, n . For the property not to hold, there must exist integers n a and b for which a 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 > an hence 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 now show that if n − m 6 = 1, then the property does not hold. By Bzout’s Theorem, as n and m are relatively prime, there exist a and x such that an = mx − 1, where 0 < a < m . Then an + n − m ≥ an +2 = mx +1, n so b = x satisfies the conditions. As a result, the only possible k are those in the form . n +1 We know that Rosencrantz played at most 2015 games, so the largest non-perfect winrate he could 1 2014 1 2 2014 possibly have is . Therefore, k ∈ { , , . . . , } , the product of which is . 2015 2 3 2015 2015 101