Difference between revisions of "2006 AMC 12A Problems/Problem 25"
Baijiangchen (talk | contribs) (→Solution) |
Baijiangchen (talk | contribs) (→Solution) |
||
Line 9: | Line 9: | ||
<math> \mathrm{(A) \ } 277\qquad \mathrm{(B) \ } 311\qquad \mathrm{(C) \ } 376\qquad \mathrm{(D) \ } 377\qquad \mathrm{(E) \ } 405</math> | <math> \mathrm{(A) \ } 277\qquad \mathrm{(B) \ } 311\qquad \mathrm{(C) \ } 376\qquad \mathrm{(D) \ } 377\qquad \mathrm{(E) \ } 405</math> | ||
− | == Solution == | + | == Solution 1== |
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: | 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? | How many ways are there to choose <math>k</math> elements from an ordered <math>n</math> element [[set]] without choosing two consecutive members? | ||
− | + | You want to choose <math>k</math> numbers out of <math>n</math> with no consecutive numbers. For each configuration, we can subtract <math>i-1</math> from the <math>i</math>-th element in your subset. This converts your configuration into a configuration with <math>k</math> elements where the largest possible element is <math>n-k+1</math>, with no restriction on consectutive numbers. Since this process is easily reversible, we have a [[bijection]]. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Without consideration of the second condition, we have: | Without consideration of the second condition, we have: | ||
<math>{15 \choose 1} + {14 \choose 2} + {13 \choose 3} + ... + {9 \choose 7} + {8 \choose 8}</math> | <math>{15 \choose 1} + {14 \choose 2} + {13 \choose 3} + ... + {9 \choose 7} + {8 \choose 8}</math> | ||
Line 27: | Line 21: | ||
Now we have, after we cancel all the terms <math>{n \choose k}</math> where <math>n < k</math>, | Now we have, after we cancel all the terms <math>{n \choose k}</math> where <math>n < k</math>, | ||
<math>{15 \choose 1} + {13 \choose 2} + {11 \choose 3} + {9 \choose 4} + {7 \choose 5}= 15 + 78 + 165 + 126 + 21 = \boxed{405} \Longrightarrow \mathrm{(E)}</math> | <math>{15 \choose 1} + {13 \choose 2} + {11 \choose 3} + {9 \choose 4} + {7 \choose 5}= 15 + 78 + 165 + 126 + 21 = \boxed{405} \Longrightarrow \mathrm{(E)}</math> | ||
+ | |||
+ | ==Solution 2== | ||
+ | We have the same setup as in the previous solution. | ||
+ | |||
+ | 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>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 == |
Revision as of 21:10, 17 February 2012
Contents
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 1
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?
You want to choose numbers out of
with no consecutive numbers. For each configuration, we can subtract
from the
-th element in your subset. This converts your configuration into a configuration with
elements where the largest possible element is
, with no restriction on consectutive numbers. Since this process is easily reversible, we have a bijection.
Without consideration of the second condition, we have:
Now we examine the second condition. It simply states that no element in our original configuration (and hence also the modified configuration, since we don't move the smallest element) can be less than , which translates to subtracting
from the "top" of each binomial coefficient.
Now we have, after we cancel all the terms
where
,
Solution 2
We have the same setup as in the previous solution.
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
See also
2006 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 24 |
Followed by Last Question |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |