Two players alternately write numbers in the cells of an $n\times n$ square board. Hereby, in the intersection of the $i$-th row and the $j$-th column the first player may write the greatest common divisor of numbers $i$ and $j$, whereas the second player may write their least common multiple. When the board is filled up, the numbers of the first column are divided by $1$, those of the second column by $2$, etc., those of the last column by $n$. Then the product of the obtained numbers in the board is computed. If the result is smaller than $1$, the first player wins, otherwise the second player wins. Which player has a winning strategy?
Problem
Source:
Tags: number theory, combinatorics, game
alchemyst_
25.07.2021 16:43
The second player has the winning strategy and that strategy is to 'mirror' Player $1$ so if Player $1$ takes $(i, j)$, Player $2$ makes sure that they take $(j, i)$ in the next move (if $i \neq j$.) We will now show that this strategy forces the final result, $R$, to be greater than or equal to $1$. If this strategy is followed, we have that $(i, j), (j, i) = gcd(i, j), lcm(i, j)$. Recall the well-known lemma that $gcd(i, j) \cdot lcm(i, j) = ij$ and so for any pair $(i, j)$ with $i < j$, they contribute a product of $ij$ to the final result. Denote the product of the board to be $P$, when we include the diagonal ($lcm(i, i) = gcd(i, i) = i$) we have that: $P = (2 \cdot 1) \cdot (3 \cdot 2) \cdot (3 \cdot 1) \cdot (4 \cdot 3) \cdot (4 \cdot 2) \cdot (4 \cdot 1)... (n \cdot 2) \cdot (n \cdot 1) \cdot n! = n! \cdot \prod_{k = 1}^{n - 1} (k + 1)^k \cdot k!$ Note that to get from $P$ to $R$ we are effectively dividing by $(n!)^n$. $\frac{n! \cdot \prod_{k = 1}^{n - 1} (k + 1)^k \cdot k!}{(n!)^n} = \frac{\prod_{k = 1}^{n - 1} (k + 1)^k \cdot k!}{(n!)^{n - 1}} = 1 = R$ Which we can see by fixing an integer $i \in (1, 2, 3 ... n)$ and observing $i$ appears exactly $n - 1$ times in the numerator. Since $R$ isn't smaller than $1$, Player $2$ wins.