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 marbles in a row and finds that the number of marbles whose right hand neighbor is the same color as themselves equals the number of marbles whose right hand neighbor is the other color. An example of such an arrangement is . Let be the maximum number of red marbles for which Ed can make such an arrangement, and let be the number of ways in which Ed can arrange the marbles to satisfy the requirement. Find the remainder when is divided by .
Solution:
To maximize the number of red marbles used, it is necessary to maximize the number of color changes in the row. This is accomplished if a red marble is placed between every two green marbles and red marbles are placed at the beginning and end of the row. This produces a total of changes. To make the number of marbles with the same colored neighbor equal to , another red marbles must be placed next to current red marbles, for a total of red marbles. The first six red marbles can be placed in only one way, but the remaining red marbles can be placed to any of the six regions bounded by the five green marbles. This is equivalent to filling out of places with green marbles and the remaining places with red marbles, which can be done in = ways, and the required remainder is .
The problems on this page are the property of the MAA's American Mathematics Competitions