Maths Olympiad Prep

Library / /12 of 15

Combinatorics Difficulty 8.2 Shortlist Prove it Romania

Show that the positive divisors of no integer greater than 11 may be placed in the cells of a rectangular array so that the four conditions below be simultaneously fulfilled:
(a) each cell contains exactly one divisor;
(b) distinct cells contain distinct divisors;
(c) the sum of the divisors on each row is the same; and
(d) the sum of the divisors on each column is the same.

Solution

Suppose, if possible, that the positive divisors of some integer n>1n > 1 may be arranged as required in an k×k \times \ell rectangular array, where kk is the number of rows, and \ell is the number of columns; clearly, kk and \ell must both be greater than 11.
Let ss be the common value of the row sums, and notice that sn+1s \ge n + 1.
Let did_i be the largest divisor on the ii-th row, i=1,,ki = 1, \dots, k. Assume, without any loss, d1>>dkd_1 > \dots > d_k, to infer that the n/din/d_i, i=1,,ki = 1, \dots, k, form a strictly increasing kk-element string of positive integers, so n/dkkn/d_k \ge k; that is, dkn/kd_k \le n/k.
Since dkd_k is maximal along the kk-th row,
dks/>n/, d_k \ge s/\ell > n/\ell,
so >k\ell > k, by the preceding (in fact, dk>s/d_k > s/\ell, since the divisors are pairwise distinct).
Mutatis mutandis, k>k > \ell, and we reach a contradiction.

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.