# Solution problem 2 about combinatoric in Shortlist problem in IMO 2016

Problem Combinatoric 2

Find all positive integers n for which all positive divisors of n 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 1.

Suppose all positive divisors of n can be arranged into a rectangular table of size k x 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,…l, let d be the largest number in the j-th column. Without loss of generality, assume $d_1>d_2>...>d_l$. Since these are divisors of n, we have

$d_l\leqslant \frac{n}{l}$ …………(1)

As dl is the maximum entry of the l-th column, we must have

$d_l\geqslant \frac{s}{k}\geqslant \frac{n}{k}$ ……………(2)

The relations (1) and (2) combine to give $\frac{n}{l}\geqslant \frac{n}{k}$, that is, $k\geqslant l$. Together with $k\leqslant 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.

Also Read :  Shortlist problem Combinatorics in IMO 2016 ( international mathematic Olympiad)