You are given a set S of first 18 positive integers.
How many subsets of S will have sum greater than 85?
I was watching a video lecture on Symmetry. The problem was given in the booklet provided with the lecture. Its a hint
Count subsets of finite positive integers constrained by sum
-
- Posts:461
- Joined:Wed Dec 15, 2010 10:05 am
- Location:Dhaka
- Contact:
Re: Count subsets of finite positive integers constrained by
$\sum_{i=1}^{18}i= 171$
now there are $2^{18}$ subsets of that set [as there are 2 options for every element]. [ note that we also count $\varnothing $ ]. Now denote the sum of the elements of a subset by $S$. So, For any subset $A$ with $0\leq S\leq 85$ we will get $A'$ for which $S$ is greater than 85.[As 0 to 85, there are 86 values and 86 to 171 also 86 values.]
So by symmetry there are $2^{18} / 2 = 2^{17}$ subsets like this.
now there are $2^{18}$ subsets of that set [as there are 2 options for every element]. [ note that we also count $\varnothing $ ]. Now denote the sum of the elements of a subset by $S$. So, For any subset $A$ with $0\leq S\leq 85$ we will get $A'$ for which $S$ is greater than 85.[As 0 to 85, there are 86 values and 86 to 171 also 86 values.]
So by symmetry there are $2^{18} / 2 = 2^{17}$ subsets like this.
Last edited by sourav das on Tue Aug 02, 2011 12:26 pm, edited 1 time in total.
You spin my head right round right round,
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
Re: Count subsets of finite positive integers constrained by
Everything is ok except this, I understand that it was a typing mistakesourav das wrote: So by symmetry there are $2^{17} / 2 = 2^{16}$ subsets like this.
-
- Posts:461
- Joined:Wed Dec 15, 2010 10:05 am
- Location:Dhaka
- Contact:
Re: Count subsets of finite positive integers constrained by
Upps. Sorry.
You spin my head right round right round,
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )