Balkan Mathematical Olympiad

Begin with a mere remark on the terms of the sequence under consideration.

Lemma 1. Each $a_n$ is minimal amongst all positive integers having the same number of positive divisors as $a_n$.

Proof. Suppose, if possible, that for some $n$, some positive integer $b<a_n$ has as many positive divisors as $a_n$. Then $a_m<b\le a_{m+1}$ for some $m<n$, and the definition of the sequence forces $b=a_{m+1}$. Since $b<a_n$, it follows that $m+1<n$, which is a contradiction, as $a_{m+1}$ should have less positive divisors than $a_n$. $\square$

Let $p_1<p_2<\cdots <p_n<\dots$ be the strictly increasing sequence of prime numbers, and write canonical factorisations into primes in the form $N={\prod }_{i\ge 1}{p}_i^{e_i}$, where $e_i\ge 0$ for all $i$, and $e_i=0$ for all but finitely many indices $i$; in this notation, the number of positive divisors of $N$ is $\tau (N)={\prod }_{i\ge 1}(e_i+1)$.

Lemma 2. The exponents in the canonical factorisation of each $a_n$ into primes form a non-strictly decreasing sequence.

Proof. Indeed, if $e_i<e_j$ for some $i<j$ in the canonical decomposition of $a_n$ into primes, then swapping the two exponents yields a smaller integer with the same number of positive divisors, contradicting Lemma 1. $\square$

We are now in a position to prove the required result. For convenience, a term $a_n$ satisfying $3a_n=2a_{n+1}$ will be referred to as a special term of the sequence.

Suppose now, if possible, that the sequence has infinitely many special terms, so the latter form a strictly increasing, and hence unbounded, subsequence. To reach a contradiction, it is sufficient to show that:

(1) The exponents of the primes in the factorisation of special terms have a common upper bound $e$; and

(2) For all large enough primes $p$, no special term is divisible by $p$.

Refer to Lemma 2 to write $a_n={\prod }_{i\ge 1}{p}_i^{e_i(n)}$, where $e_i(n)\ge e_{i+1}(n)$ for all $i$.

Statement (2) is a straightforward consequence of (1) and Lemma 1. Suppose, if possible, that some special term $a_n$ is divisible by a prime $p_i>2^{e+1}$, where $e$ is the integer provided by (1). Then $e\ge e_i(n)>0$, so $2^{e_1(n)e_i(n)+e_i(n)}{a}_n/p_i^{e_i(n)}$ is a positive integer with the same number of positive divisors as $a_n$, but smaller than $a_n$. This contradicts Lemma 1. Consequently, no special term is divisible by a prime exceeding $2^{e+1}$.

To prove (1), it is sufficient to show that, as $a_n$ runs through the special terms, the exponents $e_1(n)$ are bounded from above. Then, Lemma 2 shows that such an upper bound $e$ suits all primes.

Consider a large enough special $a_n$. The condition $\tau (a_n)<\tau (a_{n+1})$ is then equivalent to $(e_1(n)+1)(e_2(n)+1)<e_1(n)(e_2(n)+2)$. Alternatively, but equivalently, $e_1(n)\ge e_2(n)+2$. The latter implies that $a_n$ is divisible by 8, for either $e_1(n)\ge 3$ or $a_n$ is a large enough power of 2.

Next, note that $9a_n/8$ is an integer strictly between $a_n$ and $a_{n+1}$, so $\tau (9a_n/8)\le \tau (a_n)$, which is equivalent to $$(e_1(n)-2)(e_2(n)+3)\le (e_1(n)+1)(e_2(n)+1),$$ so $2e_1(n)\le 3e_2(n)+7$. This shows that $a_n$ is divisible by 3, for otherwise, letting $a_n$ run through the special terms, 3 would be an upper bound for all but finitely many $e_1(n)$, and the special terms would therefore form a bounded sequence.

Thus, $4a_n/3$ is another integer strictly between $a_n$ and $a_{n+1}$. As before, $\tau (4a_n/3)\le \tau (a_n)$. Alternatively, but equivalently, $$(e_1(n)+3)e_2(n)\le (e_1(n)+1)(e_2(n)+1),$$ so $2e_2(n)-1\le e_1(n)$. Combine this with the inequality in the previous paragraph to write $4e_2(n)-2\le 2e_1(n)\le 3e_2(n)+7$ and infer that $e_2(n)\le 9$. Consequently, $2e_1(n)\le 3e_2(n)+7\le 34$, showing that $e=17$ is suitable for (1) to hold. This establishes (1) and completes the solution.