The problem is as follows :
Given a set A with distinct positive integer elements, prove that there always exists another set B consisting of positive integers, s.t.,
- The size of B is less than or equal to the size of A
- Each element of A can be represented as the sum of some subset of B
- The subset sums of all the elements of B are distinct
It's obvious that if we take all powers of 2 less than the largest element in A, we can construct B and the subset sums are distinct. But this doesn't necessarily meet condition 1.
Can someone give a construction for this?
Best Answer
The proof shall be by strong induction over the number of elements of $A$.
So we assume it has been proven for sets with $n$ elements or less.
now notice if we can prove it when the gcd of all the $n$ integers is $1$ we can use this to prove it when the numbers are not relatively prime by dividing all the numbers by the gcd, producing the appropriate generator set and then multiplying the elements of that set by the gcd.
Take elements $x_1,x_2\dots x_n$ and notice at least one of them is odd. Let $x_j$ be the smallest odd one. We define the new set $Y$ constructed as follows:
If $x_i$ is even add $\frac{x_i}{2}$
If $x_i$ is odd add $\frac{x_i-x_j}{2}$
Don't add $x_j$.
This set has less than $n$ elements, so we may use the inductive hypothesis. (Notice this new set may have a gcd different to $1$. But it doesn't matter, since our inductive hypothesis is the strong version of the result).
We construct an appropriate generating set $T'$ for this new set using the inductive hypothesis.
We propose the set $2T'\cup\{x_j\}$ as the desired set.
Hence we have proved it for when $A$ has $n$ elements with gcd equal to $1$. Using the method describe above we use this to prove it when $A$ has $n$ elements in general, completing the induction.