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:
We begin by simplifying the problem using residues . Replace all numbers congruent to with 0, those congruent to with 1, and those congruent to with 2. This transforms the original problem into arranging four 0s, four 1s, and four 2s into a grid such that no two identical numbers are adjacent (horizontally or vertically). After solving the simplified problem, we will multiply the result by to account for the permutations of the actual numbers within each residue class.
Next, observe that adjacent numbers in the grid—especially those vertically connected—must differ. To satisfy this, we consider partitioning the grid into 6 vertical pairs (each a pair of adjacent cells in a column). We aim to use only distinct-residue pairs: (0,1), (0,2), and (1,2). Each such pair appears exactly twice so that each residue appears 4 times in total.
There are ways to assign the six pairs such that we use each of the three pair types exactly twice.
Now, for each of these 90 pair arrangements, we consider how to build the full grid. Once a valid arrangement of vertical pairs is fixed, the adjacency constraint restricts how these pairs can be sequenced horizontally. In fact, it can be shown that there are exactly two valid configurations for the first column, and once that is fixed, the rest of the grid is uniquely determined by adjacency propagation.
Therefore, there are valid ways to arrange the residue classes in the grid.
To recover the original values, we now assign specific numbers to the positions labeled 0, 1, and 2. There are ways to assign numbers to each residue class, so the total number of configurations is .
Now we compute the number of positive divisors of 2488320. We factorize as .
The number of positive divisors is .
The problems on this page are the property of the MAA's American Mathematics Competitions