Question

在图示的 $6 \times 4$ 方格中，要给 $24$ 个小方格中的 $12$ 个涂色，使每一行有两个被涂色的小方格，每一列有三个被涂色的小方格。设 $N$ 为满足这一性质的涂色方法数。求 $N$ 除以 $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.$

答案

答案：860

知识点：有限制的排列组合分类讨论

难度评级：2990

解答：

在第 $1$ ：列中选三行涂色：有 $\binom{6}{3} = 20$ 种。令 $k$ 为第 $1$ 列和第 $2$ ；列都被涂色的行数；那么第 $2$ 列可用 $\binom{3}{k}\binom{3}{3-k}$ 种方式选择。前两列涂完后，有 $k$ 行已经有两个涂色方格， $6 - 2k$ 行有一个涂色方格， $k$ 行没有涂色方格。

空行必须在第 $3$ 列和第 $4$ 。列都被涂色。第 $3$ 列取这 $k$ 个空行，再从 $6 - 2k$ 个已有一个涂色方格的行中取 $3 - k$ 个，有 $\binom{6-2k}{3-k}$ 种方式；第 $4$ 列随后被确定：它必须覆盖这些空行，并恰好覆盖第 $3$ 。列跳过的那些已有一个涂色方格的行。

求和得 $\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}$ 所以余数为 $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 第 10 题

答案：860

难度评级：2990

解答：

其他年份的第 10 题