Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Unique sums over combinations

  1. Aug 30, 2011 #1
    Hi everybody,

    Here is something I've been trying to figure out but to no avail.

    General problem description:
    From {1,...,R} take a set S of N integers such that the sums over members of each of the Binomial[N,k] combinations of elements in S are all different from each other (that is, the sums are different).

    Specifically, I want to find solutions for each of the following cases, separately:
    1. R = 1023, N = 26, k = 2
    2. R = 1023, N = 39, k = 2
    3. R = 699050, N = 52, k = 3
    4. R = 524287, N = 39, k = 4
    5. R = 419430, N = 39, k = 5

    Brute force is out of the question as the search space is sized Binomial[R,N].
    Using simulated annealing I've solved case 1 but attempts at the others have so far failed. I'd appreciate it if someone could point me towards some clever maths or better stochastic methods for finding solutions to this problem, or proof that solutions do not exist.

    I hope I have been clear in my description but if you have any questions, fire away.

    Many thanks to each and all.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted