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 Note that and can be or We have ways to designate and for a total of So the desired answer is
~MathFun1000 (Rephrasing for clarity)
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 .
The numbers left with us are which are 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, .
Solution 4 (Proportion)
WLOG, let . Then: The sum is divisible by if and only if is divisible by . The possible sums of are Two of them are not multiples of , but four of them are multiples.
A total number of permutations is
of this number, that is, give sums that are multiples of
Solution 5 (Factoring)
This is my first time doing a solution (feel free to edit it)
We have numbers. Considering any as we see that we are left with two terms that are not always divisible by which means that already gives us 5 options. Let's now consider We are left with The two terms left over are since we already have used the remaining numbers are
We now factor since are all not factors of
Now using the number we take two to get a number divisible by for We have possibilities from above. Since we can also have or there are possibilities in all.
Now using we have which results in more possibilities of times more. So, we get
Remember that can be any of different variables. So, we multiply by to get the answer
|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|