Question

En la cuadrícula $6 \times 4$ que se muestra, se van a sombrear $12$ de los $24$ cuadrados de modo que haya dos cuadrados sombreados en cada fila y tres cuadrados sombreados en cada columna. Sea $N$ el número de sombreados con esta propiedad. Halla el residuo cuando $N$ se divide entre $1000.$

In the $6 \times 4$ grid shown, $12$ of the $24$ squares are to be shaded so that there are two shaded squares in each row and three shaded squares in each column. Let $N$ be the number of shadings with this property. Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

Sombrea tres de las seis filas en la columna $1:$ $\binom{6}{3} = 20$ formas. Sea $k$ el número de filas sombreadas en ambas columnas $1$ y $2;$ la columna $2$ puede entonces elegirse de $\binom{3}{k}\binom{3}{3-k}$ formas. Tras estas dos columnas, $k$ filas están completas con dos cuadrados sombreados, $6 - 2k$ filas tienen uno, y $k$ filas no tienen ninguno.

Las filas vacías deben sombrearse en ambas columnas $3$ y $4.$ La columna $3$ toma esas $k$ filas más $3 - k$ de las $6 - 2k$ filas con un solo sombreado, de $\binom{6-2k}{3-k}$ formas, y la columna $4$ queda entonces determinada: debe cubrir las filas vacías y exactamente las filas con un solo sombreado omitidas por la columna $3.$

Sumando, $\begin{aligned} N &= 20\sum_{k=0}^{3} \binom{3}{k} \\ &\quad {}\cdot \binom{3}{3-k} \\ &\quad {}\cdot \binom{6-2k}{3-k} \\ &= 20(20 + 54 + 18 + 1) \\ &= 1860, \end{aligned}$ así que el residuo es $860.$

Shade three of the six rows in column $1:$ $\binom{6}{3} = 20$ ways. Let $k$ be the number of rows shaded in both columns $1$ and $2;$ column $2$ can then be chosen in $\binom{3}{k}\binom{3}{3-k}$ ways. After these two columns, $k$ rows are complete with two shaded squares, $6 - 2k$ rows have one, and $k$ rows have none.

The empty rows must be shaded in both columns $3$ and $4.$ Column $3$ takes those $k$ rows plus $3 - k$ of the $6 - 2k$ singly-shaded rows, in $\binom{6-2k}{3-k}$ ways, and column $4$ is then forced: it must cover the empty rows and exactly the singly-shaded rows skipped by column $3.$

Summing, $\begin{aligned} N &= 20\sum_{k=0}^{3} \binom{3}{k} \\ &\quad {}\cdot \binom{3}{3-k} \\ &\quad {}\cdot \binom{6-2k}{3-k} \\ &= 20(20 + 54 + 18 + 1) \\ &= 1860, \end{aligned}$ so the remainder is $860.$

2007 AIME I Problema 10

Solución:

El Problema 10 en otros años