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

%I #12 Jul 13 2015 22:57:25

%S 3,5,8,13,21,36,61,107,191,347,636,1177,2192,4104,7718,14572,27603,

%T 52439,99875,190661,364733,699063,1342190,2581123,4971040,9586994,

%U 18512804,35791409,69273681,134217744,260301065,505290287,981706828

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

%C 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.

%C A005255 gives an upper bound for the lowest number M for which the condition does not hold.

%C 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.

%C This condition S>P is rewritten m > [2^n - 2 + n(n-1)/2]/n , yielding the above sequence.

%C I do not know what are the exact m(n), between the upper and lower limits.

%C I would not have mentioned it, were it not for its similarity with Fibonacci in the first terms.

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

%e 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.

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

%K nonn

%O 3,1

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

%E More terms from _Robert G. Wilson v_, Sep 07 2010