Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Drab Emordnilap]

Okay, so I'm looking for 8 positive intergers. There are two restrictions:

A: No member of the set of 8 integers is greater than the sum of any other pair of integers in the set. (For example, the set [1,1,2,2,3,3,4,4] is invalid because 1+1<4.)

B: For any two distinct subsets of the set, with a subset being defined as 1-3 integers from the set, the sums of the subsets should not be equal. (For example, the set [10,10,11,13,14,15,16,17] is invalid because 10+17=11+16.)

The examples are invalid in many ways other than the specific ones listed -- it's just that I can't even come up with examples that are only invalid in one way.

Is such a set possible to construct? If so, what is the set that fits these rules with the smallest sum of the whole set?


I'm not even sure where to begin solving this.

[Drab Emordnilap]

Okay, so the integers have to be unique, or else two subsets of each a single integer would have identical sums. And the two smallest integers have to sum to more than the largest integer, so that puts some bounds on the breadth of the set. That's all I have so far.

[silverspawn]

100, 101, 102, 104, 108, 116, 132, 164

[Drab Emordnilap]

100, 101, 102, 104, 108, 116, 132, 164

Wow. It seems so obvious in hindsight.

So [64,65,66,68,72,80,96,128] works for the same reason, I think. Any smaller with the same pattern and you can sum the smallest two to be less than the largest.

[Ozle]

Okay, so the integers have to be unique, or else two subsets of each a single integer would have identical sums. And the two smallest integers have to sum to more than the largest integer, so that puts some bounds on the breadth of the set. That's all I have so far.

................................moat?

[pacovf]

100, 101, 102, 104, 108, 116, 132, 164

Wow. It seems so obvious in hindsight.

So [64,65,66,68,72,80,96,128] works for the same reason, I think. Any smaller with the same pattern and you can sum the smallest two to be less than the largest.

Not necessarily. With silverspawn's answer, the sum of any two elements is necessarily smaller than the sum of any three elements (obv. the same holds true for one/two elements), so the interesting property of the decomposition in powers of two (unicity) is "conserved" when adding a constant to all powers of two. I'm not being entirely clear, but it makes sense in my head.

This is not true for your solution (128+96=224 > 64+65+66=195), so it is not "trivially" true that condition B is conserved when you add 64 to the powers of two. It might be true, it might not be, I am not checking.

The smallest version of silverspawn's solution is 94, 95, 96, 98, 104, 112, 128, 160.

EDIT: thinking about it a bit more, your solution does work, although the reason it works is slightly less obvious.

[Kirian]

it is not "trivially" true that condition B is conserved when you add 64 to the powers of two. It might be true, it might not be, I am not checking.

The smallest version of silverspawn's solution is 94, 95, 96, 98, 104, 112, 128, 160.

Don't these two statements contradict one another?  And how did you get your "smallest" solution?

[sudgy]

There's no way to get a crazier solution mixing positive and negative integers, right?

[Ozle]

There's no way to get a crazier solution mixing positive and negative integers, right?

There is always a way of getting a crazier solution!

[StephenHas]

you might be able to use a system of inequations, label vars a, b, c,...
make matrices and then use matlab (or a free equivalent)
idk how though


[64, 65, 66, 68, 71, 77, 88, 108]
works I think, but there might be smaller sets

Positive integers was a requirement in the problem statement.

[GeoLib]

you might be able to use a system of inequations, label vars a, b, c,...
make matrices and then use matlab (or a free equivalent)
idk how though


[64, 65, 66, 68, 71, 77, 88, 108]
works I think, but there might be smaller sets

Positive integers was a requirement in the problem statement.

