Difference between revisions of "2012 AIME II Problems/Problem 12"
Firebolt360 (talk | contribs) (→Problem 12) |
|||
Line 15: | Line 15: | ||
This means that by the Chinese Remainder Theorem, <math>n</math> can have <math>2\cdot 6 \cdot 8 = 96</math> different residues mod <math>7 \cdot 11 \cdot 13 = 1001</math>. Thus, there are <math>960</math> values of <math>n</math> satisfying the conditions in the range <math>0 \le n < 10010</math>. However, we must now remove any values greater than <math>10000</math> that satisfy the conditions. By checking residues, we easily see that the only such values are <math>10006</math> and <math>10007</math>, so there remain <math>\fbox{958}</math> values satisfying the conditions of the problem. | This means that by the Chinese Remainder Theorem, <math>n</math> can have <math>2\cdot 6 \cdot 8 = 96</math> different residues mod <math>7 \cdot 11 \cdot 13 = 1001</math>. Thus, there are <math>960</math> values of <math>n</math> satisfying the conditions in the range <math>0 \le n < 10010</math>. However, we must now remove any values greater than <math>10000</math> that satisfy the conditions. By checking residues, we easily see that the only such values are <math>10006</math> and <math>10007</math>, so there remain <math>\fbox{958}</math> values satisfying the conditions of the problem. | ||
+ | |||
+ | |||
+ | === Solution 2 (Probability)=== | ||
+ | Note that <math>\operatorname{lcm}(7, 11, 13)=1001</math> and <math>10000=1001\cdot10-10</math>. Now, consider any positive integer <math>n</math> such that <math>1\le n\le 10010</math>. Since all <math>7</math>-safe numbers are of the form <math>7k+3</math> or <math>7k+4</math>, the probability that <math>n</math> is <math>7</math>-safe is <math>\frac{2}{7}</math>. Similarly, the probability that <math>n</math> is <math>11</math>-safe is <math>\frac{6}{11}</math> and the probability that <math>n</math> is <math>13</math>-safe is <math>\frac{8}{13}</math>. Furthermore, since <math>7, 11, \text{ and } 13</math> are all relatively prime, <math>n</math> being <math>7</math>-safe, <math>11</math>-safe, and <math>13</math>-safe are all independent events. Thus, the number of positive integers less then or equal to <math>10010</math> which are simultaneously <math>7</math>-safe, <math>11</math>-safe, and <math>13</math>-safe is <math>10010\left(\frac{2}{7}\right)\left(\frac{6}{11}\right)\left(\frac{8}{13}\right)=960</math>. However, the problem asks for numbers less than or equal to <math>10000</math>, so we must subtract any numbers we counted which are greater than <math>10000</math>. This is easy; we can see that <math>10006</math> and <math>10007</math> were counted, so the answer is <math>960-2=\boxed{958}</math>. | ||
+ | -brainiacmaniac31 | ||
== See Also == | == See Also == | ||
{{AIME box|year=2012|n=II|num-b=11|num-a=13}} | {{AIME box|year=2012|n=II|num-b=11|num-a=13}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 15:19, 3 June 2020
Problem 12
For a positive integer , define the positive integer to be -safe if differs in absolute value by more than from all multiples of . For example, the set of -safe numbers is . Find the number of positive integers less than or equal to which are simultaneously -safe, -safe, and -safe.
Solution
We see that a number is -safe if and only if the residue of is greater than and less than ; thus, there are residues that a -safe number can have. Therefore, a number satisfying the conditions of the problem can have different residues , different residues , and different residues . The Chinese Remainder Theorem states that for a number that is (mod b) (mod d) (mod f) has one solution if . For example, in our case, the number can be: 3 (mod 7) 3 (mod 11) 7 (mod 13) so since =1, there is 1 solution for n for this case of residues of .
This means that by the Chinese Remainder Theorem, can have different residues mod . Thus, there are values of satisfying the conditions in the range . However, we must now remove any values greater than that satisfy the conditions. By checking residues, we easily see that the only such values are and , so there remain values satisfying the conditions of the problem.
Solution 2 (Probability)
Note that and . Now, consider any positive integer such that . Since all -safe numbers are of the form or , the probability that is -safe is . Similarly, the probability that is -safe is and the probability that is -safe is . Furthermore, since are all relatively prime, being -safe, -safe, and -safe are all independent events. Thus, the number of positive integers less then or equal to which are simultaneously -safe, -safe, and -safe is . However, the problem asks for numbers less than or equal to , so we must subtract any numbers we counted which are greater than . This is easy; we can see that and were counted, so the answer is . -brainiacmaniac31
See Also
2012 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 11 |
Followed by Problem 13 | |
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.