Exercise 2. In the train, while they are returning from EGMOnd aan Zee, Clara and Edwige are playing the following game. Initially, the integer $n=1 \times 2 \times \cdots \times 20$ is written on a piece of paper. Then, each in turn, starting with Clara, the players replace the integer $n$ by one of the numbers $k n / 10$, where $k$ is an integer between 1 and 9 inclusive. The first player to write a number that is not an integer loses, and her opponent wins.

Clara and Edwige are formidable players and play optimally. Which of the two will win?
Solution to Exercise 2 Let's consider the number $n$ written on the piece of paper at the moment when player $X$ is about to play, and before the game ends. We partially factorize $n$ as a product of prime numbers: $n=2^{x} \times 5^{y} \times m$, where $x$ and $y$ are natural numbers and $m$ is a non-zero natural number that is coprime with 2 and 5.

We will then prove the property $\mathcal{P}_{n}$ by induction on $n$: player $\mathrm{X}$ will lose if $x$ and $y$ are both even, and will win otherwise. First, $\mathcal{P}_{1}$ is obvious, since X will have to replace the number $n=1$ with a number between $1 / 10$ and $9 / 10$.

Let then $n \geqslant 1$ be any integer. Suppose $\mathcal{P}_{1}, \ldots, \mathcal{P}_{n}$, and we will prove $\mathcal{P}_{n+1}$.

$\triangleright$ If $x$ and/or $y$ is odd, we denote $r$ and $s$ as the remainders of $x$ and $y$ modulo 2. Then player $\mathrm{X}$ replaces the integer $n$ with the integer $n^{\prime}=n /\left(2^{r} \times 5^{s}\right)$. Since $n^{\prime}=2^{x-r} \times 5^{y-s} \times m$, the property $\mathcal{P}_{n^{\prime}}$ ensures that the opponent of $\mathrm{X}$ will lose.

$\triangleright$ If $x$ and $y$ are both even, we still assume that $\mathrm{X}$ replaces $n$ with an integer $n^{\prime}$ (which is only possible if $x \geqslant 1$ or $y \geqslant 1$). If $\mathrm{X}$ replaces $n$ with the number $n^{\prime}=n / 2=2^{x-1} \times 5^{y} \times m$, then $\mathcal{P}_{n^{\prime}}$ ensures that the opponent of $\mathrm{X}$ will win. Otherwise, we can write $n^{\prime}$ in the form $n^{\prime}=2^{x^{\prime}} \times 5^{y-1} \times m^{\prime}$ (with $m^{\prime}$ coprime with 2 and 5): regardless of the values of $x^{\prime}$ and $m^{\prime}$, the property $\mathcal{P}_{n^{\prime}}$ still ensures that the opponent of $\mathrm{X}$ will lose.

We thus have the property $\mathcal{P}_{20!}$, where we have set $20!=1 \times 2 \times \cdots \times 20$. In particular, we easily observe that $20!=2^{18} \times 5^{4} \times m$, where we have set $m=3^{8} \times 7^{2} \times 11 \times 13 \times 17 \times 19$. Since Clara, who plays first, it is therefore Edwige who will win.