IMO 1979 SL 18

Origin: POL

Problem

Let m positive integers a1, . . . , am be given. Prove that there exist fewer than 2m positive integers b1, . . . , bn such that all sums of dis- tinct bk’s are distinct and all ai (i \leqm) occur among them.

Solution

Let us write all ai in binary representation. For S \subseteq{1, 2, . . ., m} let us define b(S) as the number in whose binary representation ones appear in exactly the slots where ones appear in all ai where i \subseteqS and don’t appear in any other ai. Some b(S), including b(\emptyset), will equal 0, and hence there are fewer than 2m different positive b(S). We note that no two positive b(S1) and b(S2) (S1 ̸= S2) have ones in the same decimal places. Hence sums of distinct b(S)’s are distinct. Moreover ai =  i\inS b(S) and hence the positive b(S) are indeed the numbers b1, . . . , bn whose ex- istence we had to prove.