Problem:
In the grid shown, of the squares are to be shaded so that there are two shaded squares in each row and three shaded squares in each column. Let be the number of shadings with this property. Find the remainder when is divided by .
Solution:
There are ways to shade three squares in the first column. Given a shading scheme for the first column, consider the ways the second, third, and fourth columns can then be shaded. If the shaded squares in the second column are in the same rows as those of the first column, then the shading pattern for the last two columns is uniquely determined. Thus there are shadings in which the first two columns have squares in the same rows shaded. Next shade the second column so that two of the shaded squares are in the same rows as shaded squares in the first column. Given a shading of the first column, there are ways to choose the two shaded rows in common, then ways to choose the third shaded square in this column. This leaves two rows with no shaded squares, so the squares in these rows must be shaded in the third and fourth columns. There are also two rows with one shaded square each, one of these in the first column and one in the second. For the first of these rows the square can be shaded in the same row in the third or fourth column, for two choices, and this uniquely determines the shading in the second of these rows. Thus there are shadings in which the first two columns have two shaded rows in common. Next shade the second column so that only one of the shaded squares is in the same row as a shaded square in the first column. The row containing the shaded square in both columns can be selected in ways and the other two shaded squares in the second column in ways. This leaves one row with no shaded squares, so the squares in this row in the third and fourth columns must be shaded. There are four rows each with one square shaded in the first two columns. Two of these rows must be shaded in the third column, and two in the fourth. This can be done in ways. Thus there are shadings in which the first two columns have one shaded row in common. Finally, if the first two columns have no shaded row in common, then the shading of the second column is uniquely determined. The three squares to be shaded in the third column can be selected in ways, and the shading for the fourth column is then uniquely determined. There are shading patterns in which the first two columns have no shaded row in common. Thus the total number of shadings is , and the requested remainder is .
The three shaded squares in the first column can be chosen in ways. For , there are ways to choose the shaded squares in the second column so that rows have two shaded squares. No shaded square in the third column can be in one of these rows. In each case there are also rows with no shaded squares, and each of these rows must contain a shaded square in the third column. The remaining shaded squares in the third column must be chosen from the remaining rows. Thus there are ways to choose the shaded squares in the third column. In each case, the shaded squares in the fourth column are uniquely determined. Therefore , and the requested remainder is .
The problems on this page are the property of the MAA's American Mathematics Competitions