Difference between revisions of "2012 AIME II Problems/Problem 12"
Williamhu888 (talk | contribs) (Created page with "== Problem 12 == For a positive integer <math>p</math>, define the positive integer <math>n</math> to be <math>p</math>''-safe'' if <math>n</math> differs in absolute value by mo...") |
(→Solution) |
||
(21 intermediate revisions by 16 users not shown) | |||
Line 1: | Line 1: | ||
== Problem 12 == | == Problem 12 == | ||
For a positive integer <math>p</math>, define the positive integer <math>n</math> to be <math>p</math>''-safe'' if <math>n</math> differs in absolute value by more than <math>2</math> from all multiples of <math>p</math>. For example, the set of <math>10</math>-safe numbers is <math>\{ 3, 4, 5, 6, 7, 13, 14, 15, 16, 17, 23, \ldots\}</math>. Find the number of positive integers less than or equal to <math>10,000</math> which are simultaneously <math>7</math>-safe, <math>11</math>-safe, and <math>13</math>-safe. | For a positive integer <math>p</math>, define the positive integer <math>n</math> to be <math>p</math>''-safe'' if <math>n</math> differs in absolute value by more than <math>2</math> from all multiples of <math>p</math>. For example, the set of <math>10</math>-safe numbers is <math>\{ 3, 4, 5, 6, 7, 13, 14, 15, 16, 17, 23, \ldots\}</math>. Find the number of positive integers less than or equal to <math>10,000</math> which are simultaneously <math>7</math>-safe, <math>11</math>-safe, and <math>13</math>-safe. | ||
+ | |||
+ | == Solution == | ||
+ | |||
+ | We see that a number <math>n</math> is <math>p</math>-safe if and only if the residue of <math>n \mod p</math> is greater than <math>2</math> and less than <math>p-2</math>; thus, there are <math>p-5</math> residues <math>\mod p</math> that a <math>p</math>-safe number can have. Therefore, a number <math>n</math> satisfying the conditions of the problem can have <math>2</math> different residues <math>\mod 7</math>, <math>6</math> different residues <math>\mod 11</math>, and <math>8</math> different residues <math>\mod 13</math>. The Chinese Remainder Theorem states that for a number <math>x</math> that is | ||
+ | <math>a</math> (mod b) | ||
+ | <math>c</math> (mod d) | ||
+ | <math>e</math> (mod f) | ||
+ | has one solution if <math>\gcd(b,d,f)=1</math>. For example, in our case, the number <math>n</math> can be: | ||
+ | 3 (mod 7) | ||
+ | 3 (mod 11) | ||
+ | 7 (mod 13) | ||
+ | so since <math>\gcd(7,11,13)</math>=1, there is 1 solution for n for this case of residues of <math>n</math>. | ||
+ | |||
+ | 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 < n \le 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. | ||
+ | |||
+ | |||
+ | *We can also say <math>\frac{2}{7}</math> of all numbers are 7-safe, <math>\frac{6}{11}</math> of all numbers are 11-safe, and <math>\frac{8}{13}</math> of all numbers are 13-safe. We can multiply these to get that <math>\frac{96}{1001}</math> of all numbers are simultaneously 7-safe, 11-safe, and 13-safe. | ||
+ | |||
+ | == See Also == | ||
+ | {{AIME box|year=2012|n=II|num-b=11|num-a=13}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 12:52, 12 June 2024
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.
- We can also say
of all numbers are 7-safe,
of all numbers are 11-safe, and
of all numbers are 13-safe. We can multiply these to get that
of all numbers are simultaneously 7-safe, 11-safe, and 13-safe.
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.