2010 AMC 12B Problem 17

Question

The entries in a

3\times3

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?

18

24

36

42

60

The top-left entry is forced to be

1

and the bottom-right to be

9

Split into cases by the center entry, which must be

4, 5,

or

6

Write

a_{ij}

for the entry in row

i,

column

j.

The conditions force

a_{11}=1,

a_{33}=9,

and

a_{22}\in\{4,5,6\}.

If

a_{22}=4,

then

\{a_{12},a_{21}\}=\{2,3\}

and

\{5,6,7,8\}

split as complementary pairs filling the rest of the last row and column:

\binom42=6

splits times

2

orders for

\{2,3\}

gives

12

arrays. By symmetry

a_{22}=6

also gives

12.

If

a_{22}=5,

then

\{a_{12},a_{13},a_{23}\}

and

\{a_{21},a_{31},a_{32}\}

are complementary subsets of

\{2,3,4,6,7,8\}

subject to the ordering constraints. The first set can be any three-element subset except

\{2,3,4\}

or

\{6,7,8\},

giving

\binom63-2=18

arrays.

Altogether

12+12+18=42.

Thus, the correct answer is D.

Problem 17 in other years