Given a positive integer $n$, all of its positive integer divisors are written on a board. Two players $A$ and $B$ play the following game: Each turn, each player colors one of these divisors either red or blue. They may choose whichever color they wish, but they may only color numbers that have not been colored before. The game ends once every number has been colored. $A$ wins if the product of all of the red numbers is a perfect square, or if no number has been colored red, $B$ wins otherwise. If $A$ goes first, determine who has a winning strategy for each $n$.
Problem
Source: Iberoamerican Problem 5
Tags: Divisors, Iberoamerican, combinatorics
23.09.2017 07:19
If $n $ is squarefree: Let $n=p_1...p_k $.A can get perfect square if the red ones are 1)$1$ 2)All numbers And of course B will color 1 blue and some number then he will destroy A's strategy. So if A wants to win the only thing is to color all numbers blue.And of course B will color a number red.So B wins. In other case that there is $p$ s.t $p^2|n $ I think A's strategy will be to start with the perfect square that divide $n $.
16.04.2019 21:48
I think your answer is wrong. $p^2$ is evidently not squarefree for any prime $p$, but $A$ wins. The divisors are $1, p, p^2$. $A$ colors $p$ blue, and clearly $A$ then wins. Unfortunately, I don't know how to solve this, does anyone have a solution?
17.04.2019 14:08
We claim that $A$ wins if and only if $n$ is either a perfect square or a prime. Let $n = \prod_{i = 1}^{k} p_i^{\alpha_i}$ and for each divisor $d = \prod_{i = 1}^{k} p_i^{\beta_i}$, replace it by the vector in $\mathbb{Z}_2^k$ corresponding to $(\beta_1, \ldots, \beta_k)$ reduced modulo $2$. Then in each move, a player chooses a vector not chosen before and multiplies it by a scalar in $\mathbb{Z}_2$. $A$ wins if and only if the sum of the vectors at the end is zero. Observe that the multiplicity of a vector $(v_1, \ldots, v_k)$ on the board is equal to $\prod_{i = 1}^{k} c_{i, v_i}$, where $c_{i, j} = |(j + 2\mathbb{Z}) \cap \{0, 1, \ldots, \alpha_i\}|$. First consider the case when $n$ is a perfect square. Then all $\alpha_i$ are even, so $c_{i, 0}$ and $c_{i, 1}$ have opposite parity for all $i$. Consequently, there is a unique vector with odd multiplicity. Hence, $A$ colors this vector blue in his first move and imitates $B$'s moves afterwards. In this way $A$ wins. Now consider the case when $n$ is neither a perfect square nor a prime power. Then the number of divisors of $n$ is even, so $B$ has the last move. Note that if the only vector that $B$ can choose in his last move is non-zero, then $B$ surely wins. So it suffices to show that $B$ can choose all the zero vectors before his last move. But this is clear since the total number of zero vectors is less than half the number of divisors. Indeed, we have $\prod_{i = 1}^{k} c_{i, 0} < \frac{1}{2}\prod_{i = 1}^{k} (\alpha_i + 1)$, which is true since there is at least one $i$ such that $c_{i, 0} = \frac{\alpha_i + 1}{2}$ (the one with $\alpha_i$ odd) and we have $c_{j, 0} < \alpha_j + 1$ for the $k - 1 \geq 1$ values of $j \neq i$. So it remains to deal with the case when $n = p^\alpha$ with $\alpha$ odd. Then we just have $m$ zeroes and $m$ ones on the board, where $m = \frac{\alpha + 1}{2}$. If $m = 1$, then $A$ wins by coloring the one blue. If $m \geq 2$, then as long as there are at least $4$ numbers on the board, $B$ just chooses the number different from the one chosen in $A$'s previous move. This reduces the game to the case $m = 2$, but note that the roles of $A$ and $B$ may be swapped, in the sense that now $B$ may want to get a zero sum in the end. However, $B$ can always win -- if he wants a zero sum, then he chooses the same number and same color as in $A$'s previous move, otherwise he chooses the same number and opposite color. This concludes the proof.