IMO shortlist 1993/23 solution

34th IMO 1993 shortlist

Problem 23

Show that for any finite set S of distinct positive integers, we can find a set T ⊇ S such that every member of T divides the sum of all the members of T.

Solution

Let S = {a₁, a₂, ... , a_r}. Put s = ∑ a_i, m = lcm(S). Suppose m = 2^kn, where n is odd. Put n = b_t...b₁b₀ in binary. Adjoin 2ⁱs for i>1 and b_i=1. The adjoined numbers have sum (n-1)s, so the enlarged set has sum ns. Now adjoin ns, 2ns, 2²ns, ... , 2^h-1ns, where h = max(k,t). The adjoined numbers have sum (2^h-1)ns, so the enlarged set T has sum 2^hns. All the members of T divide the sum.

34th IMO shortlist 1993