Difference between revisions of "2012 AIME II Problems/Problem 12"
m (→Solution 2 (Probability)) |
|||
Line 18: | Line 18: | ||
=== Solution 2 (Probability)=== | === 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 | + | 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 overcounted, so the answer is <math>960-2=\boxed{958}</math>. |
+ | |||
-brainiacmaniac31 | -brainiacmaniac31 | ||
Revision as of 16:20, 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 overcounted, 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.