Difference between revisions of "2022 AMC 12B Problems/Problem 17"
Mathboy100 (talk | contribs) (→Alternate Solution (From outside to inside)) |
(→Solution (Linear transformation, permutation)) |
||
Line 20: | Line 20: | ||
<math>\textbf{(A) }144 \qquad \textbf{(B) }240 \qquad \textbf{(C) }336 \qquad \textbf{(D) }576 \qquad \textbf{(E) }624</math> | <math>\textbf{(A) }144 \qquad \textbf{(B) }240 \qquad \textbf{(C) }336 \qquad \textbf{(D) }576 \qquad \textbf{(E) }624</math> | ||
+ | |||
+ | ==Solution (quick and easy)== | ||
+ | |||
+ | Realize the configurations of rows and columns to obtain sums of one of each <math>1, 2, 3,</math> and <math>4</math> are independent of each other. Then the answer is simply <math>(4!)^2=\boxed\textbf{(D) 576}}. | ||
+ | |||
+ | ~bad_at_mathcounts | ||
==Solution (Linear transformation, permutation)== | ==Solution (Linear transformation, permutation)== | ||
Line 27: | Line 33: | ||
First, we observe that if a matrix is feasible, and we swap two rows or two columns to get a new matrix, then this new matrix is still feasible. | First, we observe that if a matrix is feasible, and we swap two rows or two columns to get a new matrix, then this new matrix is still feasible. | ||
− | Therefore, any feasible matrix can be obtained through a sequence of such swapping operations from a feasible matrix where for all <math>i \in \left\{ 1, 2, 3 ,4 \right\}< | + | Therefore, any feasible matrix can be obtained through a sequence of such swapping operations from a feasible matrix where for all </math>i \in \left\{ 1, 2, 3 ,4 \right\}<math>, the sum of entries in row </math>i<math> is </math>i<math> and the sum of entries in column </math>i<math> is </math>i<math>, hereafter called as a benchmark matrix. |
Second, we observe that there is a unique benchmark matrix, as shown below: | Second, we observe that there is a unique benchmark matrix, as shown below: | ||
Line 48: | Line 54: | ||
Step 1: We make a permutation of rows of the benchmark matrix. | Step 1: We make a permutation of rows of the benchmark matrix. | ||
− | The number of ways is <math>4!< | + | The number of ways is </math>4!<math>. |
Step 2: We make a permutation of columns of the matrix obtained after Step 1. | Step 2: We make a permutation of columns of the matrix obtained after Step 1. | ||
− | The number of ways is <math>4!< | + | The number of ways is </math>4!<math>. |
− | Following from the rule of product, the total number of feasible matrixes is <math>4! \cdot 4! = | + | Following from the rule of product, the total number of feasible matrixes is </math>4! \cdot 4! = |
− | \boxed{\textbf{(D) 576}} | + | \boxed{\textbf{(D) 576}}$. |
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) |
Revision as of 11:18, 22 November 2022
Contents
Problem
How many arrays whose entries are
s and
s are there such that the row sums (the sum of the
entries in each row) are 1, 2, 3, and 4, in some order, and the column sums (the sum of the entries in
each column) are also 1, 2, 3, and 4, in some order? For example, the array
satisfies the condition.
Solution (quick and easy)
Realize the configurations of rows and columns to obtain sums of one of each and
are independent of each other. Then the answer is simply $(4!)^2=\boxed\textbf{(D) 576}}.
~bad_at_mathcounts
==Solution (Linear transformation, permutation)==
In this problem, we call a matrix that satisfies all constraints given in the problem a feasible matrix.
First, we observe that if a matrix is feasible, and we swap two rows or two columns to get a new matrix, then this new matrix is still feasible.
Therefore, any feasible matrix can be obtained through a sequence of such swapping operations from a feasible matrix where for all$ (Error compiling LaTeX. Unknown error_msg)i \in \left\{ 1, 2, 3 ,4 \right\}i
i
i
i$, hereafter called as a benchmark matrix.
Second, we observe that there is a unique benchmark matrix, as shown below: <cmath> \[ \left[
\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ \end{array}
\right] \] </cmath>
With above observations, we now count the number of feasible matrixes. We construct a feasible matrix in the following steps.
Step 1: We make a permutation of rows of the benchmark matrix.
The number of ways is$ (Error compiling LaTeX. Unknown error_msg)4!$.
Step 2: We make a permutation of columns of the matrix obtained after Step 1.
The number of ways is$ (Error compiling LaTeX. Unknown error_msg)4!$.
Following from the rule of product, the total number of feasible matrixes is$ (Error compiling LaTeX. Unknown error_msg)4! \cdot 4! = \boxed{\textbf{(D) 576}}$.
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Alternate Solution (From outside to inside)
Since exactly row sum is
and exactly
column sum is
, there is a unique entry in the array such that it, and every other entry in the same row or column, is a
Since there are
total entries in the array, there are
ways to choose the entry with only
s in its row and column.
WLOG, let that entry be in the top-left corner of the square. Note that there is already entry numbered
in each unfilled row, and
entry numbered
in each unfilled column. Since exactly
row sum is
and exactly
column sum is
, there is a unique entry in the
array of the empty squares such that it, and every other entry in the same row or column in the
array is a
Using a process similar to what we used in the first paragraph, we can see that there are
ways to choose the entry with only
in its row and column (in the
array).
WLOG, let that entry be in the bottom right corner of the square. Then, the remaining empty squares are the center squares. Of these, one of the columns of the empty
array will have
s and the other column will have
That happens if and only if exactly
of the remaining squares is filled with a
, and there are
ways to choose that square. Filling that square with a
and the other
squares with
s completes the grid.
All in all, there are ways to complete the grid.
pianoboy. ~mathboy100 (minor LaTeX fix)
Video Solution
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
See Also
2022 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 16 |
Followed by Problem 18 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.