IMO 1993 SL 23

Origin: GBR

Problem

A finite set of (distinct) positive integers is called a “DS-set” if each of the integers divides the sum of them all. Prove that every finite set of positive integers is a subset of some DS-set.

Solution

Let the given numbers be a1, . . . , an. Put s = a1 + \cdot \cdot \cdot + an and m = lcm(a1, . . . , an) and write m = 2kr with k \geq0 and r odd. Let the binary expansion of r be r = 2k0 + 2k1 + \cdot \cdot \cdot + 2kt, with 0 = k0 < \cdot \cdot \cdot < kt. Adjoin to the set {a1, . . . , an} the numbers 2kis, i = 1, 2, . . ., t. The sum of the enlarged set is rs. Finally, adjoin rs, 2rs, 22rs, . . . , 2l−1rs for l = max{k, kt}. The resulting set has sum 2lrs, which is divisible by m and so by each of aj, and also by the 2is above and by rs, 2rs, . . . , 2l−1rs. Therefore this is a DS-set. Second solution. We show by induction that there is a DS-set containing 1 and n. For n = 2, 3, take {1, 2, 3}. Assume that {1, n, b1, . . . , bk} is a DS- set. Then {1, n + 1, n, 2(n + 1)n, 2(n + 1)b1, . . . , 2(n + 1)bk} is a DS-set too. For given a1, . . . , an let m be a sufficiently large common multiple of the ai’s such that u = m −(a1 + \cdot \cdot \cdot + an) ̸= ai for all i. There ex- ist b1, . . . , bk such that {1, u, b1, . . . , bk} is a DS-set. It is clear that {a1, . . . , an, u, mu, mb1, . . . , mbk} is a DS-set containing a1, . . . , an.