Question

定义一个 T-grid 为满足以下两个性质的 $3 \times 3$ 矩阵：第一，恰好五个条目为 $1$ ，剩下四个条目为 $0$ ；第二，在八条行、列和长对角线中（长对角线为 $\{a_{13}, a_{22}, a_{31}\}$ 和 $\{a_{11}, a_{22}, a_{33}\}$ ），至多有一条的三个条目全相等。求不同 T-grid 的个数。

Define a T-grid to be a $3 \times 3$ matrix which satisfies the following two properties: (1) exactly five of the entries are $1$ 's, and the remaining four entries are $0$ 's, and (2) among the eight rows, columns, and long diagonals (the long diagonals are $\{a_{13}, a_{22}, a_{31}\}$ and $\{a_{11}, a_{22}, a_{33}\}$ ), no more than one of the eight has all three entries equal. Find the number of distinct T-grids.

答案

答案：68

知识点：补集计数分类讨论

难度评级：3060

解答：

满足第一条性质的矩阵有 $\binom{9}{5} = 126$ 个；我们减去有两条或更多恒定线的矩阵。两条全 $0$ 线不可能（它们至少需要 $5$ 个零），一条全 $1$ 线和一条全 $0$ 线不能相交，因而必须是平行行或平行列；同样，两条全 $1$ 线不能平行（会有 $6$ 个一），所以必须相交，使用恰好 $3 + 3 - 1 = 5$ 个一。

情况一：一条全 $1$ 线和一条与它平行的全 $0$ 线。全 $1$ 的行或列有 $6$ 种选择，平行的全 $0$ 线有 $2$ 种选择，剩下的平行线用两个 $1$ 和一个 $0$ 填充，有 $3$ 种方法，共 $6 \cdot 2 \cdot 3 = 36$ 个矩阵。每条垂直线随后都同时含有 $1$ 和 $0$ ，所以不会出现第三条恒定线，也没有重复计数。

情况二：两条相交的全 $1$ 线，其余位置为 $0$ 。这对线可以是一行一列（ $3 \cdot 3 = 9$ ），一行或一列与一条对角线（ $6 \cdot 2 = 12$ ），或两条对角线（ $1$ ），共 $22$ 个矩阵；可检查其余四个 $0$ 从不会形成一条恒定线。所以答案为 $126 - 36 - 22 = 68$ 。

There are $\binom{9}{5} = 126$ matrices satisfying (1); we subtract those with two or more constant lines. Two lines of $0$ 's are impossible (they would need at least $5$ zeros), and a line of $1$ 's and a line of $0$ 's cannot cross, so they must be parallel rows or parallel columns; likewise two lines of $1$ 's cannot be parallel ( $6$ ones), so they must cross, using exactly $3 + 3 - 1 = 5$ ones.

Case 1: a line of $1$ 's and a parallel line of $0$ 's. There are $6$ choices for the all- $1$ row or column, $2$ for the parallel all- $0$ line, and $3$ ways to fill the remaining parallel line with two $1$ 's and one $0:$ $6 \cdot 2 \cdot 3 = 36$ matrices. Every perpendicular line then contains both a $1$ and a $0,$ so no third constant line appears and nothing is double-counted.

Case 2: two crossing lines of $1$ 's and $0$ 's elsewhere. The pair can be a row and a column ( $3 \cdot 3 = 9$ ), a row or column with a diagonal ( $6 \cdot 2 = 12$ ), or the two diagonals ( $1$ ), for $22$ matrices; one checks the four remaining $0$ 's never form a constant line. So $126 - 36 - 22 = 68.$

2010 AIME II 第 11 题

答案：68

难度评级：3060

解答：

其他年份的第 11 题