Question

¿Cuántos arreglos $4 \times 4$ distintos, cuyas entradas son todas $1$ y $-1,$ tienen la propiedad de que la suma de las entradas en cada fila es $0$ y la suma de las entradas en cada columna es $0$ ?

How many different $4 \times 4$ arrays whose entries are all $1$ 's and $-1$ 's have the property that the sum of the entries in each row is $0$ and the sum of the entries in each column is $0?$

Respuesta

Solución:

Cada fila debe contener dos $1$ y dos $-1,$ así que identifica cada fila con el par de columnas que contienen sus $1;$ cada columna debe terminar elegida por exactamente dos filas. Hay $\binom{4}{2} = 6$ opciones para la fila $1.$ Clasifica según cómo la fila $2$ se superpone con la fila $1.$

Si la fila $2$ usa el mismo par ( $1$ manera), esas dos columnas quedan llenas, así que las filas $3$ y $4$ deben usar ambas el par complementario: $1$ forma de completar. Si la fila $2$ usa el par complementario ( $1$ manera), hasta ahora cada columna tiene un $1,$ así que las filas $3$ y $4$ solo necesitan ser un par complementario entre sí: $6$ opciones para la fila $3,$ la fila $4$ queda determinada, dando $6$ formas de completar. Si la fila $2$ comparte exactamente una columna con la fila $1$ ( $2 \cdot 2 = 4$ maneras), una columna queda llena, dos tienen un $1,$ y una queda vacía; las filas $3$ y $4$ deben tomar cada una la columna vacía junto con una de las dos columnas medio llenas, así que hay $2$ formas de completar.

El total es $6\,(1 \cdot 1 + 1 \cdot 6 + 4 \cdot 2) = 6 \cdot 15$ $= 90.$

Each row must contain two $1$ 's and two $-1$ 's, so identify each row with the pair of columns holding its $1$ 's; each column must end up chosen by exactly two rows. There are $\binom{4}{2} = 6$ choices for row $1.$ Classify by how row $2$ overlaps row $1.$

If row $2$ uses the same pair ( $1$ way), those two columns are full, so rows $3$ and $4$ must both use the complementary pair: $1$ completion. If row $2$ uses the complementary pair ( $1$ way), every column has one $1$ so far, so rows $3$ and $4$ need only be a complementary pair themselves: $6$ choices for row $3,$ row $4$ forced, giving $6$ completions. If row $2$ shares exactly one column with row $1$ ( $2 \cdot 2 = 4$ ways), one column is full, two have one $1,$ and one is empty; rows $3$ and $4$ must each take the empty column together with one of the two half-filled columns, so there are $2$ completions.

The total is $6\,(1 \cdot 1 + 1 \cdot 6 + 4 \cdot 2) = 6 \cdot 15$ $= 90.$

1997 AIME Problema 8

Solución:

El Problema 8 en otros años