Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2008 UNC Math Contest II Problems/Problem 1"

(Created page with "== Problem == Determine the number of <math>3 \times 3</math> square arrays whose row and column sums are equal to <math>2</math>, using <math>0, 1, 2</math> as entries. Entries...")
 
(→‎Solution)
 
Line 15: Line 15:
  
 
== Solution ==
 
== Solution ==
 +
The different ways the <math>3 \times 3</math> square can be filled can be broken down into how many <math>2</math>s are present in the square.
  
 +
 +
 +
Case One: There are zero <math>2</math>s
 +
 +
If there are no <math>2</math>s present in the square, then the only numbers there will be <math>0</math>s and <math>1</math>s. Since there must be two <math>1</math>s in each row and column, there must be exactly one <math>0</math> 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 <math>0</math>s.
 +
 +
To start counting, we know that there is exactly one <math>0</math> in the left column. If that <math>0</math> is in the top row, there are two ways to place the other two <math>0</math>s. If that <math>0</math> is in the middle row, there are also two ways to place the other two <math>0</math>s. Finally, if that <math>0</math> is in the bottom row, there are still two ways to place the other two <math>0</math>s.
 +
 +
Thus, if there are no <math>2</math>s present, there are <math>2+2+2=6</math> configurations.
 +
 +
 +
 +
Case Two: There is one <math>2</math>
 +
 +
Wherever the <math>2</math> is placed, the numbers in the same row and column as the <math>2</math> must all be <math>0</math>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 <math>2</math>, one of their three total squares is occupied by a <math>0</math>, and they are not allowed to use a <math>2</math>, since the only <math>2</math> in the square has already been placed. Thus, all the remaining squares that were not already filled with the one <math>2</math> or the required <math>0</math>s must now be filled with <math>1</math>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 <math>2</math> is placed. Since there are 9 places that the <math>2</math> could occupy, there are <math>9</math> possibilities for this case.
 +
 +
 +
 +
Case Three: There are three <math>2</math>s
 +
 +
Using the same logic we used for the case involving just one <math>2</math>, we can see that if there are three <math>2</math>s, they must all be on separate rows and columns, and every other number in the grid must be a <math>0</math>.
 +
 +
We can count the number of ways to place the three <math>2</math>s in the same way we counted the number of ways to place the three <math>0</math>s in Case One, meaning there are <math>6</math> possibilities for this case.
 +
 +
 +
 +
It should also be noted that it is impossible to have exactly two <math>2</math>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 <math>0</math>s were filled in, only one square would be left unfilled, and the other two numbers in its row would both be <math>0</math>s (the same goes for the other two numbers in its column), requiring that the last square also be filled with a <math>2</math>. Thus, if there are at least two <math>2</math>s, there must also be a third <math>2</math>, meaning it is impossible to have exactly two <math>2</math>s.
 +
 +
 +
 +
Now that we've counted all the possible cases, all that's left is to add <math>6</math> from the first case, <math>9</math> from the second case, and <math>6</math> from the third case to get <math>6 + 9 + 6 = \boxed{21}</math> total <math>3 \times 3</math> square arrays.
  
 
== See Also ==
 
== See Also ==

Latest revision as of 11:53, 23 December 2019

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 (Problems • Answer Key • Resources)
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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_UNC_Math_Contest_II_Problems/Problem_1&oldid=113238"