China Girls' Mathematical Olympiad

For positive integer $n$, let $d(n)$ denote the number of positive divisors of $n$ (including $1$ and $n$ itself).

Firstly, note that $1$ and $2$ are good, since $1=\frac{2}{d(2)}$ and $$2=\frac{8}{d(8)}.$$

Secondly, we note that if $p$ is an odd prime, then $p$ is good. This is because $d(8p)=8$. In particular, $3,5,7,11,13,17$ are good numbers.

Thirdly, we note that if $p$ is an odd prime, then $2p$ is good. This is because $d(2^2\cdot 3^{2}p)=3\cdot 3\cdot 2$. In particular, $6,10,14$ are good numbers.

Fourthly, we note that $$4=\frac{36}{d(36)},8=\frac{96}{d(96)},9=\frac{108}{d(108)},$$ $$12=\frac{240}{d(240)},15=\frac{360}{d(360)},16=\frac{128}{d(128)}.$$ Thus, the numbers $1,2,\dots ,17$ are good.

Finally, we prove that $18$ is not good. We approach indirectly by assuming that $18=\frac{n}{d(n)}$ or $n=18d(n)$ for $n=2^a\cdot 3^{b+1}\cdot p_1^{k_1}\cdots p_m^{k_m}$ (where $p_1<\cdots <p_m$ are prime numbers greater than $3$ and $a,b,k_1,\cdots ,k_m$ are positive integers); that is, $$2^{a-1}\cdot 3^{b-1}\cdot p_1^{k_1}\cdots p_m^{k_m}=(a+1)(b+2)(k_1+1)\cdots (k_m+1).\stackrel{◯}{1}$$ For every odd prime $p$ and every positive integer $k$, we can show (by an easy induction on $k$) that $$p^k>k+1.\stackrel{◯}{2}$$ Combining the last two relations, we deduce that $$2^{a-1}\cdot 3^{b-1}<(a+1)(b+2)$$ or $$f(a)=\frac{2^{a-1}}{a+1}<\frac{b+2}{3^{b-1}}=g(b).$$ It is easy to prove that $f(1)=\frac{1}{2}$, $f(2)=\frac{2}{3}$, $f(3)=1$, $f(4)=\frac{8}{5}$, $f(5)=\frac{16}{6}$, and $f(a)\ge \frac{32}{7}>4$ for $a\ge 6$. It is also easy to prove that $g(1)=3$, $g(2)=\frac{4}{3}$, $g(3)<\frac{5}{9}$, and $g(b)<\frac{2}{9}$ for $b\ge 4$. Thus $\stackrel{◯}{1}$ holds only if $b\le 3$.

If $b=3$, then $(a,b)=(1,3)$, and $\stackrel{◯}{1}$ becomes $$9p_1^{k_1}\cdots p_m^{k_m}=10(k_1+1)\cdots (k_m+1),$$ implying that $p_1=5$. Since $\stackrel{◯}{2}$ and $\frac{p_1^{k_1}}{k_1+1}=\frac{5^{k_1}}{k_1+1}\ge \frac{5}{2}$ for positive integer $k_1\ge 1$, we can easily see that there is no solution in this case.

If $b=2$, then $(a,b)=(1,2)$, $(2,2)$, $(3,2)$, and $\stackrel{◯}{1}$ becomes $$3\cdot 2^{a-1}{p}_1^{k_1}\cdots p_m^{k_m}=4(a+1)(k_1+1)\cdots (k_m+1).$$ We deduce that $4$ divides $2^{a-1}$ or $a\ge 3$. Hence $a$ must be equal to $3$. But then $4(a+1)=16$ divides $2^{a-1}$, which is impossible.

If $b=1$, then $(a,b)=(1,1)$, $(2,1)$, $(3,1)$, $(4,1)$, $(5,1)$, and $\stackrel{◯}{1}$ becomes $$2^{a-1}{p}_1^{k_1}\cdots p_m^{k_m}=3(a+1)(k_1+1)\cdots (k_m+1),$$ which is impossible since $p_i$ are primes greater than $3$.

In all the cases, we cannot find $n$ satisfying the condition $18=\frac{n}{d(n)}$; that is, $18$ is not a good number.