OFFSET
3,1
COMMENTS
Related to sequence A005255. We look for the largest number m(n) such that, in ANY sample of n numbers from 1 to m, there are always two subsets whose sums are equal.
A005255 gives an upper bound for the lowest number M for which the condition does not hold.
While searching for the solution, I used a "pigeonhole"-type argument to derive a lower bound for M. In a n-elements sample in {1,...,m}, there are S = 2^n - 2 nontrivial subsets (i.e. excluding the empty and the full); the maximum possible "subsum" is P = (m) + (m-1) + ... + (m-n+1) = nm - n(n-1)/2. By the pigeonhole principle, if S > P, there must be at least two subsums that are equal.
This condition S>P is rewritten m > [2^n - 2 + n(n-1)/2]/n , yielding the above sequence.
I do not know what are the exact m(n), between the upper and lower limits.
I would not have mentioned it, were it not for its similarity with Fibonacci in the first terms.
FORMULA
For n>=3, a(n)= [ 2^n - 2 + n(n-1)/2 ] / n rounded up.
EXAMPLE
Example for n=6 : in a 6-elements sample, there are S = 2^6 - 2 = 62 nontrivial subsets; the maximum possible "subsum" is P = (m) + (m-1) + ... + (m-5) = 6m - 6*5/2 = 6m - 15. With m = a(6) = 13, P = 63 : this is the lowest value of m for which the argument S>P is not working.
MATHEMATICA
f[n_] := Ceiling[(2^n + n (n - 1)/2 - 2)/n]; Array[f, 30, 3] (* Robert G. Wilson v, Sep 07 2010 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Marc Leotard (m.leotard(AT)ephec.be), Sep 06 2010
EXTENSIONS
More terms from Robert G. Wilson v, Sep 07 2010
STATUS
approved