Thomas King - cp's OEIS frontend

User: Thomas King

Thomas King has authored 1 sequences.

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

Thomas King, Feb 25 2022

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?

			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.

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

Cf. A006127.

Python
```
# See Thomas King link.
```

cp's OEIS Frontend

User: Thomas King

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python