Question

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.

Answer

Solution:

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 Problem 11

Solution:

Problem 11 in Other Years