AIME II

Combinatorics Difficulty 6.1 National Olympiad Prove it United States

Sixteen chairs are arranged in a row. Eight people each select a chair in which to sit so that no person sits next to two other people. Let $N$ be the number of subsets of the 16 chairs that could be selected. Find the remainder when $N$ is divided by 1000.

Solution

The problem is equivalent to counting the rearrangements of PPPPPPPPEEEEEEEE (standing for people and empty seats) where no three Ps appear together. Suppose such an arrangement contains $q$ pairs $PP$ and $8 - 2q$ Ps not adjacent to another P, where $0 \le q \le 4$ . There are 9 spaces before, after, or between the 8 Es, and $PP$ s will be placed in $q$ of those 9 spaces, while Ps will be placed in $8 - 2q$ of the remaining $9 - q$ spaces. Hence the number of arrangements for a given value of $q$ is $\binom{9}{q}\binom{9-q}{8-2q}$ , and the total number of ways to select chairs is
$\begin{aligned} \sum_{q=0}^{4} \binom{9}{q} \binom{9-q}{8-2q} &= \binom{9}{0} \binom{9}{8} + \binom{9}{1} \binom{8}{6} + \binom{9}{2} \binom{7}{4} + \binom{9}{3} \binom{6}{2} + \binom{9}{4} \binom{5}{0} \\ &= 1 \cdot 9 + 9 \cdot 28 + 36 \cdot 35 + 84 \cdot 15 + 126 \cdot 1 = 9 + 252 + 1260 + 1260 + 126 = 2907. \end{aligned}$
The requested remainder is 907.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.