Difference between revisions of "2011 AIME II Problems/Problem 7"
m (TOC) |
(→Solution) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 4: | Line 4: | ||
Ed has five identical green marbles, and a large supply of identical red marbles. He arranges the green marbles and some of the red ones in a row and finds that the number of marbles whose right hand neighbor is the same color as themselves is equal to the number of marbles whose right hand neighbor is the other color. An example of such an arrangement is GGRRRGGRG. Let <math>m</math> be the maximum number of red marbles for which such an arrangement is possible, and let <math>N</math> be the number of ways he can arrange the <math>m+5</math> marbles to satisfy the requirement. Find the remainder when <math>N</math> is divided by <math>1000</math>. | Ed has five identical green marbles, and a large supply of identical red marbles. He arranges the green marbles and some of the red ones in a row and finds that the number of marbles whose right hand neighbor is the same color as themselves is equal to the number of marbles whose right hand neighbor is the other color. An example of such an arrangement is GGRRRGGRG. Let <math>m</math> be the maximum number of red marbles for which such an arrangement is possible, and let <math>N</math> be the number of ways he can arrange the <math>m+5</math> marbles to satisfy the requirement. Find the remainder when <math>N</math> is divided by <math>1000</math>. | ||
| − | ==Solution== | + | ==Solution 1== |
We are limited by the number of marbles whose right hand neighbor is not the same color as the marble. By surrounding every green marble with red marbles - RGRGRGRGRGR. That's 10 "not the same colors" and 0 "same colors." Now, for every red marble we add, we will add one "same color" pair and keep all 10 "not the same color" pairs. It follows that we can add 10 more red marbles for a total of <math>m = 16</math>. We can place those ten marbles in any of 6 "boxes": To the left of the first green marble, to the right of the first but left of the second, etc. up until to the right of the last. This is a stars-and-bars problem, the solution of which can be found as <math>\binom{n+k}{k}</math> where n is the number of stars and k is the number of bars. There are 10 stars (The unassigned Rs, since each "box" must contain at least one, are not counted here) and 5 "bars," the green marbles. So the answer is <math>\binom{15}{5} = 3003</math>, take the remainder when divided by 1000 to get the answer: <math>\boxed{003}</math>. | We are limited by the number of marbles whose right hand neighbor is not the same color as the marble. By surrounding every green marble with red marbles - RGRGRGRGRGR. That's 10 "not the same colors" and 0 "same colors." Now, for every red marble we add, we will add one "same color" pair and keep all 10 "not the same color" pairs. It follows that we can add 10 more red marbles for a total of <math>m = 16</math>. We can place those ten marbles in any of 6 "boxes": To the left of the first green marble, to the right of the first but left of the second, etc. up until to the right of the last. This is a stars-and-bars problem, the solution of which can be found as <math>\binom{n+k}{k}</math> where n is the number of stars and k is the number of bars. There are 10 stars (The unassigned Rs, since each "box" must contain at least one, are not counted here) and 5 "bars," the green marbles. So the answer is <math>\binom{15}{5} = 3003</math>, take the remainder when divided by 1000 to get the answer: <math>\boxed{003}</math>. | ||
| Line 14: | Line 14: | ||
-jackshi2006 | -jackshi2006 | ||
| + | |||
| + | ==Solution 2== | ||
| + | Begin with the above solution's reasoning to find that the ideal sequence is RGRGRGRGRGR + 10 Rs. To count the number of arrangements where the Gs are separate, group a G and an R together (GR) which will be rearranged/counted as one. However this also introduces the case of having GRGR.... which results in too few number of marbles whose right-hand neighbor is different, so we fix an R in the beginning of our sequence which also removes it from our counting calculation. Finally we are looking at the arrangement of 5 (GR)s + 10 Rs, all indistinguishable, which is <math>\frac{15!}{5!10!}=3003\Longrightarrow\boxed{003}</math>. | ||
| + | |||
| + | ~clarkculus | ||
==See also== | ==See also== | ||
Latest revision as of 11:14, 20 July 2024
Contents
Problem
Ed has five identical green marbles, and a large supply of identical red marbles. He arranges the green marbles and some of the red ones in a row and finds that the number of marbles whose right hand neighbor is the same color as themselves is equal to the number of marbles whose right hand neighbor is the other color. An example of such an arrangement is GGRRRGGRG. Let 
be the maximum number of red marbles for which such an arrangement is possible, and let 
be the number of ways he can arrange the 
marbles to satisfy the requirement. Find the remainder when is divided by 
.
Solution 1
We are limited by the number of marbles whose right hand neighbor is not the same color as the marble. By surrounding every green marble with red marbles - RGRGRGRGRGR. That's 10 "not the same colors" and 0 "same colors." Now, for every red marble we add, we will add one "same color" pair and keep all 10 "not the same color" pairs. It follows that we can add 10 more red marbles for a total of 
. We can place those ten marbles in any of 6 "boxes": To the left of the first green marble, to the right of the first but left of the second, etc. up until to the right of the last. This is a stars-and-bars problem, the solution of which can be found as 
where n is the number of stars and k is the number of bars. There are 10 stars (The unassigned Rs, since each "box" must contain at least one, are not counted here) and 5 "bars," the green marbles. So the answer is 
, take the remainder when divided by 1000 to get the answer: 
.
Rewording:
There are three states for every marble: the one to the right is different, the one to the right is the same, and there is no marble to its right. Since there are unlimited red marbles, the second value can be created infinitely and is therefore worthless. However, the first value can only be created with a combination green marbles, thus finite, and worthy of our interest. As such, to maximize the amount of red marbles, we need to maximize the appearances of the first value. The "minimal" of this strategy is to simply separate every green marble with a red - RGRGRGRGRGR. There are ten appearances of the first value, so we must add a number of red marbles to add appearances of the second value. With quick testing we can conclude the need of nine new red marbles that can be placed in six defined places that are divided by the green marbles. This is followed by stars and bars which gives us , .
-jackshi2006
Solution 2
Begin with the above solution's reasoning to find that the ideal sequence is RGRGRGRGRGR + 10 Rs. To count the number of arrangements where the Gs are separate, group a G and an R together (GR) which will be rearranged/counted as one. However this also introduces the case of having GRGR.... which results in too few number of marbles whose right-hand neighbor is different, so we fix an R in the beginning of our sequence which also removes it from our counting calculation. Finally we are looking at the arrangement of 5 (GR)s + 10 Rs, all indistinguishable, which is 
.
~clarkculus
See also
| 2011 AIME II (Problems • Answer Key • Resources) | ||
| Preceded by Problem 6 |
Followed by Problem 8 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
