Maths Olympiad Prep

Library / /4 of 5

Combinatorics Difficulty 5.7 AIME, harder Prove it Brazil

Two players play a game as follows. There are n>1n > 1 rounds and d1d \ge 1 is fixed. In the first round A picks a positive integer m1m_1, then B picks a positive integer n1m1n_1 \ne m_1. In round kk (for k=2,,nk = 2, \dots, n), A picks an integer mkm_k such that mk1<mkmk1+dm_{k-1} < m_k \le m_{k-1} + d. Then B picks an integer nkn_k such that nk1<nknk1+dn_{k-1} < n_k \le n_{k-1} + d. A gets gcd(mk,nk1)\gcd(m_k, n_{k-1}) points and B gets gcd(mk,nk)\gcd(m_k, n_k) points. After nn rounds, A wins if he has at least as many points as B, otherwise he loses. For each n,dn, d which player has a winning strategy?

Solution

BB has a winning strategy. Let s=N!s = N! for NN sufficiently large (so N!N! is divisible by all mim_i's). BB can compute NN after AA makes his first choice, because he knows that the biggest number that AA can choose in any round is at most m1+(n1)dm_1 + (n-1)d, so NN may be any number bigger than m1+(n1)dm_1 + (n-1)d. BB always chooses nk=mk+sn_k = m_k + s. Then BB wins gcd(mk,mk+s)=mk\gcd(m_k, m_k + s) = m_k points and AA wins gcd(mk1,s+mk)=gcd(mk1,mk)mk1<mk\gcd(m_{k-1}, s+m_k) = \gcd(m_{k-1}, m_k) \le m_{k-1} < m_k points. Since BB wins more points than AA in every round, BB wins the game.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.