14th Mexico 2000 Problem A3 If A is a set of positive integers, take the set A' to be all elements which can be written as ± a 1 ± a 2 ... ± a n , where a i are distinct elements of A. Similarly, form A" from A'. What is the smallest set A such that A" contains all of 1, 2, 3, ... , 40?
3 elements, eg {1,5,25} Solution A = {1,5,25} works. We get A' = {1,4,5,6,19,20,21,24,25,26,29,30,31}. Then A" includes all n ≤ 40. Suppose A = {a,b} works with a < b. Then A' = {a,b-a,b,b+a}. Now A" has at most 81 elements - for each element x ∈ A' we can include +x, -x or 0 in the sum, a total of 81 possibilities. However, this includes the empty sum 0. Also for every positive k ∈ A", -k is also included (reversing each sign in the sum). So at best A" can include 40 positive elements. But a and b - (b-a) are the same, so A" must include less than 40 positive elements. 14th Mexican 2000 © John Scholes jscholes@kalva.demon.co.uk 9 March 2004 Last corrected/updated 9 Mar 04