Junior Balkan Mathematical Olympiad Shortlist

Solution:

First of all, the game finishes because the number on the calculator always decreases. By picking $m \%$ of a positive integer $n$, players get the number
$$\frac{m \cdot n}{100} = \frac{m \cdot n}{2^{2} 5^{2}}$$
We see that at least one of the powers of 2 and 5 that divide $n$ decreases after one move, as $m$ is not allowed to be 100, or a multiple of it. These prime divisors of $n$ are the only ones that can decrease, so we conclude that all the other prime factors of $n$ are not important for this game. Therefore, it is enough to consider numbers of the form $n = 2^{k} 5^{\ell}$ where $k, \ell \in \mathbb{N}_{0}$, and to draw conclusions from these numbers.

We will describe all possible changes of $k$ and $\ell$ in one move. Since $5^{3} > 100$, then $\ell$ cannot increase, so all possible changes are from $\ell$ to $\ell + b$, where $b \in \{0, -1, -2\}$. For $k$, we note that $2^{6} = 64$ is the biggest power of 2 less than 100, so $k$ can be changed to $k + a$, where $a \in \{-2, -1, 0, 1, 2, 3, 4\}$. But the changes of $k$ and $\ell$ are not independent. For example, if $\ell$ stays the same, then $m$ has to be divisible by 25, giving only two possibilities for a change $(k, \ell) \rightarrow (k-2, \ell)$, when $m=25$ or $m=75$, or $(k, \ell) \rightarrow (k-1, \ell)$, when $m=50$. Similarly, if $\ell$ decreases by 1, then $m$ is divisible exactly by 5 and then the different changes are given by $(k, \ell) \rightarrow (k+a, \ell-1)$, where $a \in \{-2, -1, 0, 1, 2\}$, depending on the power of 2 that divides $m$ and it can be from $2^{0}$ to $2^{4}$. If $\ell$ decreases by 2, then $m$ is not divisible by 5, so it is enough to consider when $m$ is a power of two, giving changes $(k, \ell) \rightarrow (k+a, \ell-2)$, where $a \in \{-2, -1, 0, 1, 2, 3, 4\}$.

We have translated the starting game into another game with changing (the starting pair of non-negative integers) $(k, \ell)$ by moves described above and the player who cannot make the move loses, i.e. the player who manages to play the move $(k, \ell) \rightarrow (0,0)$ wins. We claim that the second player wins if and only if $3 \mid k$ and $3 \mid \ell$.

We notice that all moves have their inverse modulo 3, namely after the move $(k, \ell) \rightarrow (k+a, \ell+b)$, the other player plays $(k+a, \ell+b) \rightarrow (k+a+c, \ell+b+d)$, where
$$(c, d) \in \{(0,-1), (0,-2), (-1,0), (-1,-1), (-1,-2), (-2,0), (-2,-1), (-2,-2)\}$$
is chosen such that $3 \mid a+c$ and $3 \mid b+d$. Such $(c, d)$ can be chosen as all possible residues different from $(0,0)$ modulo 3 are contained in the set above and there is no move that keeps $k$ and $\ell$ the same modulo 3. If the starting numbers $(k, \ell)$ are divisible by 3, then after the move of the first player at least one of $k$ and $\ell$ will not be divisible by 3, and then the second player will play the move so that $k$ and $\ell$ become divisible by 3 again. In this way, the first player can never finish the game, so the second player wins. In all other cases, the first player will make such a move to make $k$ and $\ell$ divisible by 3 and then he becomes the second player in the game, and by previous reasoning, wins.

The remaining part of the problem is to compute the number of positive integers $n \leqslant 2019$ which are winning for the second player. Those are the $n$ which are divisible by exactly $2^{3k} 5^{3\ell},\ k, \ell \in \mathbb{N}_{0}$. Here, exact divisibility by $2^{3k} 5^{3\ell}$ in this context means that $2^{3k} \| n$ and $5^{3\ell} \| n$, even for $\ell=0$, or $k=0$. For example, if we say that $n$ is exactly divisible by 8, it means that $8 \mid n, 16 \nmid n$ and $5 \nmid n$. We start by noting that for each ten consecutive numbers, exactly four of them are coprime to 10. Then we find the desired amount by dividing 2019 by numbers $2^{3k} 5^{3\ell}$ which are less than 2019, and then computing the number of numbers no bigger than $\left\lfloor \frac{2019}{2^{3k} 5^{3\ell}} \right\rfloor$ which are coprime to 10.

