<p>I've decided to start a thread of challenge questions for students that are going for an 800 in math on the SAT. To get an 800 it is important to work to increase your level of mathematical maturity. One way to do this is to attempt difficult math questions. The process is more important than getting the solution. When I post a question feel free to post your thoughts, questions, attempted solutions, and partial solutions. I will try to give questions that are difficult, but solvable with a reasonable amount of time and effort. If you need clarification on any of the definitions in the question please ask. If the problem has already been solved, but you have an alternate solution please post it. Remember the solution is not as important as the strategy that you are using to solve it. If this thread generates interesting discussion, then I will continue to contribute to it. If there is no interest I will let it die, and perhaps come up with something else.</p>
<p>Important Note: The best way to prepare for the SAT is to practice SAT problems. These are NOT SAT problems. So DO NOT let these questions cut into your regular SAT prep time. </p>
<p>So here's your first question:</p>
<p>How many subsets does the set A = {1, 2, 3, 4, 5, 6, 7, 8} have?</p>
<p>Remark: for clarification, some examples of subsets of A are {1, 5, 7}, A itself, and the empty set (which we can denote by {}).</p>
<p>Umm…256? (Just makin sure if I’m right or not first lol)</p>
<p>EDIT: Nevermind. Forgot that the numbers could be arranged in different order, in each set, resulting in a huge amount of similar sets, with different arrangements.</p>
<p>I’m sure most of us will be aware of what C stands for, and picking different subsets is just a matter of the different combinations of numbers that you can pick from the set itself. 8C0 is the empty set, 8C8 is A itself, while the numbers in between are the different combinations available.</p>
<p>Another quick way to solve this one: There are 8 elements in the set A. You can specify any subset B by specifying whether each of the 8 elements is in subset B or not in subset B. Since the empty set and the set A itself both count as subsets of A, either option, “in” or “not in” is valid independently for each element in A. This gives a total of 2^8 possibilities, which is 256.</p>
<p>^ This. Calculating nine combinations is extremely time consuming, even with a calculator. If you can do it with a ‘how many choices’ approach, it’ll be much easier. </p>
<p>There are also problems that you just can’t do with the combinations approach (at least, not without a ton of time). For example, how many ways are there to split up 5 different pieces of candy among you, your sister, and your brother?</p>
<p>Let me just restate what Fantasy said more formally:</p>
<p>If a set S has n elements, then S has 2^n subsets.</p>
<p>Can we prove this? </p>
<p>Relativity, SirWanksalot, and QuantMech have nice arguments for the case n = 8. Can you generalize each of these arguments to the case of arbitrary n?</p>
<p>Another method of proof that I like for this problem is to use Mathematical Induction. Can anyone do it this way as well?</p>
<p>Induction: Clearly this works for n = 1. Then there are just 2^1 subsets. Now assume it works for some value of n. If we add another element to the set, we double the number of subsets: now we have both the original subsets plus the original subsets with the new element added in. So since we double the number of subsets every time we add an element, as the formula predicts, it’s true.</p>
<p>Alternative way to do it (this will definitely not come up on the SAT): We know that the number of subsets is nC0 + nC1 + … + nCn. This is the same thing as (1+1)^2 = (2)^n. (expand it with binomial theorem if you don’t believe me!)</p>
<p>Supplement:
For a set {1,2,3…n}, there are nC1+nC2+…+nCn+1
Whereas, by binomial theorem, (1+x)^n=sum (r=0 to n) nCr x^r
For x=1, sum(r=0 to n) nCr x^r=sum (r=0 to n) nCr
=nC0+nC1+…+nCn
And (1+1)^n=2^n
Hence, there are 2^n subsets.</p>
<p>Let me just clarify conquerer’s proof by induction:</p>
<p>First note that we can start with a base case of n=0. In this case we have just the empty set. The empty set has just 1 = 2^0 subset, namely itself.</p>
<p>Now assume that every set with k elements has 2^k subsets, and let A be a set with k+1 elements. Let x be an arbitrary element of A. By induction, A has 2^k subsets without x, and 2^k subsets that include x. Thus A has 2(2^k) = 2^(k+1) subsets.</p>
<p>By the Principle of Mathematical Induction, if a set A has n elements, then A has 2^n subsets.</p>
<p>Define a set to be selfish if the number of elements it has is in the set. For example, A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} is selfish because it has 10 elements, and 10 is in the set. A selfish set is minimal if none of its proper subsets is also selfish. For example, the set A is not a minimal selfish set because {1} is a selfish subset. How many minimal selfish subsets does A have?</p>