A275537 Let S be a set of n-digit positive numbers; a(n) is the cardinality of S which guarantees there exist two disjoint subsets of S with equal sums of elements.

5, 10, 14, 18, 21, 25, 29, 32, 35, 39, 42, 46, 49, 53, 56, 60, 63, 66, 70, 73, 76, 80, 83, 87, 90, 93, 97, 100, 104, 107, 110, 114, 117, 120, 124, 127, 130, 134, 137, 140, 144, 147, 151, 154, 157, 161, 164, 167, 171, 174, 177, 181, 184, 187

Offset

1,1

Comments

For every n a cardinality of S has to be found such that the number of all possible nonempty proper subsets of S is greater than the number of all possible sums of the elements of those subsets. When it becomes so, the pigeonhole principle guarantees there are two disjoint subsets of S with the same sum of elements.

References

a(2) is mentioned in Miklós Bóna, A Walk Through Combinatorics, Second ed., World Scientific Publishing, 2006, p. 28., s.e. 25.

Links

Table of n, a(n) for n=1..54.

Mathematica

f[1]=5;
f[n_]:=f[n]=Module[{startingCardinality=f[n-1]+1},
While[
(2^startingCardinality)-2<=  Sum[(10^n)-i, {i, 1, startingCardinality-1}]-10^(n-1)+1,
startingCardinality++
];
startingCardinality
];
f/@Range[70]

Crossrefs

Sequence in context: A313467 A313468 A313469 * A313470 A313471 A313472

Adjacent sequences: A275534 A275535 A275536 * A275538 A275539 A275540

Keyword

base,nonn

Author

Ivan N. Ianakiev, Aug 01 2016

Status

approved