Difference between revisions of "2022 AIME I Problems/Problem 13"
(→Solution1) |
MRENTHUSIASM (talk | contribs) m (→Solution) |
||
(14 intermediate revisions by 11 users not shown) | |||
Line 3: | Line 3: | ||
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 | + | ==Solution== |
− | <math>0.abcd=\frac | + | <math>0.\overline{abcd}=\frac{abcd}{9999}</math>, <math>9999=9\times 11\times 101</math>. |
− | Then we need to find the number of positive integers less than 10000 can meet the requirement.Suppose the number is x. | + | Then we need to find the number of positive integers less than <math>10000</math> that can meet the requirement. Suppose the number is <math>x</math>. |
− | Case 1: (9999, x)=1. Clearly x satisfies | + | Case <math>1</math>: <math>\gcd (9999, x)=1</math>. Clearly, <math>x</math> satisfies the condition yielding <cmath>\varphi \left( 9999 \right) =9999\times \left( 1-\frac{1}{3} \right) \times \left( 1-\frac{1}{11} \right) \times \left( 1-\frac{1}{101} \right)=6000</cmath> values. |
− | Case 2: 3|x but x is not a multiple of 11 or 101. Then the least value of abcd is 9x, so that <math>x\le 1111</math>, 334 values from 3 to 1110. | + | Case <math>2</math>: <math>3|x</math> but <math>x</math> is not a multiple of <math>11</math> or <math>101.</math> Then the least value of <math>abcd</math> is <math>9x</math>, so that <math>x\le 1111</math>, <math>334</math> values from <math>3</math> to <math>1110.</math> |
− | Case 3: 11|x but x is not a multiple of 3 or 101. Then the least value of abcd is 11x, so that <math>x\le 909</math>, 55 values from 11 to 902. | + | Case <math>3</math>: <math>11|x</math> but <math>x</math> is not a multiple of <math>3</math> or <math>101</math>. Then the least value of <math>abcd</math> is <math>11x</math>, so that <math>x\le 909</math>, <math>55</math> values from <math>11</math> to <math>902</math>. |
− | Case 4: 101|x. None. | + | Case <math>4</math>: <math>101|x</math>. None. |
− | Case 5: 3, 11|x. Then the least value of abcd is | + | Case <math>5</math>: <math>3, 11|x</math>. Then the least value of <math>abcd</math> is <math>99x</math>, <math>3</math> values from <math>33</math> to <math>99.</math> |
− | To sum up, | + | To sum up, the answer is <cmath>6000+334+55+3\equiv\boxed{392} \pmod{1000}.</cmath> |
+ | |||
+ | ==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}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 20:54, 16 January 2023
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
, .
Then we need to find the number of positive integers less than that can meet the requirement. Suppose the number is .
Case : . Clearly, satisfies the condition yielding values.
Case : but is not a multiple of or Then the least value of is , so that , values from to
Case : but is not a multiple of or . Then the least value of is , so that , values from to .
Case : . None.
Case : . Then the least value of is , values from to
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.