Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question is more practically understood by example. I need a set A that behaves like the one below:

Set A: {1,3,5}

Set B (all subsets of A): {1}, {3}, {5}, {1,3}, {1,5}, {3,5}, {1,3,5}

Set C (summations of each element of B): {1}, {3}, {5}, {4}, {6}, {8}, {9}

Because every element of C is of unique value (that's the criteria), what I have is: every element of C identifies a specific combination of elements of A. If I am given 4, I know it's the sum of the specific elements 1 and 3 and no other possible combination of elements, and so forth for any given element of C.

To create a set A of 3 elements is easy, but I need the largest possible set A that contains only 2 digit natural numbers (from 01 to 99) matching this criteria. I need also to be able to find the matching elements of A from any given element of C (if I'm given 9 I need to know it refers to the elements 1+3+5 and so forth for any given sum).

Can anyone help me?

share|improve this question

2 Answers 2

See OEIS sequence A096858. The 8-element set {40,60,71,77,80,82,83,84} has all its subset sums distinct, so this beats Alex's 7-element answer.

share|improve this answer
    
Awesome too! Thanks. –  juanpazos Aug 20 at 4:52

Use the powers of $2$: $\{1, 2, 4, 8, 16, 32, 64\}$. Each subset sums to a unique number between $0$ and $127$, and it's easy to convert back just by calculating the binary (base 2) representation of the given number.

Edit: As Robert Israel's answer shows, the powers of $2$ are not necessarily optimal if you maximize the size of a set satisfying your condition with all elements below a certain bound (100 in your case). However, they are optimal in the reverse sense: if you specify the size of the set you want and try to minimize the size of the largest element.

Edit 2: Oops, that's also wrong. At least I can say with complete confidence that if you want a set of size $n$ with distinct subset sums and you want to minimize the largest sum (i.e. the sum of the whole list), then the first $n$ powers of $2$ are best (You'll need $2^n$ distinct sums, and each sum must be at least $0$, so the largest one must be at least $2^n-1$. The first $n$ powers of $2$ sum to exactly $2^n-1$). It's also hard to beat them for simplicity of the algorithm to translate the sum back to the subset.

share|improve this answer
    
If you specify size $7$, $\{20,31,37,40,42,43,44\}$ beats your $\{1,2,4,8,16,32,64\}$. If you specify size 8, $\{ 40,60,71,77,80,82,83,84\}$ beats $\{1,2,4,8,16,32,64,128\}$. –  Robert Israel Aug 20 at 3:21
    
Ah, darn, you're right. –  Alex Kruckman Aug 20 at 3:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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