login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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.
LINKS
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
Sequence in context: A071679 A020701 A024885 * A133605 A218607 A289916
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 25 06:53 EDT 2024. Contains 374586 sequences. (Running on oeis4.)