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:

The maximum number of red marble for which it is possible is 16, with one arrangement being RGRGRGRGRGRRRRRRRRRRR. Given that you have to find the remainder when N is divided by 1000, It means that N is greater than 1000, making counting the permutations difficult. I have no idea what the answer is.