Track / Stage 8 / 93 of 180 #1793 of 2000

Problem 1793

IMO Shortlist mid-range; USAMO P2/P5

Number theory Difficulty 8.3 Prove it IMO HK TST · Hong Kong

Denote by $\sigma(n)$ the sum of divisors of $n$ . A positive integer $n$ ( $n \ge 2$ ) is redundant if for any integer $k$ , with $k < n$ , we have $\frac{\sigma(k)}{k} < \frac{\sigma(n)}{n}$ . (For instance if $n = 1, 2, 3, 4, 5$ , then $\frac{\sigma(n)}{n} = 1, \frac{3}{2}, \frac{4}{3}, \frac{7}{4}, \frac{6}{5}$ respectively. Hence, $2$ and $4$ are redundant, $3$ and $5$ are not.) Show that there exist infinitely many redundant numbers.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

(Superabundant numbers/IMO Shortlist 1983) When $n = m!$ , we have
$\frac{\sigma(m!)}{m!} \ge \frac{1}{m!} \left( m! + \frac{m!}{2} + \frac{m!}{3} + \dots + \frac{m!}{m} \right) = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{m}.$
Since the harmonic series diverges, the sequence $\left\{ \frac{\sigma(n)}{n} \right\}$ is unbounded. Therefore, after finding some redundant numbers $n_1, n_2, \dots, n_k$ , we can always find the next number $n_{k+1}$ such that $\frac{\sigma(n_{k+1})}{n_{k+1}} > \frac{\sigma(n_k)}{n_k}$ . This implies $n_{k+1}$ is redundant, and so there are infinitely many redundant numbers.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.