Difference between revisions of "2021 AIME II Problems/Problem 3"
MRENTHUSIASM (talk | contribs) (→Solution 5 (Factoring)) |
MRENTHUSIASM (talk | contribs) m (→Solution 5 (Factoring)) |
||
Line 98: | Line 98: | ||
Now using the number <math>1,2,4,5,</math> we take two to get a number divisible by <math>3</math> for <math>(x_2 + x_5):</math> | Now using the number <math>1,2,4,5,</math> we take two to get a number divisible by <math>3</math> for <math>(x_2 + x_5):</math> | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | 1+5 &\equiv 0 \pmod{3} \\ | + | 1+5 &\equiv 0 \pmod{3}, \\ |
− | 4+2 &\equiv 0 \pmod{3} \\ | + | 4+2 &\equiv 0 \pmod{3}, \\ |
− | 4+5 &\equiv 0 \pmod{3} \\ | + | 4+5 &\equiv 0 \pmod{3}, \\ |
− | 1+2 &\equiv 0 \pmod{3} | + | 1+2 &\equiv 0 \pmod{3}. |
\end{align*}</cmath> | \end{align*}</cmath> | ||
We have <math>4</math> possibilities from above. Since we can also have <math>5+1</math> or <math>2+4,</math> there are <math>4\cdot2=8</math> possibilities in all. | We have <math>4</math> possibilities from above. Since we can also have <math>5+1</math> or <math>2+4,</math> there are <math>4\cdot2=8</math> possibilities in all. |
Latest revision as of 03:52, 11 March 2023
Contents
Problem
Find the number of permutations of numbers
such that the sum of five products
is divisible by
.
Solution 1
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
~math31415926535
~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
~MRENTHUSIASM
Solution 3
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,
.
-Arnav Nigam
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
vladimir.shelomovskii@gmail.com, vvsss
Solution 5 (Factoring)
This is my first time doing a solution (feel free to edit it)
We have
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
Video Solution
https://www.youtube.com/watch?v=HikWWhQlkVw
See Also
2021 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.