Question

Dieciséis sillas están colocadas en una fila. Ocho personas eligen cada una una silla para sentarse de modo que ninguna persona se siente junto a otras dos personas. Sea $N$ la cantidad de subconjuntos de $16$ sillas que podrían ser seleccionados. Halla el residuo cuando $N$ se divide entre $1000.$

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 $16$ chairs that could be selected. Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

Una persona se sienta junto a otras dos exactamente cuando tres sillas consecutivas están todas ocupadas, así que contamos los subconjuntos de $8$ elementos de las $16$ sillas sin tres sillas consecutivas elegidas. Las sillas ocupadas forman entonces bloques maximales de tamaño $1$ o $2.$ Si hay $m$ bloques, entonces $8 - m$ de ellos son pares y $2m - 8$ son individuales, así que $4 \le m \le 8,$ y las posiciones de los pares se pueden elegir de $\binom{m}{8-m}$ maneras. Las $8$ sillas vacías crean $9$ huecos (incluidos los extremos), y los $m$ bloques ocupan $m$ huecos distintos: $\binom{9}{m}$ maneras.

Por lo tanto $\begin{gathered} N = \sum_{m=4}^{8} \binom{m}{8-m}\binom{9}{m} \\ = 1 \cdot 126 + 10 \cdot 126 + 15 \cdot 84 \\ \quad {}+ 7 \cdot 36 + 1 \cdot 9 = 2907. \end{gathered}$

El residuo cuando $N = 2907$ se divide entre $1000$ es $907.$

A person sits next to two others exactly when three consecutive chairs are all occupied, so we count $8$ -element subsets of the $16$ chairs with no three consecutive chairs chosen. The occupied chairs then form maximal blocks of size $1$ or $2.$ If there are $m$ blocks, then $8 - m$ of them are pairs and $2m - 8$ are singles, so $4 \le m \le 8,$ and the pair positions can be chosen in $\binom{m}{8-m}$ ways. The $8$ empty chairs create $9$ gaps (including the ends), and the $m$ blocks occupy $m$ distinct gaps: $\binom{9}{m}$ ways.

Therefore $\begin{gathered} N = \sum_{m=4}^{8} \binom{m}{8-m}\binom{9}{m} \\ = 1 \cdot 126 + 10 \cdot 126 + 15 \cdot 84 \\ \quad {}+ 7 \cdot 36 + 1 \cdot 9 = 2907. \end{gathered}$

The remainder when $N = 2907$ is divided by $1000$ is $907.$

2025 AIME II Problema 10

Solución:

El Problema 10 en otros años