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 "2022 AMC 12B Problems/Problem 17"

(→‎Alternate Solution (From outside to inside))
 
(25 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
  
−
How many <math>4 \times 4</math> arrays whose entries are <math>0</math>s and <math>1</math>s are there such that the row sums (the sum of the
+
How many <math>4 \times 4</math> arrays whose entries are <math>0</math>s and <math>1</math>s are there such that the row sums (the sum of the entries in each row) are <math>1, 2, 3,</math> and <math>4,</math> in some order, and the column sums (the sum of the entries in each column) are also <math>1, 2, 3,</math> and <math>4,</math> in some order? For example, the array
−
entries in each row) are 1, 2, 3, and 4, in some order, and the column sums (the sum of the entries in
+
<cmath>\left[
−
each column) are also 1, 2, 3, and 4, in some order? For example, the array
 
−
<cmath>
 
−
\[
 
−
\left[
 
 
   \begin{array}{cccc}
 
   \begin{array}{cccc}
 
     1 & 1 & 1 & 0 \\
 
     1 & 1 & 1 & 0 \\
Line 13: Line 9:
 
     0 & 1 & 0 & 0 \\
 
     0 & 1 & 0 & 0 \\
 
   \end{array}
 
   \end{array}
−
\right]
+
\right]</cmath>
−
\]
 
−
</cmath>
 
−
 
 
 
satisfies the condition.
 
satisfies the condition.
  
 
<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 (Linear transformation, permutation)==
+
==Solution 1 (One-to-One Correspondence)==
 +
 
 +
Note that the arrays and the sum configurations have one-to-one correspondence. Furthermore, the row sum configuration and the column sum configuration are independent of each other. Therefore, the answer is <math>(4!)^2=\boxed{\textbf{(D) }576}.</math>
 +
 
 +
<u><b>Remark</b></u>
 +
 
 +
For any given sum configuration, we can uniquely reconstruct the array it represents. Conversely, for any array, it is clear that we can determine the unique sum configuration associated with it. Therefore, this establishes a one-to-one correspondence between the arrays and the sum configurations.
 +
 
 +
~bad_at_mathcounts ~MRENTHUSIASM ~tsun26
 +
 
 +
==Solution 2 (Linear Transformation and Permutation)==
  
 
In this problem, we call a matrix that satisfies all constraints given in the problem a feasible matrix.
 
In this problem, we call a matrix that satisfies all constraints given in the problem a feasible matrix.
Line 30: Line 33:
  
 
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:
−
<cmath>
+
<cmath>\left[
−
\[
 
−
\left[
 
 
   \begin{array}{cccc}
 
   \begin{array}{cccc}
 
     0 & 0 & 0 & 1 \\
 
     0 & 0 & 0 & 1 \\
Line 39: Line 40:
 
     1 & 1 & 1 & 1 \\
 
     1 & 1 & 1 & 1 \\
 
   \end{array}
 
   \end{array}
−
\right]
+
\right]</cmath>
−
\]
 
−
</cmath>
 
−
 
 
 
With above observations, we now count the number of feasible matrixes.
 
With above observations, we now count the number of feasible matrixes.
 
We construct a feasible matrix in the following steps.
 
We construct a feasible matrix in the following steps.
Line 55: Line 53:
  
 
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}}</math>.
+
\boxed{\textbf{(D) }576}</math>.
  
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
  
−
==Alternate Solution (From outside to inside)==
+
==Solution 3 (Multiplication Principle)==
 +
 
 +
Of the sixteen entries in one such array, there are six <math>0</math>s and ten <math>1</math>s. The rows and the columns each have zero, one, two, and three <math>0</math>s, in some order. Once we decide the positions of the <math>0</math>s, we form one such array.
 +
 
 +
We perform the following steps:
 +
<ol style="margin-left: 1.5em;">
 +
  <li>There are <math>\binom41=4</math> ways to choose the row with three <math>0</math>s. After that, there are <math>\binom43=4</math> ways to choose the positions of the three <math>0</math>s.</li><p>
 +
  <li>There are <math>\binom31=3</math> ways to choose the column with three <math>0</math>s. After that, there are <math>\binom32=3</math> ways to choose the positions of the two additional <math>0</math>s.</li><p>
 +
  <li>There are <math>\binom41=4</math> ways to choose the position of the last <math>0:</math> It is the intersection of the column of one <math>0</math> in Step 1 and the row of one <math>0</math> in Step 2.</li><p>
 +
</ol>
 +
Together, the answer is <math>4\cdot4\cdot3\cdot3\cdot4=\boxed{\textbf{(D) }576}.</math>
 +
 
 +
~MRENTHUSIASM
 +
 
 +
==Solution 4 (Multiplication Principle)==
 +
 
 
Since exactly <math>1</math> row sum is <math>4</math> and exactly <math>1</math> column sum is <math>4</math>, there is a unique entry in the array such that it, and every other entry in the same row or column, is a <math>1.</math> Since there are <math>16</math> total entries in the array, there are <math>16</math> ways to choose the entry with only <math>1</math>s in its row and column.
 
Since exactly <math>1</math> row sum is <math>4</math> and exactly <math>1</math> column sum is <math>4</math>, there is a unique entry in the array such that it, and every other entry in the same row or column, is a <math>1.</math> Since there are <math>16</math> total entries in the array, there are <math>16</math> ways to choose the entry with only <math>1</math>s in its row and column.
  
−
WLOG, let that entry be in the top-left corner of the square. Note that there is already <math>1</math> entry numbered <math>1</math> in each unfilled row, and <math>1</math> entry numbered <math>1</math> in each unfilled column. Since exactly <math>1</math> row sum is <math>1</math> and exactly <math>1</math> column sum is <math>1</math>, there is a unique entry in the <math>3\textrm{x}3</math> array of the empty squares such that it, and every other entry in the same row or column in the <math>3\textrm{x}3</math> array is a <math>0.</math> Using a process similar to what we used in the first paragraph, we can see that there are <math>9</math> ways to choose the entry with only <math>0</math> in its row and column (in the <math>3\textrm{x}3</math> array).
+
Without loss of generality, let that entry be in the top-left corner of the square. Note that there is already <math>1</math> entry numbered <math>1</math> in each unfilled row, and <math>1</math> entry numbered <math>1</math> in each unfilled column. Since exactly <math>1</math> row sum is <math>1</math> and exactly <math>1</math> column sum is <math>1</math>, there is a unique entry in the <math>3\times3</math> array of the empty squares such that it, and every other entry in the same row or column in the <math>3\times3</math> array is a <math>0.</math> Using a process similar to what we used in the first paragraph, we can see that there are <math>9</math> ways to choose the entry with only <math>0</math> in its row and column (in the <math>3\times3</math> array).
 +
 
 +
Without loss of generality, let that entry be in the bottom-right corner of the square. Then, the remaining empty squares are the <math>4</math> center squares. Of these, one of the columns of the empty <math>2\times2</math> array will have two <math>1</math>s and the other column will have one <math>1.</math> That happens if and only if exactly <math>1</math> of the remaining squares is filled with a <math>0</math>, and there are <math>4</math> ways to choose that square. Filling that square with a <math>0</math> and the other <math>3</math> squares with <math>1</math>s completes the grid.
 +
 
 +
All in all, there are <math>4\cdot9\cdot16=\boxed{\textbf{(D) }576}</math> ways to complete the grid.
 +
 
 +
~pianoboy
 +
 
 +
~mathboy100 (minor <math>\LaTeX</math> fix)
  
−
WLOG, let that entry be in the bottom right corner of the square. Then, the remaining empty squares are the <math>4</math> center squares. Of these, one of the columns of the empty <math>2\textrm{x}2</math> array will have <math>2</math> <math>1</math>s and the other column will have <math>1</math> <math>1.</math> That happens if and only if exactly <math>1</math> of the remaining squares is filled with a <math>0</math>, and there are <math>4</math> ways to choose that square. Filling that square with a <math>0</math> and the other <math>3</math> squares with <math>1</math>s completes the grid.
+
==Solution 5 (Meta Solving / Conjectures)==
 +
Note that swapping any two rows or any two columns or both from the given example array, leads to a new array that satisfies the condition. There are <math>4</math> rows, and you choose <math>2</math> to swap, so <math>\frac{4!}{2!2!} = 6</math>; likewise for columns. Therefore, <math>6\cdot6 = 36</math>. Clearly, the final answer must be divisible by <math>36</math>, so we can eliminate <math>\textbf{(B)}</math>, <math>\textbf{(C)}</math> and <math>\textbf{(E)}</math>.  
  
−
All in all, there are <math>4*9*16=\boxed{576}</math> ways to complete the grid.
+
Now, you are in exam mode with not much time left. You see that <math>144 = 4\cdot36</math> while <math>576 = 16\cdot36</math>. There are <math>16</math> elements in the array (<math>4</math> rows and <math>4</math> columns), so you go with <math>\boxed{\textbf{(D) }576}</math>, and this is indeed the correct answer!
  
−
pianoboy.
+
~alphamugamma
−
~mathboy100 (minor LaTeX fix)
+
 
 +
==Video Solution (Quick)==
 +
https://youtu.be/NIuo5i3nFzo
 +
 
 +
<i>~Education, the Study of Everything</i>
  
 
==Video Solution==
 
==Video Solution==
Line 76: Line 102:
  
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 +
 +
==Video Solution==
 +
https://youtu.be/JVDlHCSPF6k
  
 
==See Also==
 
==See Also==
 
{{AMC12 box|year=2022|ab=B|num-b=16|num-a=18}}
 
