2012 AIME II Problems/Problem 12
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.
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. 
