Difference between revisions of "2006 AMC 12A Problems/Problem 25"
m |
|||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | How many non-[[empty]] [[subset]]s <math>S</math> of <math>\{1,2,3,\ldots ,15\}</math> have the following two properties? | + | How many non-[[empty set | 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 [[integer]]s belong to <math>S</math>. | <math>(1)</math> No two consecutive [[integer]]s belong to <math>S</math>. |
Revision as of 13:40, 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