Let $m>1$ be a natural number and $N=m^{2017}+1$. On a blackboard, left to right, are written the following numbers: \[N, N-m, N-2m,\dots, 2m+1,m+1, 1.\]On each move, we erase the most left number, written on the board, and all its divisors (if any). This procces continues till all numbers are deleted. Which numbers will be deleted on the last move.
Problem
Source: Bulgarian NMO 2017, 3rd round, p2
Tags: number theory, combinatorics
Ankoganit
21.04.2017 18:26
We claim that the last number to be deleted is $X=\frac{m^{2017}+1}{m+1}+m$. To prove this, we need to ensure two things: Thing 1: $X$ doesn't get deleted as the divisor of some other bigger number (which would be to its left). Proof: Clearly all the numbers on the board are $1\pmod m$, and so is $X$. If $X$ is a divisor of a bigger number $Z$ which causes it to get annihilated beforehand, we must have \begin{align*}Z\equiv 1\pmod m \implies \frac ZX\equiv 1\pmod m\implies \frac ZX\ge m+1\\ \implies Z\ge (m+1)X>(m+1)\cdot\frac{m^{2017}+1}{m+1}=m^{2017}+1.\end{align*}This is absurd. So $Z$ can't actually exist, like we said before. $\square$ Thing 2: All numbers to the right of $X$ get deleted before we eventually come to $X$. Proof: Let $A$ be a number to the left of $X$; of course, $A\le X-m=\tfrac{m^{2017}+1}{m+1}$. Then $B=A\cdot (m+1)$ is at most $m^{2017}+1$ and also $1\pmod m$, so $B$ occurs somewhere in the list we had to begin with. But then $A$ should've got deleted as a divisor of $B$ earlier, as we claimed. $\square$ Thus, we're done! $\blacksquare$
We need $X+Ym\le (X-m)(m+1)\iff Y\le X-m^2-m$, but we have $Y\le \tfrac{X}{m+1}$ (why?), so it's enough to show that $$\frac{X}{m+1}\le X-m^2-m\iff X\ge m^2+2m+1\iff m^{2017}\ge m^3+2m^2+2m.$$The last inequality is easy to establish via induction on $m$ for $m\ge 2$.
). So $Y$ must've been deleted before because of $S$. $\square$
mathaddiction
24.10.2020 06:30
Notice that CLAIM. If $a|b$ then $b$ can't be removed after $a$ Proof. Indeed, when we remove $a$, $b$ is removed. $\blacksquare$. Let $S=\frac{m^{2017}+1}{m+1}+m$, then for all numbers $s$ on the blackboard with $s<S$, $(m+1)s$ is also on the blackboard, so $s$ is not the last number to be removed from the CLAIM. Now $M$ be the set numbers initially on the blackboard which is greater than or equal to $S$. Notice that if $a\in M$ then $a\equiv 1\pmod m$ and $(m+1)a>S$, so $a$ has no multiples in $M$. Therefore, the last number removed must be the minimal element of $M$ which is $S$ as desired.