Question

Define una T-grid como una matriz $3 \times 3$ que satisface las siguientes dos propiedades: (1) exactamente cinco de las entradas son $1$ 's, y las cuatro entradas restantes son $0$ 's, y (2) entre las ocho filas, columnas y diagonales largas (las diagonales largas son $\{a_{13}, a_{22}, a_{31}\}$ y $\{a_{11}, a_{22}, a_{33}\}$ ), no más de una de las ocho tiene sus tres entradas iguales. Halla el número de T-grids distintas.

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.

Respuesta

Solución:

Hay $\binom{9}{5} = 126$ matrices que satisfacen (1); restamos aquellas con dos o más líneas constantes. Dos líneas de $0$ 's son imposibles (necesitarían al menos $5$ ceros), y una línea de $1$ 's y una línea de $0$ 's no pueden cruzarse, así que deben ser filas paralelas o columnas paralelas; de igual modo dos líneas de $1$ 's no pueden ser paralelas ( $6$ unos), así que deben cruzarse, usando exactamente $3 + 3 - 1 = 5$ unos.

Caso 1: una línea de $1$ 's y una línea paralela de $0$ 's. Hay $6$ elecciones para la fila o columna toda de $1$ , $2$ para la línea paralela toda de $0$ , y $3$ maneras de llenar la línea paralela restante con dos $1$ 's y un $0:$ $6 \cdot 2 \cdot 3 = 36$ matrices. Cada línea perpendicular contiene entonces tanto un $1$ como un $0,$ así que no aparece una tercera línea constante y nada se cuenta dos veces.

Caso 2: dos líneas cruzadas de $1$ 's y $0$ 's en el resto. El par puede ser una fila y una columna ( $3 \cdot 3 = 9$ ), una fila o columna con una diagonal ( $6 \cdot 2 = 12$ ), o las dos diagonales ( $1$ ), dando $22$ matrices; se comprueba que los cuatro $0$ 's restantes nunca forman una línea constante. Así que $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 Problema 11

Solución:

El Problema 11 en otros años