Difference between revisions of "2006 AMC 12A Problems/Problem 25"

m
(See also: formatting)
Line 19: Line 19:
  
 
== See also ==
 
== See also ==
 +
* [[2006 AMC 12A Problems]]
 
* [[2006 AMC 12A Problems/Problem 24 | Previous problem]]
 
* [[2006 AMC 12A Problems/Problem 24 | Previous problem]]
* [[2006 AMC 12A Problems]]
 
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]

Revision as of 19:05, 5 November 2006

Problem

How many non- empty subsets $S$ of $\{1,2,3,\ldots ,15\}$ have the following two properties?

$(1)$ No two consecutive integers belong to $S$.

$(2)$ If $S$ contains $k$ elements, then $S$ contains no number less than $k$.

$\mathrm{(A) \ } 277\qquad \mathrm{(B) \ } 311\qquad \mathrm{(C) \ } 376\qquad \mathrm{(D) \ } 377$$\mathrm{(E) \ }  405$

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 $k$ elements from an ordered $n$ element set without choosing two consecutive members?

Note that if $n < 2k - 1$, the answer will be 0. Otherwise, the $k$ elements we choose define $k + 1$ boxes into which we can drop the $n - k$ remaining elements, with the caveat that each of the middle $k - 1$ boxes must have at least one element. This is equivalent to dropping $n - 2k + 1$ elements into $k + 1$ boxes, where each box is allowed to be empty. And this is equivalent to arranging $n - k + 1$ objects, $k$ of which are dividers, which we can do in $\displaystyle F(n, k) = {n - k + 1 \choose k}$ ways.

Now, looking at our original question, we see that the thing we want to calculate is just $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)}$

See also