Problem:
Define a -grid to be a matrix which satisfies the following two properties:
Find the number of distinct T-grids.
Solution:
Note that choosing of the entries to be 's shows that the number of matrices satisfying () is or . Counting the number of matrices satisfying () but not () and subtracting from will then produce the required answer. The matrices satisfying () but not () fall into two groups: those matrices which have one row, column, or long diagonal of all 's and one row, column, or long diagonal of all 's, and those matrices which have two rows, columns, or diagonals which are both all 's or both all 's. In the first group note that no matrix can have both a row of 's and a column or diagonal of 's, both a column of 's and a row or diagonal of 's, or both a diagonal of 's and a row or column of 's. Thus the only members of the first group are matrices with one row of 's and one row of 's or with one column of 's and one column of 's. There are ways to choose the row or column of 's, ways to choose the row or column of 's, and then ways to fill in the remaining three entries (that is, , , or ). Thus the first group has or members. The members of the second group must, by the previous argument, have two overlapping groups (rows, columns, or diagonals) of the same number. But two overlapping groups of 's would require 's, and the matrix only contains four 's. Thus the second group consists of those matrices with both a row and a column of 's, both a row or column and a diagonal of 's, or two diagonals of 's. Because the two groups of 's require five 's, the remaining entries in the matrix must all be 's. There are matrices of the first type, matrices of the second type, and matrix of the third type. Thus the total number of matrices in the second group is matrices. The number of matrices satisfying () but not () is therefore or . The requested number of T-grids is then .
The problems on this page are the property of the MAA's American Mathematics Competitions