cp's OEIS Frontend

A351911 a(n) is the least integer m such that every m-element subset of {1,2,3,...,n} contains two nonempty and disjoint subsets whose sums are equal.

%I A351911 #47 Dec 11 2022 12:41:46
%S A351911 3,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,
%T A351911 7,7,7,7,7,7,7
%N A351911 a(n) is the least integer m such that every m-element subset of {1,2,3,...,n} contains two nonempty and disjoint subsets whose sums are equal.
%C A351911 a(n) grows like log n. Proof: The set of powers of 2 in {1,2,3,...,n} cannot contain two (nonempty) disjoint subsets with the same sum due to binary representation being unique, hence 1+log_2(n) < a(n). Let N be the least integer such that Sum_{i=0..N-1} (n-i) < 2^N-1. Then by the pigeonhole principle, we have a(n) <= N because the range of possible sums (for nonempty subsets of an N-element set) is at most Sum_{i=0..N-1} (n-i) and there are 2^N-1 nonempty subsets in total. Also N is O(log n).
%C A351911 Note that if we have two (distinct) subsets whose sums agree, then we can remove the integers in the intersection from both sets to get two disjoint (and nonempty) subsets with the same sum.
%C A351911 Also note that a 0-, 1- or 2-element subset cannot have (nonempty) disjoint subsets with the same sum.
%C A351911 The sequence of run lengths starts 1, 3, 6, 11, ... could this be A006127?
%H A351911 Thomas King, <a href="https://math.stackexchange.com/questions/4099089/disjoint-subsets-with-same-sum">Disjoint subsets with same sum</a>, Math StackExchange, 2021.
%H A351911 Thomas King, <a href="/A351911/a351911_4.py.txt">Python program to compute the sequence by brute force</a>
%e A351911 For n=3 we only have to check the subset {1,2,3} for which 1+2 = 3, and therefore a(3) = 3.
%e A351911 For n=4 we first check the 3-element subsets,
%e A351911   {1,2,3} : 1+2 = 3
%e A351911   {1,3,4} : 1+3 = 4
%e A351911   {1,2,4} : Fail.
%e A351911 So we check the only 4-element subset {1,2,3,4} for which 1+2 = 3, and therefore a(4) = 4.
%o A351911 (Python) # See Thomas King link.
%Y A351911 Cf. A006127.
%K A351911 nonn,more
%O A351911 3,1
%A A351911 _Thomas King_, Feb 25 2022