MathDB
Game on GCD and LCM

Source: 2021 China TST, Test 1, Day 2 P6

March 17, 2021
number theorygreatest common divisorleast common multiple

Problem Statement

Given positive integer nn and rr pairwise distinct primes p1,p2,⋯ ,pr.p_1,p_2,\cdots,p_r. Initially, there are (n+1)r(n+1)^r numbers written on the blackboard: p1i1p2i2⋯prir(0≤i1,i2,⋯ ,ir≤n).p_1^{i_1}p_2^{i_2}\cdots p_r^{i_r} (0 \le i_1,i_2,\cdots,i_r \le n).
Alice and Bob play a game by making a move by turns, with Alice going first. In Alice's round, she erases two numbers a,ba,b (not necessarily different) and write gcd⁡(a,b)\gcd(a,b). In Bob's round, he erases two numbers a,ba,b (not necessarily different) and write lcm(a,b)\mathrm{lcm} (a,b). The game ends when only one number remains on the blackboard.
Determine the minimal possible MM such that Alice could guarantee the remaining number no greater than MM, regardless of Bob's move.
Back to ProblemsView on AoPS