Difference between revisions of "2023 AIME I Problems/Problem 7"
MRENTHUSIASM (talk | contribs) m (→Solution 2 (Simpler)) |
m (→Solution 2 (Simpler)) |
||
Line 20: | Line 20: | ||
==Solution 2 (Simpler)== | ==Solution 2 (Simpler)== | ||
− | Because the LCM of all of the numbers we are dividing by is 60, we know that all of the remainders are 0 again at 60, meaning that we have a cycle that repeats itself every 60 numbers. | + | Because the LCM of all of the numbers we are dividing by is <math>60</math>, we know that all of the remainders are <math>0</math> again at <math>60</math>, meaning that we have a cycle that repeats itself every <math>60</math> numbers. |
− | After listing all of the remainders up to 60, we find that 35, 58, and 59 are extra-distinct. So, we have 3 numbers every 60 which are extra-distinct. <math>60\cdot16</math> | + | After listing all of the remainders up to <math>60</math>, we find that <math>35</math>, <math>58</math>, and <math>59</math> are extra-distinct. So, we have <math>3</math> numbers every <math>60</math> which are extra-distinct. <math>60\cdot16 = 960</math> and <math>3\cdot16 = 48</math>, so we have <math>48</math> extra-distinct numbers in the first <math>960</math> numbers. Because of our pattern, we know that the numbers from <math>961</math> thru <math>1000</math> will have the same remainders as <math>1</math> thru <math>40</math>, so we have <math>1</math> other extra-distinct number (<math>35</math>). |
− | 48 + 1 = | + | <math>48 + 1 = \boxed{49}</math>. |
~Algebraik | ~Algebraik |
Revision as of 13:25, 9 February 2023
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
. By CRT,
, and therefore
. Using CRT again, we obtain
, which gives
values for
.
Case 2:
is then
. If
, then by CRT,
, a contradiction. Thus,
, which by CRT implies
.
can either be
, which implies that
,
cases; or
, which implies that
,
cases.
.
~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)
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.