login
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.
0
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.
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
KEYWORD
base,nonn
AUTHOR
Ivan N. Ianakiev, Aug 01 2016
STATUS
approved