Difference between revisions of "2022 AIME I Problems/Problem 13"
(→See Also) |
m (→Solution 2 (similar(?) to solution 1 but reworded (not exactly for clarity))) |
||
(30 intermediate revisions by 18 users not shown) | |||
Line 2: | Line 2: | ||
Let <math>S</math> be the set of all rational numbers that can be expressed as a repeating decimal in the form <math>0.\overline{abcd},</math> where at least one of the digits <math>a,</math> <math>b,</math> <math>c,</math> or <math>d</math> is nonzero. Let <math>N</math> be the number of distinct numerators obtained when numbers in <math>S</math> are written as fractions in lowest terms. For example, both <math>4</math> and <math>410</math> are counted among the distinct numerators for numbers in <math>S</math> because <math>0.\overline{3636} = \frac{4}{11}</math> and <math>0.\overline{1230} = \frac{410}{3333}.</math> Find the remainder when <math>N</math> is divided by <math>1000.</math> | Let <math>S</math> be the set of all rational numbers that can be expressed as a repeating decimal in the form <math>0.\overline{abcd},</math> where at least one of the digits <math>a,</math> <math>b,</math> <math>c,</math> or <math>d</math> is nonzero. Let <math>N</math> be the number of distinct numerators obtained when numbers in <math>S</math> are written as fractions in lowest terms. For example, both <math>4</math> and <math>410</math> are counted among the distinct numerators for numbers in <math>S</math> because <math>0.\overline{3636} = \frac{4}{11}</math> and <math>0.\overline{1230} = \frac{410}{3333}.</math> Find the remainder when <math>N</math> is divided by <math>1000.</math> | ||
+ | |||
+ | ==Solution 1== | ||
+ | |||
+ | <math>0.\overline{abcd}=\frac{abcd}{9999} = \frac{x}{y}</math>, <math>9999=9\times 11\times 101</math>. | ||
+ | |||
+ | Then we need to find the number of positive integers <math>x</math> that (with one of more <math>y</math> such that <math>y|9999</math>) can meet the requirement <math>1 \leq {x}\cdot\frac{9999}{y} \leq 9999</math>. | ||
+ | |||
+ | Make cases by factors of <math>x</math>. (A venn diagram of cases would be nice here.) | ||
+ | |||
+ | |||
+ | Case <math>A</math>: | ||
+ | |||
+ | <math>3 \nmid x</math> and <math>11 \nmid x</math> and <math>101 \nmid x</math>, aka <math>\gcd (9999, x)=1</math>. | ||
+ | |||
+ | Euler's totient function counts these: | ||
+ | <cmath>\varphi \left(3^2 \cdot 11 \cdot 101 \right) = ((3-1)\cdot 3)(11-1)(101-1)= \bf{6000}</cmath> values (but it's enough to note that it's a multiple of 1000 and thus does not contribute to the final answer) | ||
+ | |||
+ | Note: You don't need to know this formula. The remaining cases essentially re-derive the same computation for other factors of <math>9999</math>. This case isn't actually different. | ||
+ | |||
+ | The remaining cases have <math>3</math> (or <math>9</math>), <math>11</math>, and/or <math>101</math> as factors of <math>abcd</math>, which cancel out part of <math>9999</math>. | ||
+ | Note: Take care about when to use <math>3</math> vs <math>9</math>. | ||
+ | |||
+ | |||
+ | Case <math>B</math>: <math>3|x</math>, but <math>11 \nmid x</math> and <math>101 \nmid x</math>. | ||
+ | |||
+ | Then <math>abcd=9x</math> to leave 3 uncancelled, and <math>x=3p</math>, | ||
+ | so <math>x \leq \frac{9999}{9} = 1111</math>, giving: | ||
+ | |||
+ | <math>x \in 3 \cdot \{1, \dots \left\lfloor \frac{1111}{3}\right\rfloor\}</math>, | ||
+ | |||
+ | <math>x \notin (3\cdot 11) \cdot \{1 \dots \left\lfloor \frac{1111}{3\cdot 11}\right\rfloor\}</math>, | ||
+ | |||
+ | <math>x \notin (3 \cdot 101) \cdot \{1 \dots \left\lfloor \frac{1111}{3 \cdot 101}\right\rfloor\}</math>, | ||
+ | |||
+ | for a subtotal of <math>\left\lfloor \frac{1111}{3}\right\rfloor - (\left\lfloor\frac{1111}{3 \cdot 11}\right\rfloor + \left\lfloor\frac{1111}{3 \cdot 101}\right\rfloor ) = 370 - (33+3) = \bf{334}</math> values. | ||
+ | |||
+ | |||
+ | Case <math>C</math>: <math>11|x</math>, but <math>3 \nmid x</math> and <math>101 \nmid x</math>. | ||
+ | |||
+ | Much like previous case, <math>abcd</math> is <math>11x</math>, so <math>x \leq \frac{9999}{11} = 909 </math>, | ||
+ | |||
+ | giving <math>\left\lfloor \frac{909}{11}\right\rfloor - \left(\left\lfloor\frac{909}{11 \cdot 3}\right\rfloor + \left\lfloor\frac{909}{11 \cdot 101}\right\rfloor \right) = 82 - (27 + 0) = \bf{55}</math> values. | ||
+ | |||
+ | |||
+ | Case <math>D</math>: <math>3|x</math> and <math>11|x</math> (so <math>33|x</math>), but <math>101 \nmid x</math>. | ||
+ | |||
+ | Here, <math>abcd</math> is <math>99x</math>, so <math>x \leq \frac{9999}{99} = 101 </math>, | ||
+ | |||
+ | giving <math>\left\lfloor \frac{101}{33}\right\rfloor - \left\lfloor \frac{101}{33 \cdot 101}\right\rfloor = 3-0 = \bf{3}</math> values. | ||
+ | |||
+ | |||
+ | Case <math>E</math>: <math>101|x</math>. | ||
+ | |||
+ | Here, <math>abcd</math> is <math>101x</math>, so <math>x \leq \frac{9999}{101} = 99 </math>, | ||
+ | |||
+ | giving <math>\left\lfloor \frac{99}{101}\right\rfloor = \bf{0}</math> values, so we don't need to account for multiples of <math>3</math> and <math>11</math>. | ||
+ | |||
+ | To sum up, the answer is <cmath>6000+334+55+3+0\equiv\boxed{392} \pmod{1000}.</cmath> | ||
+ | |||
+ | ===Clarification=== | ||
+ | In this context, when the solution says, "Then <math>abcd=9x</math> to leave 3 uncancelled, and <math>x=3p</math>," it is a bit vague. The best way to clarify this is by this exact example - what is really meant is we need to divide by 9 first to achieve 1111, which has no multiple of 3; thus, given that the fraction x/y is the simplest form, x can be a multiple of 3. | ||
+ | |||
+ | Similar explanations can be said when the solution divides 9999 by 11, 101, and uses that divided result in the PIE calculation rather than 9999. | ||
+ | |||
+ | '''mathboy282''' | ||
+ | |||
+ | ==Solution 2 (similar''(?)'' to solution 1 but reworded (not ''exactly'' for clarity))== | ||
+ | |||
+ | <cmath>\text{To begin, we notice that all repeating decimals of the form }0.\overline{abcd}\text{ where }a,b,c,d\text{ are digits can be expressed of the form }\frac{\overline{abcd}}{9999}\text{.}</cmath> | ||
+ | <cmath>\text{However, when }\overline{abcd}\mid 9999\text{, the fraction is not in lowest terms.}</cmath> | ||
+ | <cmath>\text{Since }9999 = 3^2 \cdot 11 \cdot 101\text{, } x\mid 9999\iff x\mid 3\lor x\mid 11\lor x\mid 101\text{.}</cmath> | ||
+ | <cmath>\text{(For those of you who have no idea what that meant, it means every divisor of 9999 is a divisor of at least one of the following: )}</cmath> | ||
+ | <cmath>(3)</cmath> | ||
+ | <cmath>(11)</cmath> | ||
+ | <cmath>(101)</cmath> | ||
+ | <cmath>\text{(Also, I'm not going to give you explanations for the other logic equations.)}</cmath> | ||
+ | <cmath>\text{Let's say that the fraction in lowest terms is }\frac{x}{y}\text{.}</cmath> | ||
+ | <cmath>\text{If }x\mid 101\text{, then }99\mid y\text{ but that can't be, since }0\text{ is the only multiple of }101\text{ below }99\text{.}</cmath> | ||
+ | <cmath>\exists! f(f\in\mathbb{N}\land f\neq 1\land\exists g(g\nleq 0 \land x \mid f^g))\implies f=3\lor f=11 (1)</cmath> | ||
+ | <cmath>\text{If (1) is true, then we have two cases. If it isn't, we also have two cases.}</cmath> | ||
+ | <cmath>\textbf{\textit{Case 1: }}f=3</cmath> | ||
+ | <cmath>y=1111\land x=3z\implies 1\leq z\leq 370</cmath> | ||
+ | <cmath>370-33-3^{[1]}=334</cmath> | ||
+ | <cmath>\textbf{\textit{Case 2: }}f=11</cmath> | ||
+ | <cmath>y=909\land x=11z\implies 1\leq z\leq 82</cmath> | ||
+ | <cmath>82-27=55</cmath> | ||
+ | <cmath>\textbf{\textit{Case 3: }}\neg\exists! f(f\in\mathbb{N}\land f\neq 1\land\exists g(g\nleq 0 \land x \mid f^g))\land \exists f(f\in\mathbb{N}\land f\neq 1\land\exists g(g\nleq 0 \land x \mid f^g))=</cmath> | ||
+ | <cmath>\exists f_1(f_1\in\mathbb{N}\land f_1\neq 1\land\exists g_1(g_1\nleq 0 \land x \mid f_1^{g_1})\land\exists f_2(f_2\neq f_1\land f_2\in\mathbb{N}\land f_2\neq 1\land\exists g_2(g_2\nleq 0 \land x \mid f_2^{g_2}))\implies f_1=3\land f_2=11\lor f_1=11\land f_2=3</cmath> | ||
+ | <cmath>y=101\land x=33z\implies 1\leq z\leq 3</cmath> | ||
+ | <cmath>\textbf{\textit{Case 4: }}\neg\exists f(f\in\mathbb{N}\land f\neq 1\land\exists g(g\nleq 0 \land x \mid f^g))</cmath> | ||
+ | <cmath>\Phi (9999)=6000</cmath> | ||
+ | <cmath>\textbf{\textit{Grand Finale}}</cmath> | ||
+ | <cmath>\text{Adding the outcomes, }N=6000+334+55+3=6392\equiv\boxed{392}\text{ (mod 1000).}</cmath> | ||
+ | |||
+ | <cmath>\textit{[1] This is to make sure that 3 is the \textbf{only} factor of x}</cmath> | ||
+ | |||
+ | ===Note=== | ||
+ | |||
+ | <cmath>\text{When I tried to write LaTeX, AoPS kept putting the LaTeX on a new line so I gave up and put most of it in LaTeX instead.}</cmath> | ||
+ | <cmath>\text{Some of the text in this section is just normal.}</cmath> | ||
+ | <cmath>\text{Example:}</cmath> | ||
+ | |||
+ | Normal text <cmath>\text{This is some LaTeX.}</cmath> More normal text | ||
+ | |||
+ | <cmath>\text{If any of you can fix this issue, please do so.}</cmath> | ||
+ | |||
+ | ~ [[User:Afly|Afly]] ([[User talk:Afly|talk]]) | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/0FZyjuIOHnA | ||
+ | |||
+ | https://MathProblemSolvingSkills.com | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2022|n=I|num-b=12|num-a=14}} | {{AIME box|year=2022|n=I|num-b=12|num-a=14}} | ||
− | {{MAA Notice} | + | |
+ | [[Category:Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Revision as of 21:53, 2 January 2024
Contents
Problem
Let be the set of all rational numbers that can be expressed as a repeating decimal in the form
where at least one of the digits
or
is nonzero. Let
be the number of distinct numerators obtained when numbers in
are written as fractions in lowest terms. For example, both
and
are counted among the distinct numerators for numbers in
because
and
Find the remainder when
is divided by
Solution 1
,
.
Then we need to find the number of positive integers that (with one of more
such that
) can meet the requirement
.
Make cases by factors of . (A venn diagram of cases would be nice here.)
Case :
and
and
, aka
.
Euler's totient function counts these:
values (but it's enough to note that it's a multiple of 1000 and thus does not contribute to the final answer)
Note: You don't need to know this formula. The remaining cases essentially re-derive the same computation for other factors of . This case isn't actually different.
The remaining cases have (or
),
, and/or
as factors of
, which cancel out part of
.
Note: Take care about when to use
vs
.
Case :
, but
and
.
Then to leave 3 uncancelled, and
,
so
, giving:
,
,
,
for a subtotal of values.
Case :
, but
and
.
Much like previous case, is
, so
,
giving values.
Case :
and
(so
), but
.
Here, is
, so
,
giving values.
Case :
.
Here, is
, so
,
giving values, so we don't need to account for multiples of
and
.
To sum up, the answer is
Clarification
In this context, when the solution says, "Then to leave 3 uncancelled, and
," it is a bit vague. The best way to clarify this is by this exact example - what is really meant is we need to divide by 9 first to achieve 1111, which has no multiple of 3; thus, given that the fraction x/y is the simplest form, x can be a multiple of 3.
Similar explanations can be said when the solution divides 9999 by 11, 101, and uses that divided result in the PIE calculation rather than 9999.
mathboy282
Solution 2 (similar(?) to solution 1 but reworded (not exactly for clarity))
Note
Normal text More normal text
Video Solution
https://MathProblemSolvingSkills.com
See Also
2022 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
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.