6
$\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$
6
  • 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, 2014 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, 2014 at 16:56
  • $\begingroup$ Are all the elements of $A$ non-negative? $\endgroup$
    – JimmyK4542
    Dec 17, 2014 at 7:44
  • $\begingroup$ Yes. All elements of A are strictly positive. Let me add that to the problem statement. $\endgroup$
    – ZeroG
    Dec 17, 2014 at 9:19
  • $\begingroup$ does $B$ also have to be of positive integers? $\endgroup$
    – Asinomás
    Dec 17, 2014 at 18:08

1 Answer 1

4
$\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$
2
  • $\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, 2014 at 10:23
  • $\begingroup$ Yeah, but the repeated elements are not in the generating set, so it doesn't matter. $\endgroup$
    – Asinomás
    Dec 20, 2014 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.