Maths Olympiad Prep

Library / Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads /42 of 80

Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

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 s≥n+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/dk≥kn/d_k \ge k; that is, dk≤n/kd_k \le n/k.
Since dkd_k is maximal along the kk-th row,
dk≥s/ℓ>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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.