5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Algorithmically you could start with $B=A$ and remove elements until 3. is met, making sure that 2. always holds. Some work would be required that if 2. holds and $\sum B_1 = \sum B_2$ for some $B_1\ne B_2\subset B$ that we can remove (or replace) at least one element from either $B_1$ or $B_2$ such that 1. is not violated. WLOG we may assume that $B_1\cap B_2 = \emptyset$ $\endgroup$ – AlexR Dec 16 '14 at 16:36
  • $\begingroup$ The problem is the removal/replacement strategy. How do we replace? For e.g., A = 1,2,3,4 , set B = 1,2,3,4. Now since 4 = 1+3, we remove 4. But the only solution for this case is B = 1,2,4. So, removing 4 is not an option. $\endgroup$ – ZeroG Dec 16 '14 at 16:56
  • $\begingroup$ Are all the elements of $A$ non-negative? $\endgroup$ – JimmyK4542 Dec 17 '14 at 7:44
  • $\begingroup$ Yes. All elements of A are strictly positive. Let me add that to the problem statement. $\endgroup$ – ZeroG Dec 17 '14 at 9:19
  • $\begingroup$ does $B$ also have to be of positive integers? $\endgroup$ – Jorge Fernández Hidalgo Dec 17 '14 at 18:08
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The only niggle(albeit small) I see is that the smaller set that you construct might have repeated elements. For, e.g., $\frac{x_i}{2}$ could be equal to $\frac{x_i-x_j}{2}$. But we can prove that each element occurs at most twice and we can remove repeated elements. Also, the generator for odd and even will have exactly one different element and that would be $x_j$. $\endgroup$ – ZeroG Dec 20 '14 at 10:23
  • $\begingroup$ Yeah, but the repeated elements are not in the generating set, so it doesn't matter. $\endgroup$ – Jorge Fernández Hidalgo Dec 20 '14 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.