grenico wrote:
I approached this in a different way, please correct me if I thought about this the wrong way
GreenlightTestPrepEssentially, it doesn't matter what the elements are. They can be symbols representing animals for example. The important thing is that they are
different. To keep it simple then, let's imagine the set of 35 different elements are the letters a-z (26 letters) and 9 capital letters (A-I), making a set of 35 different elements.
Since there are 35 elements, let's create subsets with an odd number of elements in them. How many are there?
1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35.
There are 18 different subsets we can make, each one containing an odd number of elements (one subset as one element, another has three elements, another has 5 elements, etc..)
So now lets take these 35 different elements:
a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I
And we're going to put them into each odd-numbered subset.
How many ways can you put these 35 different elements into a subset that can hold only 1 element? \(35C1\)
How many ways can you put these 35 different elements into a subset that can hold only 3 elements? \(35C3\)
How many ways can you put these 35 different elements into a subset that can hold only 5 elements? \(35C5\)
How many ways can you put these 35 different elements into a subset that can hold only 7 elements? \(35C7\)
.
.
.
How many ways can you put these 35 different elements into a subset that can hold only 33 elements? \(35C33\)
How many ways can you put these 35 different elements into a subset that can hold only 35 elements? \(35C35\)
So the total amount of odd-numbered sets can be written out in the following way:
\(35C1\) + \(35C3\) + \(35C5\) + \(35C7\) + .... + \(35C33\) + \(35C35\)
This number is enormous and isn't worth going through the trouble to calculate fully. But we can calculate \(2^{18}\) pretty simply with a calculator.
Note that \(2^{10}\) = \(1,024\) and \(2^8\) = \(2^{10}\) / \(2^2\) = \(1,024\) / \(4\) = \(256\).
So \(2^{18}\) = \(1,024 * 256\) = \(262,144\)
Now let's just try evaluating the first couple of combination formulas from above and see what happens (again, using a calculator):
\(35C1\) = \(35\)
\(35C3\) = \( 6,545 \)
\(35C5\) = \(324,632\)
At this point, we can stop here. The sum of the first three numbers is already bigger than \(2^{18}\). It must be then that the whole sum is greater than \(2^{18}\).
Therefore the answer is A. GreenlightTestPrep , I agree with
grenico , the prompt seems to be asking about the number of different odd-sized subsets (i.e. number of unique 1-element subsets + number of unique 3-element subsets + number of unique 5-element subsets + ... + number of unique 35-element subsets), not the number of unique subsets containing only "odd-indexed" elements:
novice07 wrote:
Set A contains 35 different elements.
Quantity A |
Quantity B |
The number of subsets of A containing odd number of elements |
\(2^{18}\) |
A)The quantity in Column A is greater.
B)The quantity in Column B is greater.
C)The two quantities are equal.
D)The relationship cannot be determined from the information given.
Kudos for the right answer.
------
(I don't have an extensive enough post history to directly link the URLs here)
-> Binomial Coefficient:
The binomial coefficient C(n, k) is the number of ways of picking k unordered outcomes from n possibilities, also known as a combination or combinatorial number.
...
C(n, k) therefore gives the number of k-subsets possible out of a set of n distinct items. For example, The 2-subsets of {1,2,3,4} are the six pairs {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, and {3,4}, so C (4, 2) = 6.
(Weisstein, Eric W. "Binomial Coefficient." From MathWorld--A Wolfram Web Resource.
search "wolfram Binomial Coefficient")
-> k-Subset:
A k-subset is a subset of a set on n elements containing exactly k elements. The number of k-subsets on n elements is therefore given by the binomial coefficient C(n, k). For example, there are C (3, 2) = 3 2-subsets of {1,2,3}, namely {1,2}, {1,3}, and {2,3}.
(Weisstein, Eric W. "k-Subset." From MathWorld--A Wolfram Web Resource.
search "wolfram k-Subset")
The total number of distinct k-subsets on a set of n elements (i.e., the number of subsets) is given by
sum_(k=0)^n C(n, k)=2^n.
---
-> Count of Subsets with Even Cardinality:
Theorem
Let S
be a set whose cardinality is n
Then the number of subsets of S
whose cardinality is even is 2^(n−1)
search "proofwiki Count of Subsets with Even Cardinality"-> Count of Subsets with Odd Cardinality:
Theorem
Let S
be a set whose cardinality is n
Then the number of subsets of S
whose cardinality is odd is 2^(n−1)
search "proofwiki Count of Subsets with Odd Cardinality"-> Symmetry Rule for Binomial Coefficients:
Theorem
Let n∈Z>0,k∈Z
Then:
C(n, k) = C(n, n−k)
search "proofwiki Symmetry Rule for Binomial Coefficients"----
So for this prompt...
B: 2^18
A:
For every k∈Z∈[0, 35], there are a total of sum(C(35,k))= sum(C(35, k_odd)) + sum(C(35,k_even)) = 2^35 different unique size-k subsets of a set composed of 35 different elements.
C(35,0) + C(35,1) + C(35,2) + C(35,3) + C(35,4) + C(35,5) + C(35, 6) + C(35,7) + C(35,8) + C(35,9) + C(35,10) + C(35,11) + C(35,12) + C(35,13) + C(35,14) + C(35,15) + C(35, 16) + C(35,17) + C(35,18) + C(35,19) + C(35,20)+ + C(35,21) +C(35,22) + C(35,23) + C(35,24) + C(35,25) + C(35, 26) + C(35,27) + C(35,28) + C(35,29) + C(35,30) + C(35,31) + C(35,32) + C(35,33) + C(35,34) + C(35,35) = 2^35
With n = 35 , there should be 2^(n-1) = 2^34 k_odd-sized subsets, and 2^(n-1) = 2^34 k_even-sized subsets...
The symmetry rule for binomial coefficients shows that:
C(35,0) = C(35,35)
C(35,1) = C(35,34)
C(35,2) = C(35,33)
C(35,3) = C(35,32)
C(35,4) = C(35,31)
C(35,5) = C(35,30)
C(35,6) = C(35,29)
C(35,7) = C(35,28)
C(35,8) = C(35,27)
C(35,9) = C(35,26)
C(35,10) = C(35,25)
C(35,11) = C(35,24)
C(35,12) = C(35,23)
C(35,13) = C(35,22)
C(35,14) = C(35,21)
C(35,15) = C(35,20)
C(35,16) = C(35,19)
C(35,17) = C(35,18)
There are 18 terms in each column, and each row has an odd-even pair...for each quantity of unique k_odd-sized subsets, there is matching quantity of unique k_even-sized subsets.
So the number of unique odd-sized subsets = number of even-sized subsets for a set with n = 35 different elements:
= (2^35)/2
= 2^(35-1)
= 2^34
--------------------------
A = 2^34
B = 2^18
A > B
so the answer is A