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.

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

Offset

3,1

Comments

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).

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.

Also note that a 0-, 1- or 2-element subset cannot have (nonempty) disjoint subsets with the same sum.

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

Links

Table of n, a(n) for n=3..43.

Thomas King, Disjoint subsets with same sum, Math StackExchange, 2021.

Thomas King, Python program to compute the sequence by brute force

Example

For n=3 we only have to check the subset {1,2,3} for which 1+2 = 3, and therefore a(3) = 3.
For n=4 we first check the 3-element subsets,
  {1,2,3} : 1+2 = 3
  {1,3,4} : 1+3 = 4
  {1,2,4} : Fail.
So we check the only 4-element subset {1,2,3,4} for which 1+2 = 3, and therefore a(4) = 4.

Prog

(Python) # See Thomas King link.

Crossrefs

Cf. A006127.

Sequence in context: A332325 A194882 A096343 * A069812 A179842 A259052

Adjacent sequences: A351908 A351909 A351910 * A351912 A351913 A351914

Keyword

nonn,more

Author

Thomas King, Feb 25 2022

Status

approved