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.
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.