Skip to main content
OlympiadHQ

Browse · MathNet

Print

XX OBM

Brazil counting and probability

Problem

Two players play a game as follows. There are rounds and is fixed. In the first round A picks a positive integer , then B picks a positive integer . In round (for ), A picks an integer such that . Then B picks an integer such that . A gets points and B gets points. After rounds, A wins if he has at least as many points as B, otherwise he loses. For each which player has a winning strategy?
Solution
has a winning strategy. Let for sufficiently large (so is divisible by all 's). can compute after makes his first choice, because he knows that the biggest number that can choose in any round is at most , so may be any number bigger than . always chooses . Then wins points and wins points. Since wins more points than in every round, wins the game.
Final answer
B

Techniques

Games / greedy algorithmsGreatest common divisors (gcd)