2022 AMC 12B Problem 17

Problem 17 of 25IntermediateCounting & Probability

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

\begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \end{bmatrix}

satisfies the condition.

Show solution

Solution

The row with sum

4

is all

1

s and the column with sum

4

is all

1

s. There are

4!

ways to assign the row sums

1, 2, 3, 4

to the four rows, and

4

choices for which column has sum

4.

Delete that column. The remaining

4 \times 3

array has row sums

0, 1, 2, 3

and must have column sums

1, 2, 3.

The all-zero and all-one rows are forced; the rows of reduced sum

1

and

2

can be placed in

6

ways to produce column sums

1, 2, 3

in some order. The total is

24 \cdot 4 \cdot 6 = 576.

Thus, the correct answer is D.