There is a fast method for optimizing an objective function subject to a systems of inequality constraints (the simplex algorithm), but doing it with integers is NP-hard (i.e. it isn't likely that MATLAB will be able to solve it for you quickly).

[Jack Rudd]

I think this gives another interesting set of solutions, although not small at all:

3*5*7*11*13*17*19
4*5*7*11*13*17*19
2*9*7*11*13*17*19
8*3*5*11*13*17*19
4*9*5*7*13*17*19
16*3*5*7*11*17*19
2*27*5*7*11*13*19
8*9*5*7*11*13*17

[pacovf]

it is not "trivially" true that condition B is conserved when you add 64 to the powers of two. It might be true, it might not be, I am not checking.

The smallest version of silverspawn's solution is 94, 95, 96, 98, 104, 112, 128, 160.

Don't these two statements contradict one another?  And how did you get your "smallest" solution?

As I didn't explain very well in my previous post, my smallest solution verifies that, for any three numbers, their sum is higher than any two number sum. This means that, because subsets have at most three elements, any two subsets cannot have the same sum if they have a different number of elements. And as long as you are taking subsets with the same number of elements, adding a constant to all your elements doesn't change whether two subsets have the same sum or not.

My "smallest" solution is 0,1,2,4,8,16,32,64 (because unicity of decomposition of powers of two, and also zero, since subsets have to be disjoint), to which I add x to each number. If I add x randomly, a priori I don't keep condition B. If I add x such that (x+0) + (x+1) + (x+2) > (x+32) + (x+64) and (x+0) + (x+1) > (x+64), and I pick the smallest x that satisfies the equation, then necessarily any two subsets with a different number of elements have a different sum, and for subsets with the same number of elements I can just go back to the original powers of 2.

Does this make a little bit more sense?

[Rabid]

Can you use {0, 1, 2, 4, 8, 15, 28, 52} instead of {0,1,2,4,8,16,32,64}, because we are only using subsets of 1 to 3 elements?

[eHalcyon]

An easy way to satisfy A is to add a constant c to each member of the set, where c is equal to or larger than the largest number in the set.

If we have the set [x, y and z] where z is largest, we can add z to every element.  Then the new set [x+z, y+z, 2z].  The sum of the two smallest elements is 2z+x+y, which is of course larger than 2z.

(Edit: we can actually use a constant that is smaller than z, because condition A does not require the single element to be smaller than the sum of any two elements; it just can't be larger.  That means it can still be equal!  If we use z-1, then the new set would be [x+z-1, y+z-1, 2z-1] and the sum of the two smallest elements would be 2z+x+y-2.  If x+y = 1, then the sum is equal to the largest element and the condition is still satisfied.)



An easy way to satisfy B is to make each subsequent number the sum of all previous numbers plus a constant > 0.  Then your set will be:

[a, a+b, 2a+2b, 4a+4b, 8a+8b...]

If you use a = 1 and b = 1, then you just get powers of 2.

Because of the way that the numbers grow, it is impossible to make two subsets equal.  Suppose you have a subset S₁ where the highest number is x.  When you construct the second subset S₂, if you use a number from the set that is larger than x, it is guaranteed to be larger than sum of values in S₁.  If you do not use a number larger than x, then the sum of values in S₂ is guaranteed to be smaller.



Combining these two methods shouldn't cause any conflict.  The constant c is already large enough that any equality in sums should still be impossible.  That is, the constants guarantee that the sum of S₁ will always be larger than the sum of S₂ if |S₁| > |S₂|.  If the two subsets have the same cardinality, then method B guarantees inequality (adding the same constant to either side changes nothing).


Assuming I haven't done something stupid in this thought process, the smallest version of my solution would be...

Well, for method B, we can use [0, 1, 2, 4, 8, 16, 32, 64].  We can start with 0 because we are going to add a constant anyways.

For this set with method A, we need to add 64.  So then the final set is [64, 65, 66, 68, 72, 80, 96, 128].

That is the set that Drab mentions immediately after silverspawn's solution.  There probably are smaller sets that take advantage of the fact that subsets are restricted to a maximum of 3 elements.

(Edit: we could actually use a constant of 63, as per my edit for method A above.  So the set would be [63, 64, 65, 67, 71, 79, 95, 127].)

(Edit edit: no, that doesn't work.  63+64+65 = 127+65.)

I am not sure how pacovf found his "smallest version of silverspawn's solution".


(Edit edit: OK, this is more complicated than I'd thought...)

[eHalcyon]

Can you use {0, 1, 2, 4, 8, 15, 28, 52} instead of {0,1,2,4,8,16,32,64}, because we are only using subsets of 1 to 3 elements?

Yes I think so.  The idea is to just take the sub of the previous 3 elements instead, right?  15 > 2+4+8; 28 > 15+8+4; 52 > 28+15+8.

Then to satisfy condition A, we would just have to add 52 to each element.  And we get:

[52, 53, 54, 56, 60, 67, 80, 104]

Hmm... actually, condition A only says that no element is greater than the sum of two other elements.  They could still be equal!  Which means that the constant to add could be 1 smaller:

[51, 52, 53, 55, 59, 66, 79, 103]

Edit: no, this second set doesn't work.  51+52+53 = 103+53.

[pacovf]

That is, the constants guarantee that the sum of S₁ will always be larger than the sum of S₂ if |S₁| > |S₂|.

I agree with everything but this. See:

(128+96=224 > 64+65+66=195)

Drab's/your solution still works, but it is slightly trickier to prove. Note that, for example, it doesn't work if you add 65 instead of 64 (129+69 = 65+66+67), yet your reasoning would imply that it does.

Hint: the fact that you add 64, a power of two, is why your solution still works.

EDIT: my solution is the smallest one that verifies the condition you exposed in the quoted part.

[eHalcyon]

That is, the constants guarantee that the sum of S₁ will always be larger than the sum of S₂ if |S₁| > |S₂|.

I agree with everything but this. See:

(128+96=224 > 64+65+66=195)

Drab's/your solution still works, but it is slightly trickier to prove. Note that, for example, it doesn't work if you add 65 instead of 64 (129+69 = 65+66+67), yet your reasoning would imply that it does.

Hint: the fact that you add 64, a power of two, is why your solution still works.

EDIT: my solution is the smallest one that verifies the condition you exposed in the quoted part.

Darn, where does the reasoning go wrong that adding 65 doesn't work?  Hmm....

[Kirian]

That is, the constants guarantee that the sum of S₁ will always be larger than the sum of S₂ if |S₁| > |S₂|.

I agree with everything but this. See:

(128+96=224 > 64+65+66=195)

Drab's/your solution still works, but it is slightly trickier to prove. Note that, for example, it doesn't work if you add 65 instead of 64 (129+69 = 65+66+67), yet your reasoning would imply that it does.

Hint: the fact that you add 64, a power of two, is why your solution still works.

EDIT: my solution is the smallest one that verifies the condition you exposed in the quoted part.

Darn, where does the reasoning go wrong that adding 65 doesn't work?  Hmm....

I'm on mobile and can't do anything formal, but you can make 3k + 1 + 2 from k + 4 and k + 64 when k = 65.  So basically no two powers of two can add up to k plus two other powers of two.

[scott_pilgrim]

Hmm... actually, condition A only says that no element is greater than the sum of two other elements.  They could still be equal!  Which means that the constant to add could be 1 smaller:

[51, 52, 53, 55, 59, 66, 79, 103]

Edit: no, this second set doesn't work.  51+52+53 = 103+53.

Condition A doesn't specify that they can't be equal, but condition B does.

[eHalcyon]

Hmm... actually, condition A only says that no element is greater than the sum of two other elements.  They could still be equal!  Which means that the constant to add could be 1 smaller:

[51, 52, 53, 55, 59, 66, 79, 103]

Edit: no, this second set doesn't work.  51+52+53 = 103+53.

Condition A doesn't specify that they can't be equal, but condition B does.

Oops. 

[Kirian]

it is not "trivially" true that condition B is conserved when you add 64 to the powers of two. It might be true, it might not be, I am not checking.

The smallest version of silverspawn's solution is 94, 95, 96, 98, 104, 112, 128, 160.

Don't these two statements contradict one another?  And how did you get your "smallest" solution?

As I didn't explain very well in my previous post, my smallest solution verifies that, for any three numbers, their sum is higher than any two number sum. This means that, because subsets have at most three elements, any two subsets cannot have the same sum if they have a different number of elements. And as long as you are taking subsets with the same number of elements, adding a constant to all your elements doesn't change whether two subsets have the same sum or not.

My "smallest" solution is 0,1,2,4,8,16,32,64 (because unicity of decomposition of powers of two, and also zero, since subsets have to be disjoint), to which I add x to each number. If I add x randomly, a priori I don't keep condition B. If I add x such that (x+0) + (x+1) + (x+2) > (x+32) + (x+64) and (x+0) + (x+1) > (x+64), and I pick the smallest x that satisfies the equation, then necessarily any two subsets with a different number of elements have a different sum, and for subsets with the same number of elements I can just go back to the original powers of 2.

Does this make a little bit more sense?

If I'm understanding correctly, you can show that k >= 94 works without going through and manually checking everything from 94 and higher, while you can't show the same for K >= 64, at least not by the same line of reasoning.

[pacovf]

Exactly!

Basically, there are too many ways to make 2 disjoint subsets as to check manually whether condition B is satisfied, so you need to prove it for all possible subsets pairs at once. There is a simple way to do so for k>= 94, and none for k taken in [64, 93]. You need to look at it case by case, I think.

It works for 64 though (I don't really feel like proving it, the concept is simple but hard to write down), which is the smallest version of this solution.

However, adding the largest number to all numbers of Rabid's solution wouldn't satisfy condition B (I think), because his "reduced" solution is not as constrained as the powers of two.

[blueblimp]

This is surprisingly feasible with computer search. Here's the smallest example I found, where by "smallest" I mean "lexicographically smallest when ordered from largest integer to smallest integer", which means it wants the largest integer to be as small as possible, then the second largest integer, and so on.

Code: [Select]

       8:  79 76 74 73 72 65 54 35

SUBSET SUMS:
79           =  79
79 + 76      = 155
79 + 76 + 74 = 229
79 + 76 + 73 = 228
79 + 76 + 72 = 227
79 + 76 + 65 = 220
79 + 76 + 54 = 209
79 + 76 + 35 = 190
79 + 74      = 153
79 + 74 + 73 = 226
79 + 74 + 72 = 225
79 + 74 + 65 = 218
79 + 74 + 54 = 207
79 + 74 + 35 = 188
79 + 73      = 152
79 + 73 + 72 = 224
79 + 73 + 65 = 217
79 + 73 + 54 = 206
79 + 73 + 35 = 187
79 + 72      = 151
79 + 72 + 65 = 216
79 + 72 + 54 = 205
79 + 72 + 35 = 186
79 + 65      = 144
79 + 65 + 54 = 198
79 + 65 + 35 = 179
79 + 54      = 133
79 + 54 + 35 = 168
79 + 35      = 114
76           =  76
76 + 74      = 150
76 + 74 + 73 = 223
76 + 74 + 72 = 222
76 + 74 + 65 = 215
76 + 74 + 54 = 204
76 + 74 + 35 = 185
76 + 73      = 149
76 + 73 + 72 = 221
76 + 73 + 65 = 214
76 + 73 + 54 = 203
76 + 73 + 35 = 184
76 + 72      = 148
76 + 72 + 65 = 213
76 + 72 + 54 = 202
76 + 72 + 35 = 183
76 + 65      = 141
76 + 65 + 54 = 195
76 + 65 + 35 = 176
76 + 54      = 130
76 + 54 + 35 = 165
76 + 35      = 111
74           =  74
74 + 73      = 147
74 + 73 + 72 = 219
74 + 73 + 65 = 212
74 + 73 + 54 = 201
74 + 73 + 35 = 182
74 + 72      = 146
74 + 72 + 65 = 211
74 + 72 + 54 = 200
74 + 72 + 35 = 181
74 + 65      = 139
74 + 65 + 54 = 193
74 + 65 + 35 = 174
74 + 54      = 128
74 + 54 + 35 = 163
74 + 35      = 109
73           =  73
73 + 72      = 145
73 + 72 + 65 = 210
73 + 72 + 54 = 199
73 + 72 + 35 = 180
73 + 65      = 138
73 + 65 + 54 = 192
73 + 65 + 35 = 173
73 + 54      = 127
73 + 54 + 35 = 162
73 + 35      = 108
72           =  72
72 + 65      = 137
72 + 65 + 54 = 191
72 + 65 + 35 = 172
72 + 54      = 126
72 + 54 + 35 = 161
72 + 35      = 107
65           =  65
65 + 54      = 119
65 + 54 + 35 = 154
65 + 35      = 100
54           =  54
54 + 35      =  89
35           =  35
Code at https://github.com/malcolmsharpe/fds-int-set-solver. It could be sped up by a factor of like ~50x where I have the TODO to use a lookup table, but it turns out not to be necessary.

[Ratsia]

There is a fast method for optimizing an objective function subject to a systems of inequality constraints (the simplex algorithm), but doing it with integers is NP-hard (i.e. it isn't likely that MATLAB will be able to solve it for you quickly).

It is still good to remember that NP-hard does not mean slow for small problems. State-of-the-art integer programming solvers (CPLEX and others) would solve problems this small probably immediately, and more generally a lot of NP-hard problems can be solved efficiently for surprisingly large number of variables unless you start explicitly constructing the hardest possible instances. Consequently, one shouldn't automatically assume NP-hard problems to be too slow to compute. Too often people say "this is TSP, so there's no hope" whereas in practice TSPs of modest size are easy with standard solvers and even problems with tens of thousands of nodes can be solved exactly (this is naturally slow).