Solucione os problemas a seguir:
a) Os inteiros de 1 a 1000 são escritos ordenadamente em torno de um círculo. Partindo de 1 , riscamos os números de 15 em 15 , isto é, riscamos 1,16,31, \ldots O processo continua até se atingir um número já previamente riscado. Quantos números sobram sem riscos ?

Passo 1

O enunciado dá as seguintes informações:
  • Estão escritos em volta de um círculo os inteiros de 1 a 1000.
  • Partindo de 1, riscamos os números de 15 em 15, isto é, a sequência de números riscados começa por 1,16,31,\ldots.
  • O processo continua ciclicamente até que se atinja um número já previamente riscado.
O que o problema pede:
  • Determinar quantos números SOBRAM sem riscos (ou seja, quantos dos inteiros de 1 a 1000 não são riscados por esse procedimento).

Passo 2

Vamos modelar a sequência dos números riscados de forma matemática. Se chamarmos de a_k o k-ésimo número riscado (com a_0=1), então:
a_k = 1 + 15k \pmod{1000},
isto é, consideramos os restos módulo 1000. Isso acontece porque ao andar de 15 em 15 ao redor do círculo, estamos somando 15 e reduzindo módulo 1000.

Passo 3

A sequência vai produzir números distintos até o primeiro n>0 tal que a_n=a_0 (ou seja, até voltar ao 1 inicial). A condição a_n=a_0 é:
1 + 15n \equiv 1 \pmod{1000},
que equivale a
15n \equiv 0 \pmod{1000}.
Portanto o número de termos distintos riscados é exatamente o menor inteiro positivo n que satisfaz 15n múltiplo de 1000.

Passo 4

Uma observação de teoria (explicando por que isto é verdade): para inteiros a e m, os termos x_k=x_0+ak\pmod{m} percorrem exatamente \dfrac{m}{\gcd(a,m)} resíduos distintos antes de se repetir. Intuição: os incrementos a geram um subgrupo cíclico do grupo aditivo dos restos módulo m cujo tamanho é m/\gcd(a,m). Assim o menor n>0 com an\equiv0\pmod{m} é n=m/\gcd(a,m).
Aplicando com a=15 e m=1000, o número de termos riscados é
n=\frac{1000}{\gcd(15,1000)}.

Passo 5

Vamos calcular \gcd(15,1000) usando o Algoritmo de Euclides, passo a passo:
1000 = 15\cdot66 + 10,
15 = 10\cdot1 + 5,
10 = 5\cdot2 + 0.
Como o resto final não nulo é 5, segue que \gcd(15,1000)=5.

Passo 6

Substituindo em n=\dfrac{1000}{\gcd(15,1000)}, obtemos:
n=\frac{1000}{5}=200.
Logo são riscados exatamente 200 números distintos antes de a sequência voltar a um número já riscado.

Passo 7

O total de números escritos é 1000. Assim o número de inteiros que SOBRAM sem riscos é
1000-200=800.

Resposta

800

Exercícios relacionados