Question

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.$

答案

Solution:

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 $\sum_{b=0}^{10} \sum_{g=0}^{9} \binom{b+1}{g}\binom{11-b}{9-g} = \sum_{b=0}^{10} \binom{12}{9} = 11 \cdot 220 = 2420,$ 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 Problem 12

Solution:

Problem 12 in Other Years