Summing max elements of all subsets.

S = { 1 , 2 , 3 , n } S = \{1, 2, 3, \dots n \} Let S S be a set of first n n natural numbers.
Let max ( P ) \max(P) be the maximal element of the subset P P . Find the sum of max ( P ) \max(P) for all subsets of S S except the Empty Set.
Let the sum be denoted by f ( n ) f(n) .
Submit the value of f ( 19 ) f(19)


Example f ( 2 ) = max ( { 1 } ) + max ( { 2 } ) + max ( { 1 , 2 } ) = 1 + 2 + 2 = 5 f(2) = \max(\{1\}) + \max(\{2\}) + \max(\{1,2\}) = 1+2+2 = 5


The answer is 9437185.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Jordan Cahn
Jan 7, 2019

Let S = { 1 , 2 , , N } S=\{1,2,\ldots,N\} . For any n < N n<N , the number of subsets of S S for which n n is the maximal element is 2 n 1 2^{n-1} , since each natural number less than n n is either in the subset, or it isn't. So 1 1 will occur 1 1 time in the computation of f ( N ) f(N) , 2 2 will occur 2 2 times, 3 3 will occur 4 4 times, etc. Thus f ( 19 ) = n = 1 19 n 2 n 1 = 9437185 f(19) = \sum_{n=1}^{19} n2^{n-1} = \boxed{9437185}

Kunal Gupta
Jan 7, 2019

We'll try to find a recursive relation for f ( n ) f(n) .
Note that for a natural n n added to the set S = { 1 , 2 , 3 n 1 } S = \{1,2,3 \dots n-1\} , there are exactly 2 n 1 2^{n-1} new sets created for which n n is the maximal element. So, we can say that: f ( n ) = f ( n 1 ) + n 2 n 1 f(n) = f(n-1) + n2^{n-1} This recursion can be solved using a program or we can find a closed form to it.
We can see that since f ( 1 ) = 1 f(1)=1 f ( n ) = i = 1 n i 2 i 1 f(n) = \sum_{i=1}^{n} i2^{i-1} Consider, g ( n , a ) = i = 1 n a i = a ( a n 1 ) a 1 g(n,a) = \sum_{i=1}^{n}a^i = \dfrac{a(a^n -1)}{a-1} for some real a a and a 1 a \neq 1 Differentiating w.r.t a a g ( n , a ) a = g ( n , a ) = i = 1 n i a i 1 = ( a 1 ) ( ( n + 1 ) a n 1 ) ( a n + 1 a ) ( a 1 ) 2 \frac{\partial g(n, a)}{\partial a} = g'(n, a) = \sum_{i=1}^{n}ia^{i-1} = \dfrac{(a-1)((n+1)a^n-1) - (a^{n+1} -a)}{(a-1)^2} We see that, g ( n , 2 ) = f ( n ) = ( n + 1 ) 2 n 1 2 n + 1 + 2 1 = ( n + 1 ) 2 n 2 n + 1 + 1 g'(n, 2) = f(n) = \dfrac{(n+1)2^n -1 - 2^{n+1} +2}{1} = (n+1)2^n - 2^{n+1} +1 Plugging in n = 19 n=19 f ( 19 ) = 9437185 f(19) = 9437185

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...