2023 AIME II Problem 10

Attempt Problem 10 of the 2023 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2023 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

10.

Let NN be the number of ways to place the integers 11 through 1212 in the 1212 cells of a 2×62 \times 6 grid so that for any two cells sharing a side, the difference between the numbers in those cells is not divisible by 3.3. One way to do this is shown below. Find the number of positive integer divisors of N.N.

Answer: 144
Concepts:modular arithmeticmultiset permutationsfactor counting
Difficulty rating: 2920
Solution:

The condition says adjacent cells have different residues mod 3.3. Each residue class among 1,,121, \ldots, 12 has exactly 44 members, so N=K(4!)3,N = K \cdot (4!)^3, where KK is the number of ways to fill the grid with residues 0,1,2,0, 1, 2, each used 44 times, with adjacent cells different.

A column is an ordered pair (a,b)(a, b) of distinct residues. If the current column is (a,b)(a, b) and ee is the third residue, the next column must be one of (b,a),(b, a), (b,e),(b, e), (e,a):(e, a): each of the three unordered pairs {a,b},\{a,b\}, {b,e},\{b,e\}, {a,e}\{a,e\} occurs in exactly one allowed orientation. So a residue pattern is determined by the sequence of six unordered pairs together with the orientation of the first column. Since each residue must appear 44 times, each of the three pairs must be used exactly twice, giving 6!2!2!2!=90\frac{6!}{2!\,2!\,2!} = 90 sequences and K=290=180.K = 2 \cdot 90 = 180.

Therefore N=180243N = 180 \cdot 24^3 =2,488,320= 2{,}488{,}320 =211355,= 2^{11} \cdot 3^5 \cdot 5, which has 1262=14412 \cdot 6 \cdot 2 = 144 positive divisors.

← Problem 9#9
Full Exam

Problem 10 in Other Years