2021 AIME II Problem 3

Below is the professionally curated solution for Problem 3 of the 2021 AIME II, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:modular arithmeticpermutationscasework

Difficulty rating: 2350

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+x5x1x2x_1x_2x_3 + x_2x_3x_4 + x_3x_4x_5 + x_4x_5x_1 + x_5x_1x_2 is divisible by 3.3.

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 2Full ExamProblem 4

Problem 3 in Other Years