2008 UNC Math Contest II Problems/Problem 1

Problem

Determine the number of $3 \times 3$ square arrays whose row and column sums are equal to $2$, using $0, 1, 2$ as entries. Entries may be repeated, and not all of $0, 1, 2$ need be used as the two examples show.

\[\begin{tabular}{c c c c c c c c c} 1 & 1 & 0 & & & & 0 & 1 & 1 \\ 0 & 0 & 2 & & & & 1 & 1 & 0 \\ 1 & 1 & 0 & & & & 1 & 0 & 1 \\ \end{tabular}\]


Solution

The different ways the $3 \times 3$ square can be filled can be broken down into how many $2$s are present in the square.


Case One: There are zero $2$s

If there are no $2$s present in the square, then the only numbers there will be $0$s and $1$s. Since there must be two $1$s in each row and column, there must be exactly one $0$ in each row and column, making the number of distinct squares under this case defined by the number of distinct ways to place the three $0$s.

To start counting, we know that there is exactly one $0$ in the left column. If that $0$ is in the top row, there are two ways to place the other two $0$s. If that $0$ is in the middle row, there are also two ways to place the other two $0$s. Finally, if that $0$ is in the bottom row, there are still two ways to place the other two $0$s.

Thus, if there are no $2$s present, there are $2+2+2=6$ configurations.


Case Two: There is one $2$

Wherever the $2$ is placed, the numbers in the same row and column as the $2$ must all be $0$s to keep the sum of the numbers in that row and column at 2. This means that in the two other columns and two other rows that do not contain the $2$, one of their three total squares is occupied by a $0$, and they are not allowed to use a $2$, since the only $2$ in the square has already been placed. Thus, all the remaining squares that were not already filled with the one $2$ or the required $0$s must now be filled with $1$s to maintain the sum of 2 within every column and every row.

Thus, counting the number of configurations here is simple, as it is entirely dependent on where the $2$ is placed. Since there are 9 places that the $2$ could occupy, there are $9$ possibilities for this case.


Case Three: There are three $2$s

Using the same logic we used for the case involving just one $2$, we can see that if there are three $2$s, they must all be on separate rows and columns, and every other number in the grid must be a $0$.

We can count the number of ways to place the three $2$s in the same way we counted the number of ways to place the three $0$s in Case One, meaning there are $6$ possibilities for this case.


It should also be noted that it is impossible to have exactly two $2$s within the square, because if there were, they would have to be on separate columns and rows. This would mean that, after the required $0$s were filled in, only one square would be left unfilled, and the other two numbers in its row would both be $0$s (the same goes for the other two numbers in its column), requiring that the last square also be filled with a $2$. Thus, if there are at least two $2$s, there must also be a third $2$, meaning it is impossible to have exactly two $2$s.


Now that we've counted all the possible cases, all that's left is to add $6$ from the first case, $9$ from the second case, and $6$ from the third case to get $6 + 9 + 6 = \boxed{21}$ total $3 \times 3$ square arrays.

See Also

2008 UNCO Math Contest II (ProblemsAnswer KeyResources)
Preceded by
First Question
Followed by
Problem 2
1 2 3 4 5 6 7 8 9 10
All UNCO Math Contest Problems and Solutions