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
O processo continua até se atingir um número já previamente riscado. Quantos números sobram sem riscos ?
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
Passo 1
O enunciado dá as seguintes informações:
- Estão escritos em volta de um círculo os inteiros de
a . - Partindo de
, riscamos os números de em , isto é, a sequência de números riscados começa por . - 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
a 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
o
-ésimo número riscado (com
), então:
isto é, consideramos os restos módulo
. Isso acontece porque ao andar de
em
ao redor do círculo, estamos somando
e reduzindo módulo
.
Passo 3
A sequência vai produzir números distintos até o primeiro
tal que
(ou seja, até voltar ao
inicial). A condição
é:
que equivale a
Portanto o número de termos distintos riscados é exatamente o menor inteiro positivo
que satisfaz
múltiplo de
.
Passo 4
Uma observação de teoria (explicando por que isto é verdade): para inteiros
e
, os termos
percorrem exatamente
resíduos distintos antes de se repetir. Intuição: os incrementos
geram um subgrupo cíclico do grupo aditivo dos restos módulo
cujo tamanho é
. Assim o menor
com
é
.
Aplicando com
e
, o número de termos riscados é
Passo 5
Vamos calcular
usando o Algoritmo de Euclides, passo a passo:
Como o resto final não nulo é
, segue que
.
Passo 6
Substituindo em
, obtemos:
Logo são riscados exatamente
números distintos antes de a sequência voltar a um número já riscado.
Passo 7
O total de números escritos é
. Assim o número de inteiros que SOBRAM sem riscos é
Resposta
800