2010 AMC 10B Problem 23

Name the cells with letters:

Why $1$ and $9$ go in those corners. Every cell except the top-left has a cell to its left or above it that is smaller. The digit $1$ has nothing smaller, so it must go top-left. In the same way, $9$ has nothing larger, so it must go bottom-right.

The rules left to check are: rows $a < b$, $c < m < d$, $e < f$, and columns $c < e$, $a < m < f$, $b < d$.

The center $m$ is the busiest cell, so start there. It is larger than $1$, $a$ and $c$, so it is at least $4$. It is smaller than $d$, $f$ and $9$, so it is at most $6$. So $m$ is $4$, $5$ or $6$.

Case $m = 4$.

1. $a$ and $c$ are less than $4$, so they are $2$ and $3$ in some order: $2$ ways.
2. The cells $b, d, e, f$ get $5, 6, 7, 8$. The only rules left among them are $b < d$ and $e < f$ (all the others hold automatically). Choose which two of the four digits go to $b$ and $d$: $6$ ways. The smaller one goes to $b$, and the other two digits go to $e < f$.
3. Total: $2 \cdot 6 = 12$.

Case $m = 6$.

1. $d$ and $f$ are more than $6$, so they are $7$ and $8$ in some order: $2$ ways.
2. The cells $a, b, c, e$ get $2, 3, 4, 5$ with the rules $a < b$ and $c < e$. Choose the two digits for $a$ and $b$: $6$ ways.
3. Total: $2 \cdot 6 = 12$.

Case $m = 5$.

1. The small digits $2, 3, 4$ must fill $a$, $c$, and one more cell. That cell cannot be $d$ or $f$ (they are bigger than $5$), so it is $b$ or $e$.
2. Say $b$ is small. Then the top row is $1, a, b$ and $c$ is the third small digit. Choose $c$ from $2, 3, 4$ ($3$ ways); the other two go to $a < b$ in order. The big digits $6, 7, 8$ fill $d, e, f$ with only the rule $e < f$: choose $d$ ($3$ ways), and the other two go to $e < f$. That is $3 \cdot 3 = 9$ arrays.
3. If instead $e$ is small, flip the grid over the diagonal from $1$ to $9$ (rows become columns). This matches each array of step 8 with one here, so there are $9$ more.
4. Total: $18$.

Altogether: $12 + 12 + 18 = 42$.

The answer is $\boxed{\textbf{(D)}\ 42}$.

When a grid has "increasing" rules, start with the cell that has the most rules on it. Here the center is larger than three cells and smaller than three others, so it has only three possible values. Fixing it splits the other digits into a small group and a big group, and each group can be counted on its own. Flipping the grid over its diagonal is a quick way to reuse a count you already did.

There is a known formula for counting such grids, called the hook length formula (it goes beyond the usual school topics). For each cell, count the cells directly to its right, the cells directly below it, and the cell itself:

The number of grids is $9!$ divided by the product of these numbers:
$$\frac{362880}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1} = \frac{362880}{8640} = 42.$$

Write the cell in row $i$, column $j$ as $(i,j)$. Clearly $1$ is at $(1,1)$ and $9$ at $(3,3)$. The center $(2,2)$ exceeds $(1,1), (1,2), (2,1)$ and is below $(2,3), (3,2), (3,3)$, so the center is $4$, $5$, or $6$.

Center $4$. Then $\{2, 3\}$ fill $(1,2)$ and $(2,1)$ in $2$ ways. The digits $5, 6, 7, 8$ go to $(1,3), (2,3), (3,1), (3,2)$ with only the constraints $(1,3) < (2,3)$ and $(3,1) < (3,2)$: choose which two digits go to the top-right pair, $\binom42 = 6$ ways. Total $2 \cdot 6 = 12$.

Center $6$. Replacing each entry $x$ by $10 - x$ and rotating $180^\circ$ swaps this case with center $4$: also $12$.

Center $5$. Three of $\{2,3,4\}$ must fill $(1,2), (2,1)$ and one of the corners $(1,3)$ or $(3,1)$; the other corner gets a digit from $\{6,7,8\}$. Say $(1,3) < 5$: then $(2,1)$ can be any of $2, 3, 4$ ($3$ ways) and the other two fill row $1$ in increasing order. The digits $6, 7, 8$ go to $(2,3), (3,1), (3,2)$ with $(3,1) < (3,2)$: choose the digit for $(2,3)$, $3$ ways. That is $9$ arrays; by the transpose symmetry, $(3,1) < 5$ gives $9$ more. Total $18$.

Altogether $12 + 18 + 12 = 42$.

The answer is $\boxed{\textbf{(D)}\ 42}$.