Question

Para un entero positivo $p,$ se dice que el entero positivo $n$ es $p$ -seguro si $n$ difiere en valor absoluto en más de $2$ de todos los múltiplos de $p.$ Por ejemplo, el conjunto de números $10$ -seguros es $\{3, 4, 5, 6, 7, 13, 14, 15,$ $16, 17, 23, \ldots\}.$ Halle el número de enteros positivos menores o iguales que $10{,}000$ que son simultáneamente $7$ -seguros, $11$ -seguros y $13$ -seguros.

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.

Respuesta

Solución:

Ser $p$ -seguro depende solo de $n \bmod p:$ requiere $3 \le n \bmod p \le p - 3.$ Eso permite $2$ residuos módulo $7,$ $6$ residuos módulo $11,$ y $8$ residuos módulo $13.$ Como $7 \cdot 11 \cdot 13 = 1001,$ el teorema chino del resto da exactamente $2 \cdot 6 \cdot 8 = 96$ residuos seguros módulo $1001,$ así que cada bloque de $1001$ enteros consecutivos contiene $96$ números seguros.

Los enteros del $1$ al $10010$ forman diez de esos bloques, con $960$ números seguros. Queda descartar los números seguros entre $10001, \ldots, 10010.$ Sus residuos módulo $7$ son $5, 6, 0, 1, 2, 3, 4, 5, 6, 0,$ así que solo $10006$ y $10007$ son $7$ -seguros; ambos son también $11$ -seguros (residuos $7$ y $8$ ) y $13$ -seguros (residuos $9$ y $10$ ).

Por lo tanto el conteo es $960 - 2 = 958.$

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 Problema 12

Solución:

El Problema 12 en otros años