2011 AIME II Problems/Problem 7

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 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.

Solution

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 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 \framebox[1.3\width]{003.}$