62nd Ukrainian National Mathematical Olympiad

Answer. $p^{\beta }$ and $p^{\alpha }q$, where $q>p^{\alpha }$ where $p,q$ are prime numbers.

Solution:

First, let's prove that if a number has at least three different prime divisors, it is not suitable for us. Let $m$ be the number of different prime divisors and $p<q$ be the two smallest prime divisors of $n$. Then it is clear that there exists $\alpha$ such that the first consecutive divisors of $n$ will be the numbers $1<p<p^2<\cdots <p^{\alpha }<q$. Note that taking as $d_{i+1}$ all prime divisors of $n$ except for the smallest, we get $m-1$ numbers that satisfy the condition. Indeed, all divisors smaller than a prime number are coprime with that number, so $(d_i,d_{i+1})=1$, and since $d_{i-1}<d_i$ we get the conclusion. It remains to find another good number. Let $n:p^{\alpha +1}$. Then the divisor $q$ is a good divisor. Indeed, it cannot be followed by a divisor divisible by $q$, because the smallest of these not yet chosen divisors is $pq$, but $p^{\alpha +1}<pq$. So $p^{\alpha +1}$ is the next composite divisor. Then take the last prime number that comes after $q$ (possibly $q$), after which the next composite number will be $p^{\alpha +1}$. Then it will be the desired $m$-th good number. Now let $n$ be not divisible by $p^{\alpha +1}$. Then the next composite divisor is $pq$. If between $q$ and $pq$ there is at least one prime divisor, then we take the last of them as our $m$-th good number. Otherwise, the divisors $p^{\alpha },q,pq$ will be consecutive divisors, and hence $\frac{n}{pq},\frac{n}{q},\frac{n}{p^{\alpha }}$ will be consecutive divisors, but then the divisor $\frac{n}{q}$ will be the desired one, because since $\alpha$ is the degree of occurrence of a prime $p$ in the number $n$, $\frac{n}{p^{\alpha }}$ is not divisible by $p$, and $\frac{n}{pq}$ is not divisible by $p^{\alpha }$, but $\frac{n}{q}:p^{\alpha }$, and $\frac{n}{p^{\alpha }}$ is divisible by more than one prime divisor of $n$, which means that we have not yet taken it into account, which is what we wanted to prove.

If a number is a power of a prime, then obviously it suits us, because it has no good divisors at all. It remains to consider the case when a number has two different prime divisors, which we denote $p<q$. Then it is clear that there exists $\alpha$ that the first consecutive divisors of $n$ will be the numbers $1<p<p^2<\cdots <p^{\alpha }<q$. The divisor $p^{\alpha }$ is a good divisor, which means it is the only good divisor of our number. Hence, the next divisor after $q$ is a divisor that is divisible by $q$, but the smallest such divisor not yet used is $pq$, and therefore it comes after $q$. However, $p^{\alpha +1}<pq$, and hence our number $n$ is not divisible by $p^{\alpha +1}$. Then, similarly, the divisors $\frac{n}{pq},\frac{n}{q},\frac{n}{p^{\alpha }}$ will be consecutive divisors, and the divisor $\frac{n}{q}$ will be a good divisor. So, $\frac{n}{q}=p^{\alpha }$, so $n=p^{\alpha }q$, and $p^{\alpha }<q$, and the above answer follows. A simple check shows that both answers do indeed satisfy the condition.