Count subsets of finite positive integers constrained by sum

For discussing Olympiad Level Combinatorics problems
User avatar
Mohaimin
Posts:38
Joined:Thu Dec 09, 2010 7:38 pm
Location:Dhaka
Contact:
Count subsets of finite positive integers constrained by sum

Unread post by Mohaimin » Tue Jun 07, 2011 4:38 pm

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 ;)

sourav das
Posts:461
Joined:Wed Dec 15, 2010 10:05 am
Location:Dhaka
Contact:

Re: Count subsets of finite positive integers constrained by

Unread post by sourav das » Sun Jul 31, 2011 3:54 pm

$\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.
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$" )

User avatar
Mohaimin
Posts:38
Joined:Thu Dec 09, 2010 7:38 pm
Location:Dhaka
Contact:

Re: Count subsets of finite positive integers constrained by

Unread post by Mohaimin » Tue Aug 02, 2011 8:50 am

sourav das wrote: So by symmetry there are $2^{17} / 2 = 2^{16}$ subsets like this.
Everything is ok except this, I understand that it was a typing mistake :)

sourav das
Posts:461
Joined:Wed Dec 15, 2010 10:05 am
Location:Dhaka
Contact:

Re: Count subsets of finite positive integers constrained by

Unread post by sourav das » Tue Aug 02, 2011 12:28 pm

Upps. Sorry. :)
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

Post Reply