Timeline for When are all sums of the elements of a set different?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 22, 2014 at 14:51 | comment | added | joro | From rationals you can scale to integers by multiplying by the lcm of the denominators. If all integers are positive and $\sum x_i < 2^n$ I think there are two equal sum subsets. | |
| Oct 22, 2014 at 14:17 | comment | added | rodms | Thanks for your comments, they are very insightful! @joro I'm not concerned about the computability of the decision problem, I just need to know if the set satisfies the distinct subset sums property with some probability! | |
| Oct 22, 2014 at 13:55 | comment | added | Lucia | In the additive combinatorics literature such sets are called ``dissociated". | |
| Oct 22, 2014 at 13:18 | answer | added | joro | timeline score: 2 | |
| Oct 22, 2014 at 13:08 | comment | added | Ben Barber | It does not matter whether you allow $I$ and $J$ to intersect, as replacing $I$ by $I \setminus J$ and $J$ by $J \setminus I$ will preserve equality. | |
| Oct 22, 2014 at 13:07 | comment | added | Ben Barber | There may be no better name than distinct subset sums. | |
| Oct 22, 2014 at 13:04 | comment | added | joro | OK. If you disallow intersection, it is NP-complete over the naturals. | |
| Oct 22, 2014 at 13:03 | comment | added | rodms | @joro No, I and J can intersect as long as I \neq J. | |
| Oct 22, 2014 at 12:45 | comment | added | joro | Related: oeis.org/A201052 | |
| Oct 22, 2014 at 12:38 | comment | added | joro | Do you require I and J to have empty intersection? | |
| Oct 22, 2014 at 12:23 | history | asked | rodms | CC BY-SA 3.0 |