Difference between revisions of "2022 AIME I Problems/Problem 13"
m (→Solution: added some detail and clarification) |
(→Solution) |
||
Line 17: | Line 17: | ||
Euler's totient function counts these: | 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). | + | <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>. | 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>. |
Revision as of 20:06, 20 December 2023
Contents
[hide]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
, .
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
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.