Question

Ed tiene cinco canicas verdes idénticas y una gran cantidad de canicas rojas idénticas. Coloca las canicas verdes y algunas de las rojas en una fila y descubre que el número de canicas cuyo vecino a la derecha es del mismo color que ellas mismas es igual al número de canicas cuyo vecino a la derecha es del otro color. Un ejemplo de tal disposición es GGRRRGGRG. Sea $m$ el número máximo de canicas rojas para el cual tal disposición es posible, y sea $N$ el número de formas en que Ed puede disponer las $m + 5$ canicas para satisfacer el requisito. Halla el residuo cuando $N$ se divide entre $1000.$

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 equals 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 in which Ed can arrange the $m + 5$ marbles to satisfy the requirement. Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

Divide la fila en rachas maximales de un solo color. Si hay $k$ rachas, hay exactamente $k - 1$ pares de vecinos de distinto color. Como las rachas alternan colores y las cinco canicas verdes forman a lo sumo $5$ rachas, hay a lo sumo $6$ rachas rojas, por lo tanto a lo sumo $11$ rachas y a lo sumo $10$ pares de distinto color. Con $n$ canicas rojas hay en total $n + 4$ pares de vecinos, y el requisito dice que la mitad de ellos son pares de distinto color, así que $n + 4 \le 20,$ es decir $n \le 16.$ Por lo tanto $m = 16.$

Con $16$ rojas y $21$ canicas, el número de pares de distinto color debe ser exactamente $10,$ así que hay exactamente $11$ rachas: los colores deben alternar como rojo, verde, rojo, $\cdots$ , rojo con $6$ rachas rojas y $5$ canicas verdes individuales entre ellas. Las disposiciones corresponden a las composiciones de $16$ en $6$ partes positivas, de las cuales hay $\binom{15}{5} = 3003.$

Por lo tanto $N = 3003,$ y el residuo al dividir entre $1000$ es $3.$

Break the row into maximal single-color runs. If there are $k$ runs, there are exactly $k - 1$ different-color neighbor pairs. Since runs alternate colors and the five green marbles form at most $5$ runs, there are at most $6$ red runs, hence at most $11$ runs and at most $10$ different-color pairs. With $n$ red marbles there are $n + 4$ neighbor pairs in all, and the requirement says half of them are different-color pairs, so $n + 4 \le 20,$ i.e. $n \le 16.$ Thus $m = 16.$

With $16$ reds and $21$ marbles, the count of different-color pairs must be exactly $10,$ so there are exactly $11$ runs: the colors must alternate as red–green–red– $\cdots$ –red with $6$ red runs and $5$ single green marbles between them. The arrangements correspond to compositions of $16$ into $6$ positive parts, of which there are $\binom{15}{5} = 3003.$

Hence $N = 3003,$ and the remainder upon division by $1000$ is $3.$

2011 AIME II Problema 7

Solución:

El Problema 7 en otros años