Given positive integer $n$ and $r$ pairwise distinct primes $p_1,p_2,\cdots,p_r.$ Initially, there are $(n+1)^r$ numbers written on the blackboard: $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,b$ (not necessarily different) and write $\gcd(a,b)$. In Bob's round, he erases two numbers $a,b$ (not necessarily different) and write $\mathrm{lcm} (a,b)$. The game ends when only one number remains on the blackboard. Determine the minimal possible $M$ such that Alice could guarantee the remaining number no greater than $M$, regardless of Bob's move.
Problem
Source: 2021 China TST, Test 1, Day 2 P6
Tags: number theory, greatest common divisor, least common multiple
CANBANKAN
23.03.2021 04:07
The answer is $M^{\lfloor \frac n2 \rfloor},$ where $M=\prod\limits_{i=1}^r p_i$. Call such an operation a toggle at $a,b$. In this solution, $(a,b)$ denote their gcd and $[a,b]$ denote their lcm.
CRUXThe main idea for Alice's strategy for $n$ odd, and Bob's strategy for $n$ even is to force the game to end with one number. The main idea for Alice's strategy for $n$ even and Bob's strategy for $n$ odd is to force the game to end with two numbers such that after the other player makes the last move, you still win.
Alice's strategy for n oddAlice toggles $1, M^n$, setting $\alpha=1$.
If Bob toggles $a,\frac{M^n}{a}$, then Alice takes $\alpha, [a,\frac{M^n}{a}]$. Since $\alpha\mid M^{\frac{n+1}{2}},$ this pair of moves simply remove $a,\frac{M^n}{a}$ (even if $\alpha=a$).
If Bob toggles $a,b$ for $a,b\ne \alpha, ab\neq M^n$, then Alice toggles $\frac{M^n}{a}, \frac{M^n}{b}$. It can be easily shown that $[a,b] \cdot \gcd(\frac{M^n}{a}, \frac{M^n}{b})=M^n$.
If Bob toggles $\alpha,b$, then Alice toggles $t,\frac{M^n}{t}$ and set $\alpha$ as their gcd.
Note in this strategy, $\alpha\mid M^{\frac{n-1}{2}}$, and for all numbers $t$ other than $\alpha, M^n/\alpha$, the number of $t$'s on the blackboard is equal to the number of $\frac{M^n}{t}$'s on the blackboard. In the end, we arrive at $\alpha$ and win.
Alice's strategy for n evenAgain, Alice toggles $(1,M^n)$ as her first move. Set $\alpha=1, \beta=M^{\frac n2}$.
If Bob doesn't toggle $\beta$, Alice does exactly what she does if $n$ is odd, and the arguments would still work.
If Bob toggles $\alpha, \beta$, let $\beta$ be their LCM and let $\alpha=\gcd(T,\frac{M^n}{T})$. The key thing to note is that $\alpha, \beta \mid M^{\frac n2}$.
If Bob toggles $\beta,x$ for $x\neq \alpha$, then Alice toggles $[\beta,x], \frac{M^n}{x}$.
This is valid because at any point, unless $x\in\{\alpha,\beta, \frac{M^n}{\alpha}, \frac{M^n}{\beta} \}$, we can see that the number of $x$ on the blackboard is the same as the number of $\frac{M^n}{x}$'s on the blackboard. Furthermore, the number of $\beta, \alpha$ is one more than number of $\frac{M^n}{\beta}, \frac{M^n}{\alpha}$, respectively. The numbers in the end of the process are $\alpha,\beta$, and their LCM is a divisor of $M^{\frac n2}$, as desired.
Bob's strategy for n evenSet $\alpha=M^{\frac n2}$. If Alice toggles $x,y$, Bob toggles $\frac{M^n}{x}, \frac{M^n}{y}$. If Alice toggles $x,\frac{M^n}{x}$ for $x\neq\alpha, \frac{M^n}{\alpha}$, then Bob toggles $\alpha, \gcd(x,\frac{M^n}{x})$, and this new alpha is divisible by $M^{\frac n2}$. Notice the number of $\frac{M^n}{\alpha}$ is one less than the number of one less than the number of $\alpha$s, and for the other numbers, the number of $\frac{M^n}{x}$'s are equal to the number of $x$'s. In the end, we get $\alpha$, so we win.
Bob's strategy for n oddSet $\alpha=M^{\frac{n-1}{2}}, \beta=M^{\frac{n+1}{2}}$. For other cases, refer to the strategy above. If Alice toggles $\beta$, $\alpha$, then Bob toggles an arbitary $T,\frac{M^n}{T}$, set $\beta\rightarrow (\beta,\alpha), \alpha\rightarrow [T,\frac{M^n}{T}]$, so we see that $M^{\frac{n-1}{2}}\mid \beta, M^{\frac{n+1}{2}}\mid \alpha$.
If Alice toggles $\alpha,x$, then Bob toggles $(\alpha,x),\frac{M^n}{x}$ for $x\ne \frac{M^n}{\alpha}$, and reassigns $\alpha$ to that. The case for $\beta$ is similar. If $\alpha\beta=M^n$, then note the number of $t$ is exactly the number of $\frac{M^n}{t}$'s. Otherwise, note the number of $\alpha$, $\beta$, at the end of Bob's turn is one more than the number of $\frac{M^n}{\alpha}, \frac{M^n}{\beta}$, respectively. In the end, the last two numbers will be $\alpha, \beta$, so Bob achieves his goal.
Veconveo
18.09.2021 05:14
CANBANKAN wrote:
The answer is $M^{\lfloor \frac n2 \rfloor},$ where $M=\prod\limits_{i=1}^r p_i$. Call such an operation a toggle at $a,b$. In this solution, $(a,b)$ denote their gcd and $[a,b]$ denote their lcm.
CRUXThe main idea for Alice's strategy for $n$ odd, and Bob's strategy for $n$ even is to force the game to end with one number. The main idea for Alice's strategy for $n$ even and Bob's strategy for $n$ odd is to force the game to end with two numbers such that after the other player makes the last move, you still win.
Alice's strategy for n oddAlice toggles $1, M^n$, setting $\alpha=1$.
If Bob toggles $a,\frac{M^n}{a}$, then Alice takes $\alpha, [a,\frac{M^n}{a}]$. Since $\alpha\mid M^{\frac{n+1}{2}},$ this pair of moves simply remove $a,\frac{M^n}{a}$ (even if $\alpha=a$).
If Bob toggles $a,b$ for $a,b\ne \alpha, ab\neq M^n$, then Alice toggles $\frac{M^n}{a}, \frac{M^n}{b}$. It can be easily shown that $[a,b] \cdot \gcd(\frac{M^n}{a}, \frac{M^n}{b})=M^n$.
If Bob toggles $\alpha,b$, then Alice toggles $t,\frac{M^n}{t}$ and set $\alpha$ as their gcd.
Note in this strategy, $\alpha\mid M^{\frac{n-1}{2}}$, and for all numbers $t$ other than $\alpha, M^n/\alpha$, the number of $t$'s on the blackboard is equal to the number of $\frac{M^n}{t}$'s on the blackboard. In the end, we arrive at $\alpha$ and win.
Alice's strategy for n evenAgain, Alice toggles $(1,M^n)$ as her first move. Set $\alpha=1, \beta=M^{\frac n2}$.
If Bob doesn't toggle $\beta$, Alice does exactly what she does if $n$ is odd, and the arguments would still work.
If Bob toggles $\alpha, \beta$, let $\beta$ be their LCM and let $\alpha=\gcd(T,\frac{M^n}{T})$. The key thing to note is that $\alpha, \beta \mid M^{\frac n2}$.
If Bob toggles $\beta,x$ for $x\neq \alpha$, then Alice toggles $[\beta,x], \frac{M^n}{x}$.
This is valid because at any point, unless $x\in\{\alpha,\beta, \frac{M^n}{\alpha}, \frac{M^n}{\beta} \}$, we can see that the number of $x$ on the blackboard is the same as the number of $\frac{M^n}{x}$'s on the blackboard. Furthermore, the number of $\beta, \alpha$ is one more than number of $\frac{M^n}{\beta}, \frac{M^n}{\alpha}$, respectively. The numbers in the end of the process are $\alpha,\beta$, and their LCM is a divisor of $M^{\frac n2}$, as desired.
Bob's strategy for n evenSet $\alpha=M^{\frac n2}$. If Alice toggles $x,y$, Bob toggles $\frac{M^n}{x}, \frac{M^n}{y}$. If Alice toggles $x,\frac{M^n}{x}$ for $x\neq\alpha, \frac{M^n}{\alpha}$, then Bob toggles $\alpha, \gcd(x,\frac{M^n}{x})$, and this new alpha is divisible by $M^{\frac n2}$. Notice the number of $\frac{M^n}{\alpha}$ is one less than the number of one less than the number of $\alpha$s, and for the other numbers, the number of $\frac{M^n}{x}$'s are equal to the number of $x$'s. In the end, we get $\alpha$, so we win.
Bob's strategy for n oddSet $\alpha=M^{\frac{n-1}{2}}, \beta=M^{\frac{n+1}{2}}$. For other cases, refer to the strategy above. If Alice toggles $\beta$, $\alpha$, then Bob toggles an arbitary $T,\frac{M^n}{T}$, set $\beta\rightarrow (\beta,\alpha), \alpha\rightarrow [T,\frac{M^n}{T}]$, so we see that $M^{\frac{n-1}{2}}\mid \beta, M^{\frac{n+1}{2}}\mid \alpha$.
If Alice toggles $\alpha,x$, then Bob toggles $(\alpha,x),\frac{M^n}{x}$ for $x\ne \frac{M^n}{\alpha}$, and reassigns $\alpha$ to that. The case for $\beta$ is similar. If $\alpha\beta=M^n$, then note the number of $t$ is exactly the number of $\frac{M^n}{t}$'s. Otherwise, note the number of $\alpha$, $\beta$, at the end of Bob's turn is one more than the number of $\frac{M^n}{\alpha}, \frac{M^n}{\beta}$, respectively. In the end, the last two numbers will be $\alpha, \beta$, so Bob achieves his goal.
you can translate the word ""toggle"" of your proof?