2021 AIME II Problems/Problem 3
Find the number of permutations of numbers such that the sum of five products is divisible by .
Since is one of the numbers, a product with a in it is automatically divisible by , so WLOG , we will multiply by afterward since any of would be , after some cancelation we see that now all we need to find is the number of ways that is divisible by , since is never divisible by , now we just need to find the number of ways is divisible by , after some calculation you will see that there are ways to choose and in this way. So the desired answer is .
Solution 2 (Cyclic Symmetry and Casework)
The expression has cyclic symmetry. Without the loss of generality, let It follows that We have:
- are congruent to in some order.
We construct the following table for the case with all values in modulo For Row 1, can be either or and can be either or By the Multiplication Principle, Row 1 produces permutations. Similarly, Rows 2, 5, and 6 each produce permutations.
Together, we get permutations for the case By the cyclic symmetry, the cases and all have the same count. Therefore, the total number of permutations is
WLOG, let So, the terms are divisible by .
We are left with and . We need The only way is when They are or (mod 3)
The numbers left with us are which are (mod ) respectively.
(of or ) (of or ) = .
(of or ) (of or ) =
But, as we have just two and two , Hence, We will have to take and Among these two, we have a and in common, i.e. (because and are common in and )
So, i.e. values.
For each value of we get values for Hence, in total, we have ways.
But any of the can be So,
|2021 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|