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.

Also Read:

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)


Like us on Facebook

%d bloggers like this: