AMC 10 · 2010 · #23
Grade 7 countingThe entries in a 3×3 array include all the digits from 1 through 9, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?
Pick an answer.
AMC 10 2010 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: Fill a $3 \times 3$ grid with the digits $1$ through $9$, each used once, so that every row reads left-to-right in increasing order and every column reads top-to-bottom in increasing order. Count how many different grids are possible.
Givens: A $3 \times 3$ grid holds the nine digits $1, 2, \dots, 9$, each exactly once; Each row increases from left to right; Each column increases from top to bottom; Answer choices: (A) $18$, (B) $24$, (C) $36$, (D) $42$, (E) $60$
Unknowns: The number of valid grids
Understand
Restated: Fill a $3 \times 3$ grid with the digits $1$ through $9$, each used once, so that every row reads left-to-right in increasing order and every column reads top-to-bottom in increasing order. Count how many different grids are possible.
Givens: A $3 \times 3$ grid holds the nine digits $1, 2, \dots, 9$, each exactly once; Each row increases from left to right; Each column increases from top to bottom; Answer choices: (A) $18$, (B) $24$, (C) $36$, (D) $42$, (E) $60$
Plan
Primary tool: #2 Make a Systematic List
Secondary: #14 Extreme Principle, #7 Identify Subproblems, #5 Look for a Pattern
"How many arrangements" is the classic trigger for Tool #2 (Make a Systematic List). Nine digits in nine cells is too many to list blindly, so first Tool #14 (Extreme Principle) pins the forced cells: the top-left must be the smallest digit and the bottom-right the largest, and the center is squeezed to just three possible values. That splits the count into a few clean cases — Tool #7 (Identify Subproblems) — organized by the center digit. Inside each case the remaining digits fall into small ordered groups that are easy to count with the multiplication principle. Tool #5 (Look for a Pattern) then reuses one case for its mirror image, halving the work.
Execute — Answer: D
1.NBT.B.3 Step 1 Pin the two corners
- The top-left cell $a$ is smaller than everything in its row and its column, so it is smaller than all eight other digits — it must be $1$.
- The bottom-right cell $i$ is larger than everything in its row and column, so it must be $9$.
💡 The overall smallest digit can only sit where nothing is required to be smaller, and that is the top-left corner; the largest sits in the opposite corner.
1.NBT.B.3 Step 2 Trap the center
- The center $e$ is bigger than $a$, $b$, and $d$ (three cells above-and-left of it), so at least three digits are smaller than $e$, forcing $e \ge 4$.
- It is also smaller than $f$, $h$, and $i$ (three cells below-and-right), so at least three digits are larger, forcing $e \le 6$.
- Thus the center is $4$, $5$, or $6$.
💡 Three cells must be below the center and three above it, so the center digit cannot be too small or too large.
7.SP.C.8 Step 3 Split by the center digit
- Break the count into three cases according to whether the center is $4$, $5$, or $6$.
- Each case fixes which digits are forced into the top-left region versus the bottom-right region, making the leftover cells easy to count.
💡 Fixing the pivot value in the middle turns one hard count into three small independent counts.
3.OA.A.3 Step 4 Count center = 4
- The three digits below the center are the digits smaller than $4$, namely $\{1,2,3\}$; since $a=1$, cells $b$ and $d$ hold $\{2,3\}$ in either order ($2$ ways).
- The remaining digits $\{5,6,7,8\}$ fill the top-right $c$, right-middle $f$, bottom-left $g$, and bottom-middle $h$ (with $i=9$).
- The only ties are $c<f$ (right column) and $g<h$ (bottom row), which are otherwise independent.
- So choose which two of $\{5,6,7,8\}$ go into the right column — the smaller is $c$, the larger is $f$ — and the other two fall into the bottom row in forced order: $\binom{4}{2}=6$ ways.
💡 Once the small digits are placed, splitting the four leftover digits into an ordered pair-and-pair is just choosing two of four.
4.OA.C.5 Step 5 Count center = 6 by symmetry
- Replacing every digit $k$ by $10-k$ and flipping the grid across its center turns increasing rows and columns back into increasing rows and columns, and sends center $4$ to center $6$.
- This is a perfect one-to-one pairing between the two cases, so they have the same count.
💡 The rule "replace $k$ by $10-k$" is a mirror that swaps small and large, matching every center-$4$ grid with exactly one center-$6$ grid.
3.OA.A.3 Step 6 Count center = 5
- With $a=1$ and $i=9$, the leftover small digits $\{2,3,4\}$ and large digits $\{6,7,8\}$ fill $b,c,d,f,g,h$.
- Column and row rules force $b,d$ to be small and $f,h$ to be large; that leaves one small and one large to split between $c$ and $g$.
- Case $c$ small, $g$ large: the smalls $\{2,3,4\}$ go to $b,c,d$ with $b<c$ required and $d$ free — $3$ ways — and independently the larges go to $f,h,g$ with $g<h$ required and $f$ free — $3$ ways, giving $9$.
- Case $g$ small, $c$ large is the mirror, giving another $9$.
💡 The center-$5$ grid has one extra degree of freedom — which diagonal cell holds a small digit — and each choice leaves two tidy ordered triples.
2.NBT.B.5 Step 7 Add the cases
Add the three case counts to get the total number of valid grids.
💡 The three center values cover every grid with no overlap, so the counts simply add.
1.NBT.B.3 The top-left cell $a$ is smaller than everything in its row and its column, so i 1.NBT.B.3 The center $e$ is bigger than $a$, $b$, and $d$ (three cells above-and-left of i 7.SP.C.8 Break the count into three cases according to whether the center is $4$, $5$, or 3.OA.A.3 The three digits below the center are the digits smaller than $4$, namely ${1,2 4.OA.C.5 Replacing every digit $k$ by $10-k$ and flipping the grid across its center turn 3.OA.A.3 With $a=1$ and $i=9$, the leftover small digits $\{2,3,4\}$ and large digits ${ 2.NBT.B.5 Add the three case counts to get the total number of valid grids. Review
Reasonableness: The three cases $e=4,5,6$ are exhaustive (the center can be nothing else) and mutually exclusive (a grid has one center digit), so adding $12+18+12=42$ is legitimate. The symmetry between $e=4$ and $e=6$ shows up as equal counts, a good internal consistency check. The total $42$ matches choice (D), and it also agrees with the standard result that the number of increasing $3\times3$ fillings (standard Young tableaux of a $3\times3$ square) is $9!/(5\cdot4\cdot3\cdot4\cdot3\cdot2\cdot3\cdot2\cdot1) = 362880/8640 = 42$.
Alternative: The hook length formula (Tool #9, Solve an Easier Related Problem, applied to the theory of Young tableaux) gives the answer in one shot: for the $3\times3$ square the hook lengths are $\begin{smallmatrix}5&4&3\\4&3&2\\3&2&1\end{smallmatrix}$, and the count is $9!$ divided by their product, $362880/8640 = 42$. It is faster but hides the structure that the casework makes visible; both give (D).
CCSS standards used (min grade 7)
1.NBT.B.3Compare two two-digit numbers using symbols (Ordering the digits to force $1$ into the top-left corner and $9$ into the bottom-right, and to squeeze the center digit into $\{4,5,6\}$.)7.SP.C.8Find probabilities of compound events using organized lists, tables, and simulation (Organizing the whole count into cases by the center digit and enumerating the valid placements within each case.)3.OA.A.3Solve multiplication and division word problems within 100 (Using the multiplication counting principle inside each case ($2\times6$ for center $4$, $3\times3$ per subcase for center $5$).)4.OA.C.5Generate a number or shape pattern following a given rule (Applying the rule $k\mapsto10-k$ as a symmetry that pairs every center-$4$ grid with a center-$6$ grid, so the two cases share a count.)2.NBT.B.5Fluently add and subtract within 100 (Adding the three case counts $12+18+12$ to reach the total $42$.)
⭐ Lock the forced cells first — $1$ in the top-left, $9$ in the bottom-right, and the center can only be $4$, $5$, or $6$ — then count each center case separately: $12+18+12=42$.
⭐ Lock the forced cells first — $1$ in the top-left, $9$ in the bottom-right, and the center can only be $4$, $5$, or $6$ — then count each center case separately: $12+18+12=42$.
More like this
Same archetype — closest grade level first.