Difference between revisions of "2006 AMC 12A Problems/Problem 25"
(→Solution 2) |
m (Small error in solution 1) |
||
| Line 18: | Line 18: | ||
<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> | ||
| − | 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 <math>k</math>, which translates to subtracting <math>k</math> from the "top" of each [[binomial coefficient]]. | + | 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 <math>k</math>, which translates to subtracting <math>k - 1</math> from the "top" of each [[binomial coefficient]]. |
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> | ||
Revision as of 17:43, 24 December 2018
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 consecutive 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
Another way of visualizing the solution above would be to use 
's and 
's. Denote as the numbers we have chosen and as other numbers. Taking an example, assuming we are picking two numbers, we imagine the shape 
. This notation forces a number between the two chosen numbers, which blocks the two numbers we picked from being consecutive. Now we consider the orientations with this shape. We have 
remaining numbers.
We need to find the number of ways to place the remaining 
's. We can find this by utilizing stars and bars, with the following marker being placed to represent groups: *| - *|*. Now, we have to place 
numbers within 
groups, which is 
. The same concept can be used for the remaining numbers. The rest of the solution continues as above.
Solution by: Everyoneintexas
Solution 3
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 (which divide the nonconsecutive numbers) into which we can drop the 
remaining elements, with the caveat that each of the middle boxes must have at least one element (since the numbers are nonconsecutive). 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 | |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
