6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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]
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Aspirant Mar 6 at 4:37
  • $\begingroup$ I refuse to look further into this without an upvote :)))) $\endgroup$ – Oldboy Mar 6 at 6:32
  • $\begingroup$ No blackmailing! ;) $\endgroup$ – Aspirant Mar 6 at 15:03
  • 1
    $\begingroup$ After two days of research I have completely reworked my answer. $\endgroup$ – Oldboy Mar 9 at 12:12
  • $\begingroup$ 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$ $\endgroup$ – Aspirant Mar 11 at 5:06

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.