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.

答案

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

Solution:

Problem 12 in Other Years