2012 AIME II Problem 12

Question

For a positive integer

p,

define the positive integer

n

to be

p

-safe if

n

differs in absolute value by more than

2

from all multiples of

p.

For example, the set of

10

-safe numbers is

\{3,

4,

5,

6,

7,

13,

14,

15,

16,

17,

23,

\ldots\}.

Find the number of positive integers less than or equal to

10{,}000

which are simultaneously

7

-safe,

11

-safe, and

13

-safe.

Answer

Answer: 958

Concepts:modular arithmetic Chinese Remainder Theorem

Difficulty rating: 2920

Small hint:

n

is

p

-safe exactly when

3 \le n \bmod p \le p - 3

Big hint:

Since

7 \cdot 11 \cdot 13 = 1001,

count the safe residues in each block of

1001

consecutive integers, then adjust near the cutoff

10{,}000

Solution:

Being

p

-safe depends only on

n \bmod p:

it requires

3 \le n \bmod p \le p - 3.

That allows

2

residues modulo

7,

6

residues modulo

11,

and

8

residues modulo

13.

Since

7 \cdot 11 \cdot 13 = 1001,

the Chinese remainder theorem gives exactly

2 \cdot 6 \cdot 8 = 96

safe residues modulo

1001,

so each block of

1001

consecutive integers contains

96

safe numbers.

The integers

1

through

10010

form ten such blocks, containing

960

safe numbers. It remains to discard the safe numbers among

10001, \ldots, 10010.

Their residues modulo

7

run

5, 6, 0, 1, 2, 3, 4, 5, 6, 0,

so only

10006

and

10007

are

7

-safe; both are also

11

-safe (residues

7

and

8

) and

13

-safe (residues

9

and

10

).

Therefore the count is

960 - 2 = 958.

2012 AIME II Problem 12

Answer: 958

Difficulty rating: 2920

Small hint:

Big hint:

Solution:

Problem 12 in other years