Finding a set of maximal sum , such that no two subsets have the same sum.

If $$S$$ represents the set {$$1,2,3,...,10$$} , then find a subset $$X$$ such that the sum of the elements of $$X$$ is maximum , and no two subsets of $$X$$ have the same sum .

A bit of trial and error shows that the greedy algorithm works , when the number of elements of $$S$$ is less .

For example , if $$S$$ = {$$1,2,3,4$$} , the greedy algorithm yields $$X$$ = {$$2,3,4$$} , which is indeed the answer , yielding a maximal sum of $$2+3+4=9$$ .

However , I have not been able to prove that the greedy algorithm works . Basically , if $$X_n$$ represents a subset of maximal sum satisfying the problem-condition (where $$n$$ represents the cardinality of the subset) , I have to prove that if there exists $$X_{n+1}$$ , then $$X_n \subset X_{n+1}$$ .

Any help would be greatly appreciated.

First of all, your statement that $$X_n\subset X_{n+1}$$ is not correct. The conjecture that has to be proved is the following:

Assume that $$X_n=\{a_1,a_2,\dots,a_k\}$$ is the solution for a set of cardinality $$n$$. Then $$X'_n=\{a_1+1,a_2+1,\dots,a_k+1\}\subset X_{n+1}$$

All that you need to prove the statement (and much more) can be found in the following paper:

Sums of lexicographically ordered sets

It's not an easy reading but at the hart of it is the OEIS sequence A005255 (Atkinson-Negro-Santoro): "For each $$n$$, the $$n$$-term sequence ($$b_k = a_n - a_{n-k}, 1 \le k \le n$$), has the property that all $$2^n$$ sums of subsets of the terms are distinct."

The sequence goes like this:

0, 1, 2, 4, 7, 13, 24, 46, 88, 172, 337, 667, 1321, 2629, 5234, 10444, 20842, 41638, 83188, 166288, 332404, 664636, 1328935, 2657533, 5314399, 10628131, 21254941, 42508561, 85014493, 170026357, 340047480, 680089726, 1360169008, 2720327572

How do you find the solution for a set of cardinality $$n$$? Suppose, for example, that $$n$$=200.

Step (1): Find the greatest number $$m$$ in the sequence that is less or equal to $$n$$. In our particular case: $$m$$=172

Step (2): Take all the numbers from the sequence that are smaller than $$m$$. In our case those numbers are: 0, 1, 2, 4, 7, 13, 24, 46, 88.

Step (3): Now calculate the difference between $$n$$ and numbers isolated in step (2): 200-88=112, 200-46=154, 200-24=176, 200-13=187, 200-7=193, 200-4=196, 200-2=198, 200-1=199, 200-0=200

Numbers calculated in step (3) are the actual solution of the problem:

$$X_{200}=\{112, 154, 176, 187, 193, 196, 198, 199, 200\}$$

The following code is lightning fast and provides solution for any "reasonable" $$n$$ (even when $$n$$ has 50 digits):

cache = [0, 1]

# OEIS A005255
def a(i):
if i < len(cache):
return cache[i]
else:
j = i - 1 - (i + 1) // 2
result = 2 * a(i - 1) - a(j)
cache.append(result)
return result

def solve(n):
# find the biggest a(i) such that a(i) <= n
i = 0;
while a(i) <= n:
i += 1
j = i - 1
return [n - a(k) for k in range(j - 1, -1, -1)]


Some examples:

print(solve(100))
# prints [54, 76, 87, 93, 96, 98, 99, 100]

print(solve(100000))
# prints [58362, 79158, 89556, 94766, 97371, 98679, 99333, 99663, 99828, 99912, 99954, 99976, 99987, 99993, 99996, 99998, 99999, 100000]


And for $$n=1,000,000,000$$ the solution is:

[659952520, 829973643, 914985507, 957491439, 978745059, 989371869, 994685601, 997342467, 998671065, 999335364, 999667596, 999833712, 999916812, 999958362, 999979158, 999989556, 999994766, 999997371, 999998679, 999999333, 999999663, 999999828, 999999912, 999999954, 999999976, 999999987, 999999993, 999999996, 999999998, 999999999, 1000000000]

• So the greedy algorithm does seem to work ? I mean , in each case , the cardinality of $X$ is increased by appending the optimal and maximal element from $S$. Is there any mathematically rigorous way of proving the same? – Aspirant Mar 6 at 4:37
• I refuse to look further into this without an upvote :)))) – Oldboy Mar 6 at 6:32
• No blackmailing! ;) – Aspirant Mar 6 at 15:03
• After two days of research I have completely reworked my answer. – Oldboy Mar 9 at 12:12
• I really appreciate the help , but I think my conjecture was misinterpreted . It is merely restating the greedy algorithm . For example , if $S=${$1,2,3,4,5$} , $X_2=${$4,5$}, while $X_3=${$3,4,5$} . Clearly , $X_2 \subset X_3$ . However , here , the conjecture you stated doesn’t hold . Please note that the $n$ I mentioned isn’t the cardinality of the set , but the cardinality of the $subset$ – Aspirant Mar 11 at 5:06