Two players play a game as follows. There are n>1 rounds and d≥1 is fixed. In the first round A picks a positive integer m1, then B picks a positive integer n1=m1. In round k (for k=2,…,n), A picks an integer mk such that mk−1<mk≤mk−1+d. Then B picks an integer nk such that nk−1<nk≤nk−1+d. A gets gcd(mk,nk−1) points and B gets gcd(mk,nk) points. After n rounds, A wins if he has at least as many points as B, otherwise he loses. For each n,d which player has a winning strategy?
Solution
B has a winning strategy. Let s=N! for N sufficiently large (so N! is divisible by all mi's). B can compute N after A makes his first choice, because he knows that the biggest number that A can choose in any round is at most m1+(n−1)d, so N may be any number bigger than m1+(n−1)d. B always chooses nk=mk+s. Then B wins gcd(mk,mk+s)=mk points and A wins gcd(mk−1,s+mk)=gcd(mk−1,mk)≤mk−1<mk points. Since B wins more points than A in every round, B 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.