Problem:
Let be the number of ways to place the integers through in the cells of a grid so that for any two cells sharing a side, the difference between the numbers in those cells is not divisible by . One way to do this is shown below. Find the number of positive integer divisors of .
Solution:
Answer (144):
Replace each integer with its remainder upon division by 3 . Then there are 4 copies of each of the numbers 0,1 , and 2 , and the given condition implies that no two cells sharing a side can contain the same number. It suffices to compute the number of such labellings and to multiply this by .
Observe that each of the six columns must contain two distinct numbers. That is, each column must contain either a 01 pair, a 02 pair, or a 12 pair. For there to be four zeros in the grid, the pairs 01 and 02 must appear in a total of 4 columns, implying that the pair 12 must appear twice. Similarly, each of 01 and 02 must appear twice.
There are ways to arrange the order of these columns, and 2 ways to orient the first column. Note that each pair, 01,02 , or 12 , shares at least one entry with any adjacent pair, and these shared entries cannot appear in the same row of the grid. Thus the orientation of any pair determines the orientation of the pair in the next column, implying that the orientation of the pairs in all columns is determined by the orientation of the pair in the first column.
In total, there are 180 ways to fill in the grid in this manner. Hence . The requested number of positive integer divisors of is .
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions