AMC 10 · 2022 · #17

Grade 7 counting

Archetype Constraint Graph Coloring └ Sub-archetype Degree-Driven Extreme Pinning

permutations-basicfactorialfundamental-counting-principlelogical-deductionextreme-principle extreme-principleif-then-reasoningeasier-related-problemsystematic-enumeration ↑ Prerequisites: permutations-basicfundamental-counting-principle

📏 Medium solution 💡 3 insights

Problem

Fill a four by four grid with zeros and ones. The four row sums must be 1, 2, 3, and 4 in some order, and the four column sums must be too. Count all such grids.

Pick an answer.

(A)

144

(B)

240

(C)

336

(D)

576

(E)

624

How to solve

Strategy Extreme Principle

Sixteen cells with two entries each is 2¹⁶ = 65536 grids — far too many to touch one at a time, and there is no obvious formula. Tool #14 (Extreme Principle) breaks it open: do not start in the middle of the grid, start at the sums that leave no room to move. A row that sums to 4 across four cells must be all 1s, and a column that sums to 4 must be all 1s. Those two full lines then pin the row that sums to 1 and the column that sums to 1, because each of those already receives its single 1 from a full line. Tool #9 (Solve an Easier Related Problem) peels those four settled lines away and leaves a 2 × 2 corner that is the same puzzle at half the size. Tool #5 (Look for a Pattern) reads off the rule the finished grid obeys. Tool #4 (Introduce a Variable) names the row sums r₁, …, r₄ and the column sums c₁, …, c₄ so the argument can be written once instead of case by case. Tool #2 (Make a Systematic List) then counts, not grids, but the two orderings that generate them. Tool #3 (Eliminate Possibilities) matches the count against the five choices.

1STEP 1

Name the two orderings

Rows and columns give the same grand total.

r₁ + r₂ + r₃ + r₄ = 1 + 2 + 3 + 4 = 10 = c₁ + c₂ + c₃ + c₄

2STEP 2

Fill the lines summing to four

Summing to four makes a line all ones.

r_i = 4 → a_i1 = a_i2 = a_i3 = a_i4 = 1, c_j = 4 → a₁j = a₂j = a₃j = a₄j = 1

3STEP 3

Fill the lines summing to one

A line summing to one has one place to go.

r_i = 1 → a_ij = 1 only at the column with c_j = 4; c_j = 1 → a_ij = 1 only at the row with r_i = 4

4STEP 4

Peel off four lines

Peeling four lines leaves a small grid.

& c=3 & c=2 ; r=3 & 1 & 1 ; r=2 & 1 & 0

5STEP 5

One grid per pair of orderings

The two orderings determine the grid completely.

a_ij = 1 ⇔ r_i + c_j ≥ 5

6STEP 6

Count the orderings and multiply

Multiply the two ordering counts.

4! · 4! = 24 · 24 = 576

7STEP 7

Match the choice

The result is 576.

4! · 4! = 576 → (D)

Answer

576

A symmetry check settles it independently. Swapping two rows of a valid grid leaves the set of row sums untouched and does not change any column sum, so the result is still valid; the same holds for swapping two columns. So shuffling the four rows and the four columns of any valid grid always lands on a valid grid, giving 24 · 24 = 576 results. Those 576 are all different: the row sums are 1, 2, 3, 4 with no repeats, so moving a row changes which row carries which sum and therefore changes the grid. Hence the valid grids split into groups of exactly 576, and the total must be a multiple of 576. Of the five choices only 576 is a multiple of 576 — 144, 240 and 336 are too small, and 624 is not a multiple. The count also passes smaller checks: every valid grid holds exactly 10 ones and 6 zeros, and swapping the roles of 0 and 1 turns row sums 1, 2, 3, 4 into row sums 3, 2, 1, 0 and does the same to the columns, so the zero pattern is a mirror image of the one pattern, exactly as the finished grid shows.

💡Key takeaway

Start where there is no room to move: a row summing to 4 must be all 1s, and that single fact cascades until every cell is forced. So the only real decision is which row gets which total and which column gets which total, and that is 4! · 4! = 576.

Name the two orderings
The 4s force two full lines
The 1s have nowhere else to go
Peel four lines, a 2x2 is left
One grid per pair of orderings
Count the orderings and multiply
Match the count to a choice