Difference between revisions of "2006 AMC 12A Problems/Problem 25"
(→See also) |
|||
(15 intermediate revisions by 6 users not shown) | |||
Line 14: | Line 14: | ||
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 | + | 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 consecutive 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> | ||
− | 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> | ||
==Solution 2== | ==Solution 2== | ||
+ | Another way of visualizing the solution above would be to use <math>|</math>'s and <math>-</math>'s. Denote <math>|</math> as the numbers we have chosen and <math>-</math> as other numbers. Taking an example, assuming we are picking two numbers, we imagine the shape <math>| - |</math>. 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 <math>15 - 3 = 12</math> remaining numbers. | ||
+ | |||
+ | We need to find the number of ways to place the remaining <math>12 -</math>'s. We can find this by utilizing stars and bars, with the following marker being placed to represent groups: *| - *|*. Now, we have to place <math>12</math> numbers within <math>3</math> groups, which is <math>{14 \choose 2}</math>. 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. | 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 (which divide the nonconsecutive numbers) 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 (since the numbers are nonconsecutive). 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. | 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 (which divide the nonconsecutive numbers) 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 (since the numbers are nonconsecutive). 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> | + | 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> | ||
+ | |||
+ | ==Solution 4== | ||
+ | Let <math>s</math> be the numbers of elements in a subset. First we examine the second condition. No elements less than <math>s</math> can be put in a subset of size <math>s</math>, therefore the "lowest" element that can go into the subset is <math>s</math>, whereas the "highest" element that can go into the subset is <math>15</math>. This is a total of <math>15-s+1</math> or <math>16-s</math> possible elements. | ||
+ | |||
+ | Now we consider the first condition. No consecutive elements are allowed. This means that if an element <math>e</math> is put into the subset, both <math>e-1</math> and <math>e+1</math> are no longer possibilities. Assume that all subsets are ordered from least to greatest (we are looking for the number of combinations, so we can order these combinations however we want). Then the first element will be <math>s</math> (as a reminder, the lowest possible element in a subset is <math>s</math>), the second element will be at least <math>s+2</math>, and so on. After <math>s</math> elements are chosen, we will have skipped <math>s-1</math> elements (these are the elements that were "eliminated" as they were consecutive). Therefore, we ignore exactly <math>s-1</math> elements (if we ignore more or less elements, then <math>s</math> changes) Since we must ignore <math>s-1</math> elements, we can simply remove those beforehand. (<math>16-s)-(s-1) = 17-2s</math> possible elements | ||
+ | |||
+ | Now we look for the bounds of <math>s</math>. We are looking for non-empty subsets, so <math>s\ge1</math>. If <math>s</math> is too large, there will not be enough non-consecutive terms between <math>s</math> and <math>15</math>. Specifically, the highest element in a subset using "optimal" selection will be <math>s+2(s-1)</math> or <math>3s-2</math>. If <math>3s-1>15</math>, that means s is too large. Therefore <math>3s-2\le15</math>; solving for <math>s</math> yields <math>s\le5</math>. Now we know that <math>1 \le s \le 5</math>. | ||
+ | |||
+ | We want to know the number of ways to arrange <math>17-2s</math> "balls" into <math>s</math> identical "boxes" with at most <math>1</math> ball per box, for <math>s=1</math> to <math>s=5</math>. This is equivalent to <math>\sum_{s=1}^{5}{17-2s \choose s} = 405</math>, or <math>\boxed{\text{E}}</math>. | ||
+ | |||
+ | ==Solution 5 (Clever bash)== | ||
+ | We will split the problem into cases, and maybe one could then generalize this to arbitrary <math>n</math>. | ||
+ | |||
+ | <math>\bold{Case 1}:</math> (<math>n=15, k=1</math>). Then this is easy. We have <math>\binom{15}{1}=15</math>. | ||
+ | |||
+ | <math>\bold{Case 2}:</math> (<math>n=14, k=2</math>). Now we have something tricky. To get a good grasp on this case, let us consider the smallest element; <math>2</math>, in the first spot. We then have <math>15-1=14</math> numbers left. However, we cannot have the digit <math>3</math>. Hence we have to choose <math>2</math> numbers from <math>14-1=13</math> integers left. This can be done in <math>\binom{13}{2}=78</math> ways. | ||
+ | |||
+ | <math>\bold{Case 3}:</math> (<math>n=13, k=3</math>). As in the last case, we can use the smallest element to get a good grasp on this case. Put the digit <math>3</math> in the first spot. Then there are <math>11</math> integers left for the second spot. But in total, we have to avoid <math>2</math> elements for each subset of cardinality <math>3</math> <math>{a,b,c}</math>. So we have to choose <math>3</math> elements from <math>13-2=11</math> elements, which can be done in <math>\binom{11}{3}=165</math> ways. | ||
+ | |||
+ | <math>\bold{Case 4}:</math> (<math>n=12, k=4</math>). As in the previous case, we have to avoid <math>3</math> numbers, and choose <math>4</math> from them. Which is choosing <math>4</math> elements from <math>12-3=9</math> elements, which can be done in <math>\binom{9}{4}=126</math> ways. | ||
+ | |||
+ | <math>\bold{Case 5}:</math> (<math>n=11, k=4</math>). Now you are accustomed to the strategy. We remove <math>4</math> integers leaving <math>\binom{7}{5}=21</math> ways. | ||
+ | |||
+ | Adding up all of the cases yields <math>405</math>, as in <math>\boxed{E)405}</math>. | ||
+ | |||
+ | Note also that we only went up to cardinality or <math>k=5</math>, or else for greater <math>k</math>, we would always have consecutive numbers. | ||
+ | |||
+ | EDIT: I have coincidentally found a video solution using the exact same method: https://www.youtube.com/watch?v=mqE9P2JEs-k | ||
+ | (Also if you think I am copying, why would I have then posted the video, hm? Explain that)! | ||
+ | |||
+ | == Video Solutions == | ||
+ | https://www.youtube.com/watch?v=KpABvGFJANU (by Challenge 25) | ||
== See also == | == See also == |
Latest revision as of 11:52, 27 September 2022
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 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
Solution 4
Let be the numbers of elements in a subset. First we examine the second condition. No elements less than
can be put in a subset of size
, therefore the "lowest" element that can go into the subset is
, whereas the "highest" element that can go into the subset is
. This is a total of
or
possible elements.
Now we consider the first condition. No consecutive elements are allowed. This means that if an element is put into the subset, both
and
are no longer possibilities. Assume that all subsets are ordered from least to greatest (we are looking for the number of combinations, so we can order these combinations however we want). Then the first element will be
(as a reminder, the lowest possible element in a subset is
), the second element will be at least
, and so on. After
elements are chosen, we will have skipped
elements (these are the elements that were "eliminated" as they were consecutive). Therefore, we ignore exactly
elements (if we ignore more or less elements, then
changes) Since we must ignore
elements, we can simply remove those beforehand. (
possible elements
Now we look for the bounds of . We are looking for non-empty subsets, so
. If
is too large, there will not be enough non-consecutive terms between
and
. Specifically, the highest element in a subset using "optimal" selection will be
or
. If
, that means s is too large. Therefore
; solving for
yields
. Now we know that
.
We want to know the number of ways to arrange "balls" into
identical "boxes" with at most
ball per box, for
to
. This is equivalent to
, or
.
Solution 5 (Clever bash)
We will split the problem into cases, and maybe one could then generalize this to arbitrary .
(
). Then this is easy. We have
.
(
). Now we have something tricky. To get a good grasp on this case, let us consider the smallest element;
, in the first spot. We then have
numbers left. However, we cannot have the digit
. Hence we have to choose
numbers from
integers left. This can be done in
ways.
(
). As in the last case, we can use the smallest element to get a good grasp on this case. Put the digit
in the first spot. Then there are
integers left for the second spot. But in total, we have to avoid
elements for each subset of cardinality
. So we have to choose
elements from
elements, which can be done in
ways.
(
). As in the previous case, we have to avoid
numbers, and choose
from them. Which is choosing
elements from
elements, which can be done in
ways.
(
). Now you are accustomed to the strategy. We remove
integers leaving
ways.
Adding up all of the cases yields , as in
.
Note also that we only went up to cardinality or , or else for greater
, we would always have consecutive numbers.
EDIT: I have coincidentally found a video solution using the exact same method: https://www.youtube.com/watch?v=mqE9P2JEs-k (Also if you think I am copying, why would I have then posted the video, hm? Explain that)!
Video Solutions
https://www.youtube.com/watch?v=KpABvGFJANU (by Challenge 25)
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.