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 hay tantas canicas cuyo vecino de la derecha es de su mismo color como canicas cuyo vecino de 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 de $N$ al dividirlo 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

Respuesta: 3

Conceptos:arreglos con restricciones particiones y composiciones estrellas y barras

Nivel de dificultad: 2710

Pista pequeña:

Si la fila consta de $k$ bloques máximos de un solo color, el número de pares de vecinos de distinto color es $k - 1$ .

If the row consists of $k$ maximal single-color runs, the number of different-color neighbor pairs is $k - 1$

Pista grande:

Cinco canicas verdes permiten a lo sumo $11$ bloques, así que puede haber a lo sumo $10$ cambios de color. La igualdad entre los dos tipos de pares obliga entonces a usar $16$ canicas rojas; cuenta las composiciones de $16$ en $6$ partes positivas.

Five greens allow at most $11$ runs, so at most $10$ color changes. Matching same and different pairs then forces $16$ reds; count compositions of $16$ into $6$ positive parts.

Solución:

Divide la fila en bloques máximos de un solo color. Si hay $k$ bloques, hay exactamente $k - 1$ pares de vecinos de distinto color. Como los bloques alternan colores y las cinco canicas verdes forman a lo sumo $5$ bloques, hay a lo sumo $6$ bloques rojos; por lo tanto, hay a lo sumo $11$ bloques y $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$ canicas rojas y $21$ canicas en total, el número de pares de distinto color debe ser exactamente $10,$ así que hay exactamente $11$ bloques: los colores deben alternar como rojo, verde, rojo, $\cdots$ , rojo, con $6$ bloques rojos y $5$ canicas verdes individuales entre ellos. 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

Respuesta: 3

Nivel de dificultad: 2710

Pista pequeña:

Pista grande:

Solución:

El Problema 7 en otros años