Maths Olympiad Prep

Library / /25 of 55

, 2016

Number theory Difficulty 8.7 Shortlist Prove it IMO

Find all positive integers nn for which all positive divisors of nn can be put into the cells of a rectangular table under the following constraints:
- each cell contains a distinct divisor;
- the sums of all rows are equal; and
- the sums of all columns are equal.

Solution

Solution 1. Suppose all positive divisors of nn can be arranged into a rectangular table of size k×lk \times l where the number of rows kk does not exceed the number of columns ll. Let the sum of numbers in each column be ss. Since nn belongs to one of the columns, we have sns \geqslant n, where equality holds only when n=1n=1.
For j=1,2,,lj=1,2, \ldots, l, let djd_{j} be the largest number in the jj-th column. Without loss of generality, assume d1>d2>>dld_{1}>d_{2}>\cdots>d_{l}. Since these are divisors of nn, we have
dlnl(1) d_{l} \leqslant \frac{n}{l} \tag{1}
As dld_{l} is the maximum entry of the ll-th column, we must have
dlsknk(2) d_{l} \geqslant \frac{s}{k} \geqslant \frac{n}{k} \tag{2}
The relations (1) and (2) combine to give nlnk\frac{n}{l} \geqslant \frac{n}{k}, that is, klk \geqslant l. Together with klk \leqslant l, we conclude that k=lk=l. Then all inequalities in (1) and (2) are equalities. In particular, s=ns=n and so n=1n=1, in which case the conditions are clearly satisfied.

Solution 2. Clearly n=1n=1 works. Then we assume n>1n>1 and let its prime factorization be n=p1r1p2r2ptrtn=p_{1}^{r_{1}} p_{2}^{r_{2}} \cdots p_{t}^{r_{t}}. Suppose the table has kk rows and ll columns with 1<kl1<k \leqslant l. Note that klk l is the number of positive divisors of nn and the sum of all entries is the sum of positive divisors of nn, which we denote by σ(n)\sigma(n). Consider the column containing nn. Since the column sum is σ(n)l\frac{\sigma(n)}{l}, we must have σ(n)l>n\frac{\sigma(n)}{l}>n. Therefore, we have
(r1+1)(r2+1)(rt+1)=kll2<(σ(n)n)2=(1+1p1++1p1r1)2(1+1pt++1ptrt)2. \begin{aligned} \left(r_{1}+1\right)\left(r_{2}+1\right) \cdots\left(r_{t}+1\right) & =k l \leqslant 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{aligned}
This can be rewritten as
f(p1,r1)f(p2,r2)f(pt,rt)<1 \begin{equation*} f\left(p_{1}, r_{1}\right) f\left(p_{2}, r_{2}\right) \cdots f\left(p_{t}, r_{t}\right)<1 \tag{3} \end{equation*}
where
f(p,r)=r+1(1+1p++1pr)2=(r+1)(11p)2(11pr+1)2 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)=89,f(2,2)=4849,f(3,1)=98 f(2,1)=\frac{8}{9}, \quad f(2,2)=\frac{48}{49}, \quad f(3,1)=\frac{9}{8}
Also, we find that
f(2,r)(112r+1)2>1 for r3f(3,r)43(113r+1)2>43>98 for r2, and f(p,r)3225(11pr+1)2>3225>98 for p5 \begin{aligned} & f(2, r) \geqslant\left(1-\frac{1}{2^{r+1}}\right)^{-2}>1 \quad \text{ for } r \geqslant 3 \\ & f(3, r) \geqslant \frac{4}{3}\left(1-\frac{1}{3^{r+1}}\right)^{-2}>\frac{4}{3}>\frac{9}{8} \quad \text{ for } r \geqslant 2, \text{ and } \\ & f(p, r) \geqslant \frac{32}{25}\left(1-\frac{1}{p^{r+1}}\right)^{-2}>\frac{32}{25}>\frac{9}{8} \quad \text{ for } p \geqslant 5 \end{aligned}
From these values and bounds, it is clear that (3) holds only when n=2n=2 or 4 . In both cases, it is easy to see that the conditions are not satisfied. Hence, the only possible nn is 1 .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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