{{AMC12 box|year=2022|ab=B|num-b=16|num-a=18}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 09:49, 4 November 2024

Problem

How many $4 \times 4$ arrays whose entries are $0$s and $1$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 \[\left[ \begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ \end{array} \right]\] satisfies the condition.

$\textbf{(A) }144 \qquad \textbf{(B) }240 \qquad \textbf{(C) }336 \qquad \textbf{(D) }576 \qquad \textbf{(E) }624$

Solution 1 (One-to-One Correspondence)

Note that the arrays and the sum configurations have one-to-one correspondence. Furthermore, the row sum configuration and the column sum configuration are independent of each other. Therefore, the answer is $(4!)^2=\boxed{\textbf{(D) }576}.$

Remark

For any given sum configuration, we can uniquely reconstruct the array it represents. Conversely, for any array, it is clear that we can determine the unique sum configuration associated with it. Therefore, this establishes a one-to-one correspondence between the arrays and the sum configurations.

~bad_at_mathcounts ~MRENTHUSIASM ~tsun26

Solution 2 (Linear Transformation and 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 $i \in \left\{ 1, 2, 3 ,4 \right\}$, the sum of entries in row $i$ is $i$ and the sum of entries in column $i$ is $i$, hereafter called as a benchmark matrix.

Second, we observe that there is a unique benchmark matrix, as shown below: \[\left[ \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ \end{array} \right]\] 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 $4!$.

Step 2: We make a permutation of columns of the matrix obtained after Step 1.

The number of ways is $4!$.

Following from the rule of product, the total number of feasible matrixes is $4! \cdot 4! = \boxed{\textbf{(D) }576}$.

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Solution 3 (Multiplication Principle)

Of the sixteen entries in one such array, there are six $0$s and ten $1$s. The rows and the columns each have zero, one, two, and three $0$s, in some order. Once we decide the positions of the $0$s, we form one such array.

We perform the following steps:

  1. There are $\binom41=4$ ways to choose the row with three $0$s. After that, there are $\binom43=4$ ways to choose the positions of the three $0$s.

  2. There are $\binom31=3$ ways to choose the column with three $0$s. After that, there are $\binom32=3$ ways to choose the positions of the two additional $0$s.

  3. There are $\binom41=4$ ways to choose the position of the last $0:$ It is the intersection of the column of one $0$ in Step 1 and the row of one $0$ in Step 2.

Together, the answer is $4\cdot4\cdot3\cdot3\cdot4=\boxed{\textbf{(D) }576}.$

~MRENTHUSIASM

Solution 4 (Multiplication Principle)

Since exactly $1$ row sum is $4$ and exactly $1$ column sum is $4$, there is a unique entry in the array such that it, and every other entry in the same row or column, is a $1.$ Since there are $16$ total entries in the array, there are $16$ ways to choose the entry with only $1$s in its row and column.

Without loss of generality, let that entry be in the top-left corner of the square. Note that there is already $1$ entry numbered $1$ in each unfilled row, and $1$ entry numbered $1$ in each unfilled column. Since exactly $1$ row sum is $1$ and exactly $1$ column sum is $1$, there is a unique entry in the $3\times3$ array of the empty squares such that it, and every other entry in the same row or column in the $3\times3$ array is a $0.$ Using a process similar to what we used in the first paragraph, we can see that there are $9$ ways to choose the entry with only $0$ in its row and column (in the $3\times3$ array).

Without loss of generality, let that entry be in the bottom-right corner of the square. Then, the remaining empty squares are the $4$ center squares. Of these, one of the columns of the empty $2\times2$ array will have two $1$s and the other column will have one $1.$ That happens if and only if exactly $1$ of the remaining squares is filled with a $0$, and there are $4$ ways to choose that square. Filling that square with a $0$ and the other $3$ squares with $1$s completes the grid.

All in all, there are $4\cdot9\cdot16=\boxed{\textbf{(D) }576}$ ways to complete the grid.

~pianoboy

~mathboy100 (minor $\LaTeX$ fix)

Solution 5 (Meta Solving / Conjectures)

Note that swapping any two rows or any two columns or both from the given example array, leads to a new array that satisfies the condition. There are $4$ rows, and you choose $2$ to swap, so $\frac{4!}{2!2!} = 6$; likewise for columns. Therefore, $6\cdot6 = 36$. Clearly, the final answer must be divisible by $36$, so we can eliminate $\textbf{(B)}$, $\textbf{(C)}$ and $\textbf{(E)}$.

Now, you are in exam mode with not much time left. You see that $144 = 4\cdot36$ while $576 = 16\cdot36$. There are $16$ elements in the array ($4$ rows and $4$ columns), so you go with $\boxed{\textbf{(D) }576}$, and this is indeed the correct answer!

~alphamugamma

Video Solution (Quick)

https://youtu.be/NIuo5i3nFzo

~Education, the Study of Everything

Video Solution

https://youtu.be/_dN_ZHiaiko

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Video Solution

https://youtu.be/JVDlHCSPF6k

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_12B_Problems/Problem_17&oldid=231544"