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

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

Offset: 3

Author

Marc Leotard (m.leotard(AT)ephec.be), Sep 06 2010

Keywords

• nonn

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.

Examples

			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.
		

Programs

Mathematica

f[n_] := Ceiling[(2^n + n (n - 1)/2 - 2)/n]; Array[f, 30, 3] (* Robert G. Wilson v, Sep 07 2010 *)

Formula

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

Extensions

More terms from Robert G. Wilson v, Sep 07 2010