2023 AIME I Problems/Problem 7
Problem
Call a positive integer extra-distinct if the remainders when is divided by and are distinct. Find the number of extra-distinct positive integers less than .
Solution 1
can either be or (mod ).
Case 1:
Then, , which implies and , and therefore . Using CRT, we obtain , which gives values for .
Case 2:
is then . If , , a contradiction. Thus, , which implies . can either be , which implies that by CRT, giving cases; or , which implies that by CRT, giving cases.
The total number of extra-distinct numbers is thus .
~mathboy100
Solution 2 (Simpler)
Because the LCM of all of the numbers we are dividing by is , we know that all of the remainders are again at , meaning that we have a cycle that repeats itself every numbers.
After listing all of the remainders up to , we find that , , and are extra-distinct. So, we have numbers every which are extra-distinct. and , so we have extra-distinct numbers in the first numbers. Because of our pattern, we know that the numbers from thru will have the same remainders as thru , so we have other extra-distinct number ().
.
~Algebraik
Solution 3
.
We have . This violates the condition that is extra-distinct. Therefore, this case has no solution.
.
We have . This violates the condition that is extra-distinct. Therefore, this case has no solution.
.
We have . This violates the condition that is extra-distinct. Therefore, this case has no solution.
.
The condition implies , .
Because is extra-distinct, for is a permutation of . Thus, .
However, conflicts . Therefore, this case has no solution.
.
The condition implies and .
Because is extra-distinct, for is a permutation of .
Because , we must have . Hence, .
Hence, . Hence, .
We have . Therefore, the number extra-distinct in this case is 16.
.
The condition implies and .
Because is extra-distinct, and are two distinct numbers in . Because and is odd, we have . Hence, or 4.
, , .
We have .
We have . Therefore, the number extra-distinct in this subcase is 17.
, , .
.
We have . Therefore, the number extra-distinct in this subcase is 16.
Putting all cases together, the total number of extra-distinct is .
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution
~MathProblemSolvingSkills.com
See also
2023 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
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.