2023 AIME II Problems/Problem 10
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 
![\[\begin{array}{|c|c|c|c|c|c|} \hline \,1\, & \,3\, & \,5\, & \,7\, & \,9\, & 11 \\ \hline \,2\, & \,4\, & \,6\, & \,8\, & 10 & 12 \\ \hline \end{array}\]](http://latex.artofproblemsolving.com/f/d/b/fdba8f1061b07630343b8333d80a69ee33cbc5ca.png)
Solution 1
We replace the numbers which are 0 mod 3 to 0, 1 mod 3 to 1, and 2mod 3 to 2.
Then, the problem is equivalent to arranging 4 0's,4 1's, and 4 2's into the grid (and then multiplying by 
to account for replacing the remainder numbers with actual numbers) such that no 2 of the same numbers are adjacent.
Then, the numbers which are vertically connected must be different. 2 1s must be connected with 2 2s, and 2 1s must be connected with 2 2s (vertically), as if there are less 1s connected with either, then there will be 2s or 3s which must be connected within the same number. For instance if we did did: - 12 x 3 - 13 x 1 Then we would be left with 23 x1, and 2 remaining 3s which aren't supposed to be connected, so it is impossible. Similar logic works for why all 1s can't be connected with all 2s.
Thus, we are left with the problem of re-arranging 2x 12 pairs, 2x 13 pairs, 2x 23 pairs. Notice that the pairs can be re-arranged horizontally in any configuration, but when 2 pairs are placed adjacent there is only 1 configuration for the rightmost pair to be set after the leftmost one has been placed.
We have 
ways to horizontally re-arrange the pairs, with 2 ways to set the initial leftmost column. Thus, there are 180 ways to arrange the pairs. Accounting for the initial simplification of the problem with 1-12 -> 0-3, we obtain the answer is:
![\[2488320=2^{11}\cdot3^5\cdot5^1\]](http://latex.artofproblemsolving.com/c/3/8/c38969618a06b141437d6edba0187da1f7ada5b6.png)
The number of divisors is: 
~SAHANWIJETUNGA
See also
| 2023 AIME II (Problems • Answer Key • Resources) | ||
| Preceded by Problem 9 |
Followed by Problem 11 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
