Difference between revisions of "2023 AIME I Problems/Problem 7"
m (→Solution 2 (Simpler)) |
(→Solution 4 (Small addition to solution 2)) |
||
(9 intermediate revisions by 6 users not shown) | |||
Line 4: | Line 4: | ||
==Solution 1== | ==Solution 1== | ||
− | <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 \equiv 0 \pmod{2}</math> | Case 1: <math>n \equiv 0 \pmod{2}</math> | ||
− | Then, <math>n \equiv 2 \pmod{4}</math>, which implies <math>n \equiv 1 \pmod{3}</math> | + | Then, <math>n \equiv 2 \pmod{4}</math>, which implies <math>n \equiv 1 \pmod{3}</math> and <math>n \equiv 4 \pmod{6}</math>, and therefore <math>n \equiv 3 \pmod{5}</math>. Using [[Chinese Remainder Theorem|CRT]], we obtain <math>n \equiv 58 \pmod{60}</math>, which gives <math>16</math> values for <math>n</math>. |
Case 2: <math>n \equiv 1 \pmod{2}</math> | Case 2: <math>n \equiv 1 \pmod{2}</math> | ||
− | <math>n</math> is then <math>3 \pmod{4}</math>. If <math>n \equiv 0 \pmod{3}</math> | + | <math>n</math> is then <math>3 \pmod{4}</math>. If <math>n \equiv 0 \pmod{3}</math>, <math>n \equiv 3 \pmod{6}</math>, a contradiction. Thus, <math>n \equiv 2 \pmod{3}</math>, which 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> by CRT, giving <math>17</math> cases; or <math>4 \pmod{5}</math>, which implies that <math>n \equiv 59 \pmod{60}</math> by CRT, giving <math>16</math> cases. |
− | <math>16 + 16 + 17 = \boxed{ | + | The total number of extra-distinct numbers is thus <math>16 + 16 + 17 = \boxed{049}</math>. |
~mathboy100 | ~mathboy100 | ||
Line 24: | Line 24: | ||
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>). | 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>). | ||
− | <math>48 + 1 = \boxed{ | + | <math>48 + 1 = \boxed{049}</math>. |
~Algebraik | ~Algebraik | ||
Line 91: | Line 91: | ||
Therefore, the number extra-distinct <math>n</math> in this subcase is 16. | Therefore, the number extra-distinct <math>n</math> in this subcase is 16. | ||
− | Putting all cases together, the total number of extra-distinct <math>n</math> is <math>16 + 17 + 16 = \boxed{ | + | Putting all cases together, the total number of extra-distinct <math>n</math> is <math>16 + 17 + 16 = \boxed{049}</math>. |
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
+ | |||
+ | ==Solution 4 (Small addition to solution 2)== | ||
+ | We need to find that <math>35</math>, <math>58</math>, and <math>59</math> are all extra-distinct numbers smaller then <math>61.</math> | ||
+ | |||
+ | Let <math>k \in \left\{2, 3, 4, 5, 6 \right\}.</math> Denote the remainder in the division of <math>a</math> by <math>b</math> as <math>{\rm Rem} \ \left( a, b \right).</math> | ||
+ | |||
+ | <math>{\rm Rem} \ \left( -1, k \right) = k - 1 \implies {\rm Rem} \ \left( 59, k \right) = k - 1 = \left\{1, 2, 3, 4, 5 \right\}\implies 59</math> is extra-distinct. | ||
+ | <math>{\rm Rem} \ \left( -2, k \right) = k - 2 \implies {\rm Rem} \ \left( 58, k \right) = k - 2 = \left\{0, 1, 2, 3, 4 \right\} \implies 58</math> is extra-distinct. | ||
+ | <cmath>{\rm Rem} \ \left( x + 12y, k \right) = {\rm Rem} \ \left(x, k \right) + \left\{0, 0, 0, {\rm Rem} \ \left(12y, k \right), 0 \right\}.</cmath> | ||
+ | We need to check all of the remainders up to <math>12 - 3 = 9</math> and remainders | ||
+ | <cmath>{\rm Rem} \ \left( 59 - 12, k \right) = {\rm Rem} \ \left( 59 - 36, k \right) = \left\{1, 2, 3, 3, 5 \right\}, | ||
+ | {\rm Rem} \ \left( 59 - 48, k \right) = \left\{1, 2, 3, 1, 5 \right\},</cmath> | ||
+ | <math>{\rm Rem} \ \left( 59 - 24, k \right) ={\rm Rem} \ \left(35, k \right) = \left\{1, 2, 3, 0, 5 \right\} \implies 35</math> is extra-distinct. | ||
+ | <math>58 - 12 = 46 \implies {\rm Rem} \ \left( 46, 5 \right) = 1 = {\rm Rem} \ \left( 46, 3 \right), </math> | ||
+ | <math>58 - 24 = 34 \implies {\rm Rem} \ \left( 34, 5 \right) = 4 = {\rm Rem} \ \left( 34, 6 \right), </math> | ||
+ | <math>58 - 36 = 22 \implies {\rm Rem} \ \left( 22, 5 \right) = 2 = {\rm Rem} \ \left( 22, 4 \right), </math> | ||
+ | <math>58 - 48 = 10 \implies {\rm Rem} \ \left( 10, 5 \right) = 0 = {\rm Rem} \ \left( 10, 2 \right). </math> | ||
+ | |||
+ | '''vladimir.shelomovskii@gmail.com, vvsss''' | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/8oOik9d1fWM | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
==See also== | ==See also== |
Latest revision as of 17:55, 31 October 2023
Contents
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)
Solution 4 (Small addition to solution 2)
We need to find that ,
, and
are all extra-distinct numbers smaller then
Let Denote the remainder in the division of
by
as
is extra-distinct.
is extra-distinct.
We need to check all of the remainders up to
and remainders
is extra-distinct.
vladimir.shelomovskii@gmail.com, vvsss
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.