A351911 - OEIS

%I #47 Dec 11 2022 12:41:46

%S 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 7,7,7,7,7,7,7

%N 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 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 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 Also note that a 0-, 1- or 2-element subset cannot have (nonempty) disjoint subsets with the same sum.

%C The sequence of run lengths starts 1, 3, 6, 11, ... could this be A006127?

%H 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 Thomas King, <a href="/A351911/a351911_4.py.txt">Python program to compute the sequence by brute force</a>

%e For n=3 we only have to check the subset {1,2,3} for which 1+2 = 3, and therefore a(3) = 3.

%e For n=4 we first check the 3-element subsets,

%e   {1,2,3} : 1+2 = 3

%e   {1,3,4} : 1+3 = 4

%e   {1,2,4} : Fail.

%e So we check the only 4-element subset {1,2,3,4} for which 1+2 = 3, and therefore a(4) = 4.

%o (Python) # See Thomas King link.

%Y Cf. A006127.

%K nonn,more

%O 3,1

%A _Thomas King_, Feb 25 2022