Question

Hay dos astas de bandera distinguibles, y hay $19$ banderas, de las cuales $10$ son banderas azules idénticas, y $9$ son banderas verdes idénticas. Sea $N$ el número de arreglos distinguibles que usan todas las banderas en los que cada asta tiene al menos una bandera y no hay dos banderas verdes adyacentes en ninguna de las astas. Halla el residuo cuando $N$ se divide entre $1000.$

There are two distinguishable flagpoles, and there are $19$ flags, of which $10$ are identical blue flags, and $9$ are identical green flags. Let $N$ be the number of distinguishable arrangements using all of the flags in which each flagpole has at least one flag and no two green flags on either pole are adjacent. Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

Supongamos que la primera asta recibe $b$ banderas azules y $g$ verdes, la segunda las restantes $10 - b$ azules y $9 - g$ verdes. En un asta con $b$ banderas azules, las banderas verdes deben ocupar espacios distintos entre los $b + 1$ espacios alrededor de las azules, de $\binom{b+1}{g}$ maneras. Ignorando temporalmente el requisito de que cada asta sea no vacía, el total es $\begin{aligned} &\sum_{b=0}^{10} \sum_{g=0}^{9} \binom{b+1}{g} \\ &\quad {}\cdot \binom{11-b}{9-g} \\ &= \sum_{b=0}^{10} \binom{12}{9} \\ &= 11 \cdot 220 = 2420, \end{aligned}$ donde la suma interior se colapsa por la identidad de Vandermonde, ya que $(b + 1) + (11 - b) = 12.$

Los arreglos que dejan un asta vacía ponen las $19$ banderas en una sola asta, de $\binom{11}{9} = 55$ maneras para cada elección de asta. Por lo tanto $N = 2420 - 2 \cdot 55 = 2310,$ y el residuo cuando $N$ se divide entre $1000$ es $310.$

Suppose the first pole gets $b$ blue and $g$ green flags, the second the remaining $10 - b$ blue and $9 - g$ green. On a pole with $b$ blue flags, the green flags must occupy distinct gaps among the $b + 1$ gaps around the blues, in $\binom{b+1}{g}$ ways. Temporarily ignoring the requirement that each pole be nonempty, the total is $\begin{aligned} &\sum_{b=0}^{10} \sum_{g=0}^{9} \binom{b+1}{g} \\ &\quad {}\cdot \binom{11-b}{9-g} \\ &= \sum_{b=0}^{10} \binom{12}{9} \\ &= 11 \cdot 220 = 2420, \end{aligned}$ where the inner sum collapses by Vandermonde's identity, since $(b + 1) + (11 - b) = 12.$

The arrangements that leave a pole empty put all $19$ flags on one pole, in $\binom{11}{9} = 55$ ways for each choice of pole. Hence $N = 2420 - 2 \cdot 55 = 2310,$ and the remainder when $N$ is divided by $1000$ is $310.$

2008 AIME II Problema 12

Solución:

El Problema 12 en otros años