login
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

%I #19 Feb 24 2019 11:03:49

%S 5,10,14,18,21,25,29,32,35,39,42,46,49,53,56,60,63,66,70,73,76,80,83,

%T 87,90,93,97,100,104,107,110,114,117,120,124,127,130,134,137,140,144,

%U 147,151,154,157,161,164,167,171,174,177,181,184,187

%N 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.

%C 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.

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

%t f[1]=5;

%t f[n_]:=f[n]=Module[{startingCardinality=f[n-1]+1},

%t While[

%t (2^startingCardinality)-2<= Sum[(10^n)-i,{i,1,startingCardinality-1}]-10^(n-1)+1,

%t startingCardinality++

%t ];

%t startingCardinality

%t ];

%t f/@Range[70]

%K base,nonn

%O 1,1

%A _Ivan N. Ianakiev_, Aug 01 2016