2021 AIME II Problem 3

Attempt Problem 3 of the 2021 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 2021 AIME II solutions, or check the answer key.

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

3.

Find the number of permutations x1,x2,x3,x4,x5x_1, x_2, x_3, x_4, x_5 of numbers 1,2,3,4,51, 2, 3, 4, 5 such that the sum of five products x1x2x3+x2x3x4+x3x4x5+x4x5x1+x5x1x2 \begin{aligned} &x_1x_2x_3 + x_2x_3x_4 \\ &\quad {}+ x_3x_4x_5 + x_4x_5x_1 \\ &\quad {}+ x_5x_1x_2 \end{aligned} is divisible by 3.3.

Answer: 80
Concepts:modular arithmeticpermutationscasework
Difficulty rating: 2350
Solution:

Work modulo 3.3. The value 33 is the only multiple of 3,3, and each of the five products covers three cyclically consecutive positions, so if xi=3x_i = 3 exactly two products avoid position i:i: those covering positions i+1,i+2,i+3i+1, i+2, i+3 and i+2,i+3,i+4i+2, i+3, i+4 (indices mod 55). Their sum is xi+2xi+3(xi+1+xi+4),x_{i+2}x_{i+3}(x_{i+1} + x_{i+4}), and since xi+2xi+3x_{i+2}x_{i+3} is not divisible by 3,3, the condition is xi+1+xi+40(mod3).x_{i+1} + x_{i+4} \equiv 0 \pmod 3.

Among the remaining values, 11 and 44 are 1\equiv 1 while 22 and 55 are 2(mod3),\equiv 2 \pmod 3, so positions i+1i+1 and i+4i+4 must take one value from each class: 222=82 \cdot 2 \cdot 2 = 8 ordered choices. The other two values fill positions i+2i+2 and i+3i+3 in 22 ways. With 55 choices for the position of 3,3, the count is 582=80.5 \cdot 8 \cdot 2 = 80.

← Problem 2#2
Full Exam

Problem 3 in Other Years