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