AIME 1997 · 第 8 题

Solution 1

For more detailed explanations, see related problem (AIME I 2007, 10).

The problem is asking us for all configurations of $4\times 4$ grids with 2 1's and 2 -1's in each row and column. We do casework upon the first two columns:

• The first two columns share no two numbers in the same row. There are ${4\choose2} = 6$ ways to pick two 1's in the first column, and the second column is determined. For the third and fourth columns, no two numbers can be in the same row (to make the sum of each row 0), so again there are ${4\choose 2}$ ways. This gives $6^2 = 36$.
• The first two columns share one number in the same row. There are ${4\choose 1} = 4$ ways to pick the position of the shared 1, then ${3\choose 2} = 3$ ways to pick the locations for the next two 1s, and then $2$ ways to orient the 1s. For the third and fourth columns, the two rows with shared 1s or -1s are fixed, so the only things that can be changed is the orientation of the mixed rows, in $2$ ways. This gives $4 \cdot 3 \cdot 2 \cdot 2 = 48$.
• The first two columns share two numbers in the same row. There are ${4\choose 2} = 6$ ways to pick the position of the shared 1s. Everything is then fixed.

Adding these cases up, we get $36 + 48 + 6 = \boxed{090}$.

Solution 2

Each row and column must have 2 1's and 2 -1's. Let's consider the first column. There are a total of $6$ ways to arrange 2 1's and 2 -1's. Let's consider the setup where the first and second indices of column 1 are 1 and the third and fourth are -1. Okay, now on the first row, there are 3 ways to arrange the one 1 and 2 -1's we have left to put. Now, we take cases on the second row's remaining elements. If the second row goes like 1,-1,1,-1, then by observation, there are 2 ways to complete the grid. If it goes like 1,1, -1, -1, there is 1 way to complete the grid. If it goes like 1, -1, -1, 1, then there are 2 ways to complete the grid. So our answer is $6*3*(2+1+2)$ = $\boxed{090}$.

-pi_is_3.141

Solution 3

Notice that for every arrangement $A$ of the first rows of $-1$s and $1$s, we have the inverse of that row $A^{-1}$ so that the sum of the rows and columns of $A$ and $A^{-1}$ is $0$. Therefore if we have another arrangement $B$, we have $B^{-1}$. For instance, if $A=(-1,1,1,-1)$, $A^{-1}=(1,-1,-1,1)$. We then have that if we fix the first row $A$, we have that first there are $\binom{4}{2}$ values of the fixed $A$. We then have the following cases:

Case $1$: ($AA^{-1}BB^{-1}$). $\binom{4}{2}$.

Case $2$: ($ABA^{-1}B^{-1}$). $\binom{4}{2}$.

Case $3$: ($AAA^{-1}A^{-1}$). $\binom{4}{2}/2$, where here we divided by $2$ because then we would overcount $AA$ and $A^{-1}A^{-1}$.

Therefore the answer is $\binom{4}{2}(\binom{4}{2}+\binom{4}{2}+\binom{4}{2}/2)$=$6(6+6+3)$=$\boxed{090}$.

~th1nq3r

Solution 4 (Bijection and Casework)

How many orderings are possible for the first row? Well, that's easy! There are $4 \choose 2$ = 6 possible ways to distribute two 1's into the first row, and the remaining -1's are uniquely determined.

Now, the hard part. We know that to obtain a commutative sum of 0, each row and column must have two 1's and two -1's. So, we can consider the bottom 3x2 matrix.

There are a total of $3 \choose 2$ * $3 \choose 2$ = 9 different orderings that satisfy the conditions of the sum to 0 (that is, $3 \choose 2$ ways to distribute the -1's in the first column, and $3 \choose 2$ ways to distribute the 1's in the second column, where the last number is uniquely determined). We have a couple of cases.

Case 1: In the bottom left 3x2 matrix of the 4x4 grid, each row contains 1, -1 or -1, 1.

This is obviously not possible as each row contains a maximum of two -1's or two 1's and by simple logic or pigeonhole, there will be no such case.

Case 2: In the bottom left 3x2 matrix of the 4x4 grid, two rows contain 1, -1 and one contains -1, 1.

Sweet! Notice that when we have two rows that contain 1, -1, then the third row is uniquely determined as -1, 1. Thus, we just need to count the cases of 1,-1 and we got our answer.

There are two -1's in the first column, and two 1's in the second. Thus, our orderings (in respective row order), must look like some permutation of

$$\begin{bmatrix} -1 & 1 \\ -1 & 1 \\ 1 & -1 \end{bmatrix}$$ This is an easy permutation! Say that A = $\begin{bmatrix} -1 & 1 \end{bmatrix}$and B =$\begin{bmatrix} 1 & -1 \end{bmatrix}$. Then, we have the matrix

$$\begin{bmatrix} A \\ A \\ B \end{bmatrix}$$ in which there are $\frac{3!}{2!} = 3$ possible arrangements. Now, let's consider the bottom right 3x2 matrix of the 4x4 matrix in this case. For the first 3x1 matrix, we just need to distribute either two 1's or two -1's (doesn't matter, as it is just dependent on the top number), which can happen in $3 \choose 2$ = 3 ways, and the last number is uniquely determined. Then, the last 3x1 matrix is uniquely determined, giving us a total of 3 \cdot 3 = 9 total cases in this case.

Case 3: In the bottom left 3x2 matrix of the 4x4 grid, one row has -1, 1.

In simpler terms, a case like

$$\begin{bmatrix} -1 & 1 \\ 1 & 1 \\ -1 & -1 \end{bmatrix}$$ satisfies the constraints.

Label the cases A,B,C top down in respective order. Then, there are $3! = 6$ total configurations. In two of the rows (the rows containing B and C), they already determine the last two numbers of said rows. In the remaining row containing A, note that those numbers are also uniquely determined from the preceding rows, as they are already filled!

However, notice that this case already covers our case 4, which one row contains 1,-1! This is due to the ordering of the top row (thank them later). If you aren't convinced, we can order the top row to make a case consisting of one row containing -1,1 possible, and we can reorder the top row again to make a case consisting of one row containing 1,-1. For example, we can arrange our top row as

$$\begin{bmatrix} 1 & -1 & -1 & 1 \end{bmatrix}$$ to obtain the 3x2 matrix

$$\begin{bmatrix} -1 & 1 \\ 1 & 1 \\ -1 & -1 \end{bmatrix}$$ , but we can also order the top row as

$$\begin{bmatrix} -1 & 1 & -1 & 1 \end{bmatrix}$$ to obtain the matrix

$$\begin{bmatrix} -1 & -1 \\ 1 & 1 \\ 1 & -1 \end{bmatrix}$$ Boom! Two birds with one stone! (This is also called a 1-1 correspondence or bijection).

Thus, there are 6 total cases for this case.

We have a total of 6 possible orderings for the first row. Then, two cases emerge, in which, because each of the 6 possible orderings of the first row can affect the number of cases, we multiply the sum of each case by the total number of orderings of the first row. Thus, our answer is $6 \cdot (3 \cdot 3 + 6) = 6 \cdot (15) = \boxed{090}$.

~Pinotation