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

Author

Thomas King, Feb 25 2022

Keywords

• nonn
• more

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?

Examples

			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.
		

Links

• Thomas King, Disjoint subsets with same sum, Math StackExchange, 2021.
• Thomas King, Python program to compute the sequence by brute force

Crossrefs

Cf. A006127.

Programs

Python

# See Thomas King link.