Difference between revisions of "2006 AMC 12A Problems/Problem 25"
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | How many non-empty | + | How many non-[[empty]] [[subset]]s <math>S</math> of <math>\{1,2,3,\ldots ,15\}</math> have the following two properties? |
| − | <math>(1)</math> No two consecutive | + | <math>(1)</math> No two [[consecutive integer]]s belong to <math>S</math>. |
| − | <math>(2)</math> If <math>S</math> contains <math>k</math> | + | <math>(2)</math> If <math>S</math> contains <math>k</math> [[element]]s, then <math>S</math> contains no number less than <math>k</math>. |
<math> \mathrm{(A) \ } 277\qquad \mathrm{(B) \ } 311\qquad \mathrm{(C) \ } 376\qquad \mathrm{(D) \ } 377</math><math>\mathrm{(E) \ } 405</math> | <math> \mathrm{(A) \ } 277\qquad \mathrm{(B) \ } 311\qquad \mathrm{(C) \ } 376\qquad \mathrm{(D) \ } 377</math><math>\mathrm{(E) \ } 405</math> | ||
== Solution == | == Solution == | ||
| + | This question can be solved fairly directly by casework and pattern-finding. We give a somewhat more general attack, based on the solution to the following problem: | ||
| + | |||
| + | How many ways are there to choose <math>k</math> elements from an ordered <math>n</math> element [[set]] without choosing two consecutive members? | ||
| + | |||
| + | Note that if <math>n < 2k - 1</math>, the answer will be 0. Otherwise, the <math>k</math> elements we choose define <math>k + 1</math> boxes into which we can drop the <math>n - k</math> remaining elements, with the caveat that each of the middle <math>k - 1</math> boxes must have at least one element. This is equivalent to dropping <math>n - 2k + 1</math> elements into <math>k + 1</math> boxes, where each box is allowed to be empty. And this is equivalent to arranging <math>n - k + 1</math> objects, <math>k</math> of which are dividers, which we can do in <math>\displaystyle F(n, k) = {n - k + 1 \choose k}</math> ways. | ||
| + | |||
| + | Now, looking at our original question, we see that the thing we want to calculate is just <math>F(15, 1) + F(14, 2) + F(13, 3) + F(12, 4) + F(11, 5) = {15\choose 1} + {13\choose2} + {11\choose 3} + {9\choose 4} + {7 \choose 5} = 15 + 78 + 165 + 126 + 21 = 405 \Longrightarrow \mathrm{(E)}</math> | ||
== See also == | == See also == | ||
| + | * [[2006 AMC 12A Problems/Problem 24 | Previous problem]] | ||
* [[2006 AMC 12A Problems]] | * [[2006 AMC 12A Problems]] | ||
| + | |||
| + | [[Category:Intermediate Combinatorics Problems]] | ||
Revision as of 14:39, 14 October 2006
Problem
How many non-empty subsets 
of 
have the following two properties?
No two consecutive integers belong to .
If contains 
elements, then contains no number less than .
Solution
This question can be solved fairly directly by casework and pattern-finding. We give a somewhat more general attack, based on the solution to the following problem:
How many ways are there to choose elements from an ordered 
element set without choosing two consecutive members?
Note that if 
, the answer will be 0. Otherwise, the elements we choose define 
boxes into which we can drop the 
remaining elements, with the caveat that each of the middle 
boxes must have at least one element. This is equivalent to dropping 
elements into boxes, where each box is allowed to be empty. And this is equivalent to arranging 
objects, of which are dividers, which we can do in 
ways.
Now, looking at our original question, we see that the thing we want to calculate is just 
