Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2011 AIME II Problems/Problem 7"

(→‎Solution)
(→‎Solution)
 
(7 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 +
__TOC__
 +
 
==Problem==
 
==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 <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 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>.
 +
 +
 +
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 <math>\binom{15}{5} = 3003</math>, <math>\boxed{003}</math>.
 +
 +
 +
-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>.
  
−
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 tot he number of marbles whose right hand neighbor is the other color. An example of such an arrangement is GGRRRGGRG. Let ''m'' be the maximum number of red marbles for which such an arrangement is possible, and let N be the number of ways he can arrange the ''m''+5 marbles to satisfy the requirement. Find the remainder when N is divided by 1000.
+
~clarkculus
  
−
==Solution==
+
==See also==
 +
{{AIME box|year=2011|n=II|num-b=6|num-a=8}}
  
−
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 16 = ''m''.  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>\framebox[1.3\width]{003.}</math>
+
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 11:14, 20 July 2024

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 $m$ be the maximum number of red marbles for which such an arrangement is possible, and let $N$ be the number of ways he can arrange the $m+5$ marbles to satisfy the requirement. Find the remainder when $N$ is divided by $1000$.

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 $m = 16$. 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 $\binom{n+k}{k}$ 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 $\binom{15}{5} = 3003$, take the remainder when divided by 1000 to get the answer: $\boxed{003}$.


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 $\binom{15}{5} = 3003$, $\boxed{003}$.


-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 $\frac{15!}{5!10!}=3003\Longrightarrow\boxed{003}$.

~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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_AIME_II_Problems/Problem_7&oldid=223204"