South African Mathematics Olympiad

We prove that no positive divisor $d$ of $n$ that is greater or equal to $\sqrt{n}$ can be special: if $d$ is special, then $d+1$ is also a divisor, so $n/d$ and $n/(d+1)$ are both integers, which means that their difference is at least 1. Thus $$\frac{n}{d}\ge \frac{n}{d+1}+1,$$ which is equivalent to $n\ge d(d+1)$. But since $d(d+1)>d^2\ge n$, this is a contradiction. Thus only divisors less than $\sqrt{n}$ can be special. Since divisors come in pairs ($a$ and $n/a$) such that one of them is less than $\sqrt{n}$ and one greater than $\sqrt{n}$ (when $n$ is a square, $\sqrt{n}$ is paired with itself), this means that at most half the divisors can be special.

If precisely half the divisors are special, then $n$ cannot be a square, and every divisor less than $\sqrt{n}$ has to be special. Thus 1 has to be a special divisor, meaning that 2 is a divisor (and thus also special), so 3 is a divisor, and so on, up to the greatest integer $k$ that is less than $\sqrt{n}$. Finally, $k$ is special, so $k+1$ has to be a divisor as well. Since $k$ is the greatest divisor less than $\sqrt{n}$ and $k+1$ the least divisor greater than $\sqrt{n}$, their product must be $n$, so $n=k(k+1)=k^2+k$. Moreover, $k-1$ is also a divisor of $n=k^2+k$ (unless $k=1$), so it also divides $n-(k-1)(k+2)=k^2+k-(k^2+k-2)=2$.

This leaves us with $k=1$, $k=2$ and $k=3$ as the only possibilities, giving us $n=2$, $n=6$ or $n=12$. In all these cases, exactly half the divisors are special.