Set T={2,7,9,18,36,72,144,288,576}. If all the subsets of T

Question

Set T={2,7,9,18,36,72,144,288,576}. If all the subsets of T containing at least two elements are formed, and V is the set of the sums of the elements of these subsets, how many distinct elements does V have?

(A) 346 (B) 382 (C) 495 (C) 502 (D) 512 (E) none of these

ps_dahiya · Answer

Total cases = 2^9 - 1 (When none selected) - 9 (When only 1 selected) = 502

Starting from 9, sum of a element is equal to all elements to its left. So possibility of two elements having same sum is none because we are not taking cases when only one element is selected. (For example when only 9 is selected and when both 2 and 7 are selected)

So answer = 502

Zooroopa · Answer

Is this true? Following have the same sum:

{2,7,9,18,72} and {36,72}!!

It is true that Max #V = 2^^9 - 9C0 - 9C1 = 502.

We need to use this feature to find the actual cardinality of V.

heman · Answer

=9c2 + 9c3 +9c4 + 9c5 + 9c6+ 9c7+ 9c8+9c9
= 502

Heman

yezz · Answer

Folks i hope you accept me joining your thread.

I share with you the determination , hope and the hard work.

Regarding this problem.... plz tell me if my logic is right.

One element sets:2,7,9,18,36,72,144,288,576

two elements sets: ( 2,7 ie sum = 9) 

three elements set : ( 2, 7 , 9 ie: sum = 18)

So the way that you follow will lead to repetition and not distinction as asked in the problem.


Thanks

laxieqv · Answer

A synthesis of all ideas above:
Only sets formed by   juxtaposed   numbers of set T and started with 2 ( more than two terms) have sum which is equal to one element of set T --> we have to eliminate such sets. The number of these sets is 7. ( {2,7} , {2,7,9}, {2,7,9,18} , {2,7,9,18,36} , { 2,7,9,18,36,72}, {2,7,9,18,36,72,144}, {2,7,9,18,36,72,144,288} )
So, from Dahiya's solution, we have to substract 7 ---> we have 495 sets which satisfy the problem's condition. 

Is it C, Kevin?

laxieqv · Answer

Consider {2,7} first : Subsets formed by {2,7} and any subset of{18,36,72,144,288,576} have the same sums with subsets formed by {9} and any subset of {18,36,72,144,288,576}. WE have {18,36,72,144,288,576} can form 2^6-1= 63 subsets --> combine these sets with either {2,7} or {9} , we have 63*2= 126 subsets in all ---> we have 126 indistinctive elements of V

consider {2,7,9} and { 18} : in the same manner, we have 62 indistinctive elements of V 

Up to here, we have: 126+ 62= 188 indistinctive elements ---> number of distinctive elements of V must be < 502- 188= 314 ---> E

kevincan · Answer

But why are we throwing out all 126? Shouldn't we discard only 63? Keep working, you're on the right track!

laxieqv · Answer

Uhm, if continuing working this way, as you said we should discard only 63, then  the number of discarded sums is 120 ..means B . But, I think V includes all the sums ( the number of sums = the number of subsets including no less than 2 elements) ...that means V includes the sums of , for example, {2,7,18} and { 9,18} ---> we should discard 63*2= 126

kevincan · Answer

Let's look at an easier example:

W={2,7,9,18,36}

Obviously, 27 should be a member of V, which corresponds to the sum 9+18 but also to 2+7+18. 54 should be a member of V, which corresponds to 36+18 but also to 36+2+7+9. Remember that the copies should not be counted twice, but they need to be counted once!

laxieqv · Answer

hik, then it's a little confusing ...also, the question is " how many distinct elements does V have?" ---> makes it sound like V contains distinct as well as indistinct elements ...in other words, if the same sums are not counted twice, the question should be " how many elements does V have?"

kevincan · Answer

How many times will 27 appear in V? Some may say once, others may say twice. I worded the question that way so that people will be forced to count how many different sums could result from adding at least two elements of S.

sangarelli · Answer

Taking 2 alone(dropping 7) with the set of numbers we have 247 sets that can be formed.2^8-9  where set is (2,9,18...576)
These are all unique sets.


Taking 7 alone(dropping 2) we have 127 sets that can be formed(2^7-1)(sets with 7 fixed as first element) sets such as(9,18,36,...576) have already been counted in the first step 



Now taking 2 and 7 together with the other numbers we have the original set (2,7,9,18,....576)
any combination with 2 and 7 invloved is the same as the combination of 9 involved.
for example:(2,7,18) same as (9,18) so the only set uncounted is (2,7).Sets with 2 alone or 7 alone have already been counted.


