1

I'm attempting to create a scoring system for a card game which would preclude ties in scoring, by setting the point value of each card such that no two combinations of cards could add up to the same score. (For this particular case, I need a set of 17 integers, since there are 17 scorable cards.)

I've tried several heuristic approaches (various winnowing procedures along the lines of taking an array of integers, iteratively generating random subsets, and discard those which appear in subsets sharing a common sum); then exhaustively validating the results (by enumerating their subsets).

From what I've seen, the theoretical limit to the size of such a set is near log2(n), where n is the number of members of the superset from which the subset-distinct-sum subset is drawn. However, while I've been able to approach this, I've not been able to match it. My best result so far is a set of 13 integers, drawn from the 250,000 integers between 10,000 and 25,000,000, counting by hundreds (the latter is immaterial to the algorithm, but is a domain constrain of my use case):

[332600,708900,2130500,2435900,5322500,7564200,10594500,12776200,17326700,17925700,22004400,23334700,24764900]

I've hunted around, and most of the SDS generators are sequence generators that make no pretense of creating dense sets, but instead have the ability to be continued indefinitely to larger and larger numbers (e.g. the Conway-Guy Sequence). I have no such constraint, and would prefer a denser set without requiring a sequence relationship with each other.

(I did consider using the Conway-Guy Sequence n=2..18 * 10,000, but the resulting set has a broader range than I would like. I'd also really like a more general algorithm.)

Edit: For clarity, I'm looking for a way (non-deterministic or dynamic-programming methods are fine) to generate an SDS set denser than those provided by simply enumerating exponents or using a sequence like Conway-Guy. I hope, by discarding the "sequence generator" constraint, I can find numbers much closer together than such sequences provide.

Improve this question
14
  • I am confused, why wouldn't you just use powers of two?
    – RBarryYoung
    Commented Sep 22, 2014 at 15:29
  • 1
    based on what you are saying, your real desire isn't to get a better "density" as powers of two already get vanishingly close to the maximum, but rather to get that same density in a more amenable range, one where all of the numbers are within 2x of each other. Does that sound correct? Because I think that's do-able. For instance, I think I can readily get 18-19 numbers between one and two million.
    – RBarryYoung
    Commented Sep 25, 2014 at 17:09
  • 1
    FYI, I have posted what I think is a fairly complete answer to your question.
    – RBarryYoung
    Commented Sep 30, 2014 at 15:32
  • 1
    Isn't this problem called Sidon sequence?
    – Puterdo Borato
    Commented Mar 31, 2021 at 11:42
  • 1
    @sehrgut Then if I understand correctly this problem is a finite Bh[g] set. I never found a real algorithm description for computing it. There's some "greedy algorithm" description available but it is more in shape of theorems.
    – Puterdo Borato
    Commented Apr 6, 2021 at 8:25

2 Answers 2

Reset to default
1

For any value of N, it is readily possible to generate up to Floor(Log2(N))-1 numbers (which we'll call the set "S") such that:

  1. All members of S are less than or equal to N, and

  2. No two distinct subsets of S have the same sum, and

  3. All members of S are within a factor of two of each other.

Your suspicions were correct in that S would not be in any sense extensible (you could not add more members to it)

Method:

  1. For N, find T = 2^P , where T is the highest power of two that is less than or equal to N. That is:

    • P = Floor( Log2(N) ), and
    • T = 2^P

  2. Then the members of S can be generated as:

    • for( i=0 to P-2 ): S(i) = 2^i + 2^(P-1)
    • Or, to put it another way, S(i) = 2^i, for 0<= i < P-1

This makes for a total of P-1 (or Floor(Log2(N))-1) members. Can two distinct subsets of S ever sum to the same number? No:

Proof

Let's consider any two subsets of S: U and V, which are distinct (that is, they have no members in common). Then the sum of U is:

Sum(U) = O(U)*(T/2) + Sum(2^i| S(i):U)

Where

  • O(U) is the Order of the set U (how many elements it has),
  • "S(i):U" means "S(i) is an element of U", and
  • "|" is the conditioning operator (means "given that.." or "where.."),

So, putting the last two together, Sum(2^i| S(i):U) just means "the sum of all of the powers of two that are elements of U" (remembering that S(i) = 2^i)).

And likewise, the sum of V is:

Sum(V) = O(V)*(2^(P-1)) + Sum(2^i| S(i):V)

Now because U and V are distinct: Sum(2^i| S(i):U) can never be equal, because no two sums of distinct powers of two can ever be equal.

Also, because Sum(2^i; 0 <= i < P-1) = 2^(P-1)-1), these sums of the powers of two must always be less than 2^P-1. This means that the sums of U and V could only be equal if:

O(U)*(2^(P-1)) = O(V)*(2^(P-1))

or

O(U) = O(V)

That is, if U and V have the same number of elements, so that the first terms will be equal (because the second terms can never be as large as any differences in the first terms).

In such a case (O(U) = (O(V)) the first terms are equal, so Sum(U) would equal Sum(V) IFF their second terms (the binary sums) are also equal. However, we already know that they can never be equal, therefore, it can never be true that Sum(U) = Sum(V).

Improve this answer
1
  • Thank you! This code works a treat! I'm trying now to generalize it to scale over a range larger than a single power of two, though I'm not sure that's possible.
    – sehrgut
    Commented Oct 1, 2014 at 13:37
0

It seems like another way of phrasing the problem is to make sure that the previous terms never sum to the current term. If that's never the case, you'll never have two sums that add up to the same.

Ex: 2, 3, 6, 12, 24, 48, 96, ...

Summing to any single element {i} takes 1 more than the sum of the previous terms, and summing to any multi-element set {i,j} takes more than the sum of previous elements to i and previous elements to j.

More mathematically: (i-1), i, 2i, 4i, 8i, ... 2^n i Should work for any i, n.

The only way this doesn't work is if you're allowed to choose the same number twice in your subset (if that's the case, you should specify it in the problem). But that brings up the issue that Sum{i} = Sum{i} for any number, so that seems like an issue.

Improve this answer
2
  • Unfortunately, this hits the same density problem as the comment by @RBarryYoung above, for my problem domain. While it generates a sequence, the sequence is sparser than the theoretical maximum density. The Conway-Guy Sequence I referenced is, as far as I've found, the densest SDS sequence generator known. However, I'm hoping to, in discarding the necessity of sequential relationship, get a set of values significantly closer together than these sequences produce.
    – sehrgut
    Commented Sep 22, 2014 at 15:46
  • 1
    Ah, ok. I misunderstood the optimal criteria.
    – Mshnik
    Commented Sep 22, 2014 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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