First, there are $4 \cdot 201 + 4 = 808$ numbers (out of positive integers $n \leqslant 2019$) coprime to 10. Then, there are $\left\lfloor \frac{2019}{8} \right\rfloor = 252$ numbers divisible by 8, and $25 \cdot 4 + 1 = 101$ among them are exactly divisible by 8. There are $\left\lfloor \frac{2019}{64} \right\rfloor = 31$ numbers divisible by 64, giving $3 \cdot 4 + 1 = 13$ divisible exactly by 64. And there are two numbers, 512 and $3 \cdot 512$, which are divisible by exactly 512. Similarly, there are $\left\lfloor \frac{2019}{125} \right\rfloor = 16$ numbers divisible by 125, implying that $4 + 2 = 6$ of them are exactly divisible by 125. Finally, there is only one number divisible by exactly 1000, and this is 1000 itself. All other numbers that are divisible by exactly $2^{3k} 5^{3\ell}$ are greater than 2019. So, we obtain that $808 + 101 + 13 + 2 + 6 + 1 = 931$ numbers not bigger than 2019 are winning for the statistician.

Alternative Solution by PSC:

Let us call a positive integer $n$ losing if $n = 2^{r} 5^{s} k$ where $r \equiv s \equiv 0 \bmod 3$ and $(k, 10) = 1$. We call all other positive integers winning.

Lemma 1. If $n$ is losing, then $\frac{m n}{100}$ is winning for all $m \in \{1,2, \ldots, 99\}$ such that $100 \mid m n$.

Proof of Lemma 1. Let $m = 2^{t} 5^{u} k'$. For $\frac{m n}{100}$ to be losing, we would need $t \equiv u \equiv 2 \bmod 3$. But then $m \geqslant 100$, a contradiction.

Lemma 2. If $n$ is winning, then there is an $m \in \{1,2, \ldots, 99\}$ such that $100 \mid m n$ and $\frac{m n}{100}$ is losing.

Proof of Lemma 2. Let $n = 2^{r} 5^{s} k$ where $(k, 10) = 1$. Pick $t, u \in \{0,1,2\}$ such that $t \equiv (2-r) \bmod 3$ and $u \equiv (2-s) \bmod 3$ and let $m = 2^{t} 5^{u}$. Then $100 \mid m n$ and $\frac{m n}{100}$ is losing. Furthermore $m < 100$ as otherwise $m = 100, t = u = 2$ giving $r \equiv s \equiv 0 \bmod 3$ contradicting the fact that $n$ was winning.

Combining Lemmas 1 and 2 we obtain that the second player wins if and only if the game starts from a losing number.

The remaining part of the problem is to compute the number of positive integers $n \leqslant 2019$ which are winning for the second player. Those are the $n$ which are divisible by exactly $2^{3k} 5^{3\ell},\ k, \ell \in \mathbb{N}_{0}$. Here, exact divisibility by $2^{3k} 5^{3\ell}$ in this context means that $2^{3k} \| n$ and $5^{3\ell} \| n$, even for $\ell=0$, or $k=0$. For example, if we say that $n$ is exactly divisible by 8, it means that $8 \mid n, 16 \nmid n$ and $5 \nmid n$. We start by noting that for each ten consecutive numbers, exactly four of them are coprime to 10. Then we find the desired amount by dividing 2019 by numbers $2^{3k} 5^{3\ell}$ which are less than 2019, and then computing the number of numbers no bigger than $\left\lfloor \frac{2019}{2^{3k} 5^{3\ell}} \right\rfloor$ which are coprime to 10.

First, there are $4 \cdot 201 + 4 = 808$ numbers (out of positive integers $n \leqslant 2019$) coprime to 10. Then, there are $\left\lfloor \frac{2019}{8} \right\rfloor = 252$ numbers divisible by 8, and $25 \cdot 4 + 1 = 101$ among them are exactly divisible by 8. There are $\left\lfloor \frac{2019}{64} \right\rfloor = 31$ numbers divisible by 64, giving $3 \cdot 4 + 1 = 13$ divisible exactly by 64. And there are two numbers, 512 and $3 \cdot 512$, which are divisible by exactly 512. Similarly, there are $\left\lfloor \frac{2019}{125} \right\rfloor = 16$ numbers divisible by 125, implying that $4 + 2 = 6$ of them are exactly divisible by 125. Finally, there is only one number divisible by exactly 1000, and this is 1000 itself. All other numbers that are divisible by exactly $2^{3k} 5^{3\ell}$ are greater than 2019. So, we obtain that $808 + 101 + 13 + 2 + 6 + 1 = 931$ numbers not bigger than 2019 are winning for the statistician.