Problem:
The 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?
Answer Choices:
A. 18
B. 24
C. 36
D. 42
E. 60
Solution:
Let aij​ denote the entry in row i and column j. he given conditions imply that a11​=1,a33​=9, and a22​=4,5, or 6 . If a22​=4, then {a12​,a21​}={2,3}, and the sets {a31​,a32​} and {a13​,a23​} are complementary subsets of {5,6,7,8}. There are (24​)=6 ways to choose {a31​,a32​} and {a13​,a23​}, and only one way to order the entries. There are 2 ways to order {a12​,a21​}, so 12 arrays with a22​=4 meet the given conditions. Similarly, the conditions are met by 12 arrays with a22​=6. If a22​=5, then {a12​,a13​,a23​} and {a21​,a31​,a32​} are complementary subsets of {2,3,4,6,7,8} subject to the conditions a12​<5, a21​<5,a32​>5, and a23​>5. Thus {a12​,a13​,a23​}î€ ={2,3,4} or {6,7,8}, so its elements can be chosen in (36​)−2=18 ways. Both the remaining entries and the ordering of all entries are then determined, so 18 arrays with a22​=5 meet the given conditions.
Altogether, the conditions are met by 12+12+18=42​ arrays.
The problems on this page are the property of the MAA's American Mathematics Competitions