Given a set of distances S, choose N unique points P on a number line such that the distances between the N points occur in S as much as possible. That is, maximize the occurence in S of the distances between the N points. 


For example:


S = {2, 4}, N = 4


One answer would be P = {2, 4, 6, 8}, since the distances between the points P are 2, 2, 2, 2, 4, 4, 6. Only 6 is not in S.


or


S = {7, 13, 14, 22}
N = 4501


answer ???


I'm not looking for an exact answer (although an exact answer wouldn't hurt) but rather I am trying to avoid reinventing the wheel (fun though it may be). What mathematical tools could I use to avoid bruteforcing the possible values of P. How should how would you approach this problem?



Given N points on a number line and m total distances between those points, are there efficent ways to optimize for particular values in m?
Some comments expanding on gowers' hunch: we may as well assume that the elements of S have gcd 1. If the size of the set is |S| = m and the sum of the elements of S is k then taking a block of N consecutive integers for $N \geq m$ gives (mN - k) pairs. There's also a theoretical maximum of $mN - \binom{m + 1}{2}$: every element of any N-set can be the larger half of at most m pairs, except that the smallest element can be the larger half of at most 0, the second-smallest can be the larger half of at most 1, etc., and the m-th smallest can be the larger half of at most (m - 1).


This theoretical maximum is achieved for S = {1, 2, ..., m} and matches gowers' strategy in this case. However, usually there's some gap between gowers' strategy and the theoretical max, and in some cases we can definitely do better than gowers' strategy: for example, with S = {1, 5, 10} and N = 12, a block of 12 consecutive integers gives us 11 + 7 + 2 = 20 pairs while an arithmetic progression with step size 5 gets us 11 + 10 = 21 pairs. So for small values of N we can sometimes do better by ignoring certain elements of S.


