Difference between revisions of "2012 AIME II Problems/Problem 12"
m |
|||
| Line 7: | Line 7: | ||
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>. 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>10007</math> and <math>10006</math>, so there remain <math>\fbox{958}</math> values satisfying the conditions of the problem. | 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>. 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>10007</math> and <math>10006</math>, so there remain <math>\fbox{958}</math> values satisfying the conditions of the problem. | ||
| − | == See | + | == 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}} | ||
Revision as of 15:45, 3 April 2012
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 
. 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.
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 | ||
