IMO 2016 Shortlisted Problems

Solution 1. Suppose all positive divisors of $n$ can be arranged into a rectangular table of size $k\times l$ where the number of rows $k$ does not exceed the number of columns $l$. Let the sum of numbers in each column be $s$. Since $n$ belongs to one of the columns, we have $s⩾n$, where equality holds only when $n=1$. For $j=1,2,\dots ,l$, let $d_j$ be the largest number in the $j$-th column. Without loss of generality, assume $d_1>d_2>\cdots >d_l$. Since these are divisors of $n$, we have $$d_l⩽\frac{n}{l}\text{\hspace{1em}(1)}$$ As $d_l$ is the maximum entry of the $l$-th column, we must have $$d_l⩾\frac{s}{k}⩾\frac{n}{k}\text{\hspace{1em}(2)}$$ The relations (1) and (2) combine to give $\frac{n}{l}⩾\frac{n}{k}$, that is, $k⩾l$. Together with $k⩽l$, we conclude that $k=l$. Then all inequalities in (1) and (2) are equalities. In particular, $s=n$ and so $n=1$, in which case the conditions are clearly satisfied.

Solution 2. Clearly $n=1$ works. Then we assume $n>1$ and let its prime factorization be $n=p_1^{r_1}{p}_2^{r_2}\cdots p_t^{r_t}$. Suppose the table has $k$ rows and $l$ columns with $1<k⩽l$. Note that $kl$ is the number of positive divisors of $n$ and the sum of all entries is the sum of positive divisors of $n$, which we denote by $\sigma (n)$. Consider the column containing $n$. Since the column sum is $\frac{\sigma (n)}{l}$, we must have $\frac{\sigma (n)}{l}>n$. Therefore, we have $$\begin{array}{rl}\left(r_1+1\right)\left(r_2+1\right)\cdots \left(r_t+1\right)& =kl⩽l^2<{\left(\frac{\sigma (n)}{n}\right)}^2\\ & ={\left(1+\frac{1}{p_1}+\cdots +\frac{1}{p_1^{r_1}}\right)}^2\cdots {\left(1+\frac{1}{p_t}+\cdots +\frac{1}{p_t^{r_t}}\right)}^2.\end{array}$$ This can be rewritten as $$\begin{array}{c}f\left(p_1,r_1\right)f\left(p_2,r_2\right)\cdots f\left(p_t,r_t\right)<1\end{array}\text{\hspace{1em}(3)}$$ where $$f(p,r)=\frac{r+1}{{\left(1+\frac{1}{p}+\cdots +\frac{1}{p^r}\right)}^2}=\frac{(r+1){\left(1-\frac{1}{p}\right)}^2}{{\left(1-\frac{1}{p^{r+1}}\right)}^2}$$ Direct computation yields $$f(2,1)=\frac{8}{9},f(2,2)=\frac{48}{49},f(3,1)=\frac{9}{8}$$ Also, we find that $$\begin{array}{rl}& f(2,r)⩾{\left(1-\frac{1}{2^{r+1}}\right)}^{-2}>1\text{ for }r⩾3\\ & f(3,r)⩾\frac{4}{3}{\left(1-\frac{1}{3^{r+1}}\right)}^{-2}>\frac{4}{3}>\frac{9}{8}\text{ for }r⩾2,\text{ and }\\ & f(p,r)⩾\frac{32}{25}{\left(1-\frac{1}{p^{r+1}}\right)}^{-2}>\frac{32}{25}>\frac{9}{8}\text{ for }p⩾5\end{array}$$ From these values and bounds, it is clear that (3) holds only when $n=2$ or 4 . In both cases, it is easy to see that the conditions are not satisfied. Hence, the only possible $n$ is 1 .