Maths Olympiad Prep

Library / Brazilian Mathematical Olympiad /75 of 120

Brazilian Mathematical Olympiad

Combinatorics Difficulty 5.7 AIME, harder Prove it Brazil

Two players play a game as follows. There are n>1n > 1 rounds and d≥1d \ge 1 is fixed. In the first round A picks a positive integer m1m_1, then B picks a positive integer n1≠m1n_1 \ne m_1. In round kk (for k=2,…,nk = 2, \dots, n), A picks an integer mkm_k such that mk−1<mk≤mk−1+dm_{k-1} < m_k \le m_{k-1} + d. Then B picks an integer nkn_k such that nk−1<nk≤nk−1+dn_{k-1} < n_k \le n_{k-1} + d. A gets gcd⁡(mk,nk−1)\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+(n−1)dm_1 + (n-1)d, so NN may be any number bigger than m1+(n−1)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⁡(mk−1,s+mk)=gcd⁡(mk−1,mk)≤mk−1<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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.