[Math] Set with distinct subset sums

arithmeticcombinatoricscontest-math

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.,

  1. The size of B is less than or equal to the size of A
  2. Each element of A can be represented as the sum of some subset of B
  3. 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.

  1. Clearly it satisfies it has $n$ elements or less.
  2. If $x_i$ is even we could have created $\frac{x_i}{2}$ from $T'$ so we can do $x_i$ from $2T'$. If $x_i$ is odd we could have created $\frac{x_i-x_j}{2}$ from $T$, so we can create $x_i-x_j$ from $2T$ and $x_i$ from $2T\cup\{x_j\}$
  3. The sums containing $x_j$ are all odd, the sums not containing $x_j$ are all even, so there is no overlap. The fact there are no two equal not containg $x_j$ is directly inherited from $T$ being as it is. If two sums containing $x_j$ where equal they would be equal after taking away $x_j$ from each set. Thus all subsets have different sums.

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.

Related Question