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.
Answer : 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 . Since these are divisors of n, we have
As dl is the maximum entry of the l-th column, we must have
The relations (1) and (2) combine to give , that is, . Together with 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.