

A180459


Sampling n numbers between 1 and a(n)1, you are guaranteed to always find two subsets whose sums are equal.


0



3, 5, 8, 13, 21, 36, 61, 107, 191, 347, 636, 1177, 2192, 4104, 7718, 14572, 27603, 52439, 99875, 190661, 364733, 699063, 1342190, 2581123, 4971040, 9586994, 18512804, 35791409, 69273681, 134217744, 260301065, 505290287, 981706828
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 nelements 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) + (m1) + ... + (mn+1) = nm  n(n1)/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(n1)/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.


LINKS



FORMULA

For n>=3, a(n)= [ 2^n  2 + n(n1)/2 ] / n rounded up.


EXAMPLE

Example for n=6 : in a 6elements sample, there are S = 2^6  2 = 62 nontrivial subsets; the maximum possible "subsum" is P = (m) + (m1) + ... + (m5) = 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



STATUS

approved