similarly taking (2,7,9,36,72...576) is same as (18,...576)
for ex: 2,7,9,36 is same as 18,36
therfore the only set not considered is (2,7,9)


continuing we get 2,7,9,18 as the third set which is uncounted
.
.
.
and 2,7,9,18...576 as the last set a total of 8 sets
therfore the total no. of sets is 247+127+8 = 382

HongHu · Answer

Wow, what a great question. Let me make an attempt too.

The pattern in set T seems to be this: a,b,a+b,2(a+b),4(a+b),...2^(n-3)*(a+b).

From the pattern we can see that if the first two elements are not chosen then we would be able to freely choose anything without getting the same sum. Reason: assume a>b without losing generalibilty, 2^a+2^b=2^a(1+2^(b-a)) and 1+2^(b-a) will never be a power of 2. In other words, the sum of any two terms that a factor of 2 will not equal to any term of the set.

When we include the first two terms with other elements in T, however, it is likely we will get a sum that is not distinctive. For example a+b+2(a+b)=(a+b)+2(a+b).

Knowing this, let's start to pick elements of set V.
Two elements: we are safe because set V only includes sum of two elements and up. Total outcomes C(n,2)
Three elements: When a and b are chosen with another element other than (a+b), we will get a sum that is equal to (a+b) with that particular element, which we have already counted in the two elements group. Therefore total outcome would be C(n,3)-C(n-3,1). Here n-3 is because we choose the third element from set T but we can't choose a,b,and (a+b).
Four elements: Similarly, total outcomes would be C(n,4)-C(n-4,1).
...
Therefore total outcome would be: 
C(n,2)+C(n,3)+...+C(n,n)-C(n-3,1)-C(n-4,1)...-C(1,1)

Here n=9, total outcome would be 
C(9,2)+C(9,3)+...+C(9,9)-C(6,1)-C(5,1)-...C(1,1)
=2^9-C(9,0)-C(9,1)-C(6,1)-C(5,1)-...-C(1,1)
=512-1-9-6-5-4-3-2-1
=481

HongHu · Answer

Hmmm there seems to be more. When we pick four elements, we will also get indistinctive elements by selecting a,b and two other elements other than a+b. So total outcome would be C(n,4)-C(n-4,1)-C(n-3,2).
...
Now we actually get a total outcome like this then:
C(n,2)+C(n,3)+...+C(n,n)-C(n-3,1)-C(n-4,1)-...-C(1,1)-C(n-3,2)-C(n-4,2)-...-C(2,2)-...-C(n-3,n-3)

When n=9 we have:
C(9,2)+C(9,3)+..C(9,9)-C(6,1)-C(5,1)-..C(1,1)-C(6,2)-C(5,2)-..C(2,2)-C(6,3)-C(5,3)-..-C(3,3)-C(6,4)-C(5,4)-C(4,4)-C(6,5)-C(5,5)-C(6,6)
=2^9-C(9,0)-C(9,1)-2^6+1-2^5+1-2^4+1-2^3+1-2^2+1-2^1+1
=512-1-9-2^7+1+1+6
=512-1-9-128+8=382

Phew. There must be a simpler way.


Ahh Looks like sangarelli's approach is much simpler.

laxieqv · Answer

Kevin, so three of us got 382, is it the correct answer?!!

kevincan · Answer

However, any subset of {18,36,72,144,288,576} will yield same sum with {2,7} as with {9}, so the answer is going to be much lower than what you say.

We all agree that the number of sets with at least 1 elements is 2^9-1-9=502

However, these sets do not all have unique sums!

Any set containing 2,7 but not 9 has a sister containing 9 but not 2 or 7 with the same sum. How many of these sets are there? Answer: the number of non-empty subsets of {18,36,...576} i.e. 2^6-1=63

Similarly any set containing 2,7 and 9 but not 18 has a sister containing 18 but not 2,7, or 9 with the same sum. How many of these sets are there? 2^5-1=31

Following this logic, number of distinct elements in V is 502-(63+31+15+7+3+1)=382

The answer is indeed 382- congrats to all who tried it. For my book, I think I'll make it a bit easier and clear up the confusion that Laxi noted!

laxieqv · Answer

Ok so i got on right track but could not reach the target beautifully :twisted:

..thank you for great problems!! Do u mind posting more arithmatics-oriented problems in addition to permutation or combination ones?!!

kevincan · Answer

I'll do my best. Questions occur to me when I least expect them to. I'll look at arithm. questions and hopefully will feel inspired.

Professor · Answer

wow what a combination!!!!!!!!! problem by kevin and solutions by honghu and laxi is a real test of math. great discussions among the great math gurus..

Set T={2,7,9,18,36,72,144,288,576}. If all the subsets of T

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards