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"

(→‎Problem)
(→‎Solution 5 (Meta Solving / Conjectures))
 
(23 intermediate revisions by 5 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>
 +
 
 +
~bad_at_mathcounts ~MRENTHUSIASM
 +
 
 +
==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 29:
  
 
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 36:
 
     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 49:
  
 
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*3</math> array of the empty squares such that it, and every other entry in the same row or column in the <math>3*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*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)
 +
 
 +
==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>.
 +
 
 +
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!
  
−
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*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.
+
~alphamugamma
  
−
All in all, there are <math>4*9*16=\boxed{576}</math> ways to complete the grid.
 
  
−
pianoboy.
+
==Video Solution (Quick)==
 +
https://youtu.be/NIuo5i3nFzo
 +
 
 +
<i>~Education, the Study of Everything</i>
 +
 
 
==Video Solution==
 
==Video Solution==
  
Line 74: Line 99:
  
 
~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 00:19, 10 July 2023

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}.$

~bad_at_mathcounts ~MRENTHUSIASM

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=195478"