|
| |
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Marc Leotard (m.leotard(AT)ephec.be), Sep 06 2010
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
