Difference between revisions of "2023 AIME I Problems/Problem 7"
Mathboy100 (talk | contribs) |
m (→Solution 2) |
||
Line 74: | Line 74: | ||
<math>n</math> can either be <math>0</math> or <math>1</math> mod <math>2</math>. | <math>n</math> can either be <math>0</math> or <math>1</math> mod <math>2</math>. | ||
− | Case 1: <math>n | + | Case 1: <math>n \equiv 0 \pmod{2}</math> |
− | Then, <math>n | + | Then, <math>n \equiv 2 \pmod{4}</math>, which implies <math>n \equiv 1 \pmod{3}</math>. By CRT, <math>n \equiv 4 \pmod{6}</math>, and therefore <math>n \equiv 3 \pmod{5}</math>. Using CRT again, we obtain <math>n \equiv 58 \pmod{60}</math>, which gives <math>16</math> values for <math>n</math>. |
− | Case 2: <math>n | + | Case 2: <math>n \equiv 1 \pmod{2}</math> |
− | <math>n</math> is then <math>3 \pmod{4}</math>. If <math>n | + | <math>n</math> is then <math>3 \pmod{4}</math>. If <math>n \equiv 0 \pmod{3}</math>, then by CRT, <math>n \equiv 3 \pmod{6}</math>, a contradiction. Thus, <math>n \equiv 2 \pmod{3}</math>, which by CRT implies <math>n \equiv 5 \pmod{6}</math>. <math>n</math> can either be <math>0 \pmod{5}</math>, which implies that <math>n \equiv 35 \pmod{60}</math>, <math>17</math> cases; or <math>4 \pmod{5}</math>, which implies that <math>n \equiv 59 \pmod{60}</math>, <math>16</math> cases. |
<math>16 + 16 + 17 = \boxed{49}</math>. | <math>16 + 16 + 17 = \boxed{49}</math>. | ||
~mathboy100 | ~mathboy100 |
Revision as of 17:12, 8 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
.
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)
Solution 2
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