100 pessoas passam, um a um, por 100 armários numerados de 1 a 100 , originalmente fechados. O primeiro abre todas as portas, o segundo fecha todas as portas cujos números são múltiplos de 2 , o terceiro muda o status das portas de números múltiplos de 3 (isto é, abre as que estiverem fechadas e fecha as que estiverem abertas), e assim por diante. Ao fim do processo, qual é a porta de maior número que está fechada?

Passo 1

O enunciado descreve 100 portas numeradas de 1 a 100, todas inicialmente fechadas. O 1^\circ visitante abre todas; o 2^\circ fecha as de número múltiplo de 2; o 3^\circ inverte o estado das múltiplas de 3, e assim por diante até o 100^\circ. Precisamos usar o fato de que cada porta n é “visitada” em cada divisor de n e, ao final, identificar a maior porta que ficou fechada.

Passo 2

Observe que a porta de número n sofre uma troca de estado a cada visitante cujo número divide n. Logo, o total de trocas é exatamente o número de divisores de n, denotado por d(n).
Como toda porta começa fechada, ela termina aberta se for trocada um número ímpar de vezes e termina fechada se o número de trocas for par. Assim:
\text{porta \(n\) está aberta} \iff d(n)\text{ é ímpar},áéí
\text{porta \(n\) está fechada} \iff d(n)\text{ é par}.áé

Passo 3

Um resultado clássico de teoria dos números diz que d(n) é ímpar exatamente quando n é um quadrado perfeito (pois divisores se emparelham, salvo o fator \sqrt{n} quando n é quadrado). Portanto:
\text{portas abertas} = \{\,k^2 \mid k\in\mathbb{N},\,k^2\le100\},
e as demais portas (não-quadrados) ficam fechadas.

Passo 4

Entre 1 e 100, o maior quadrado perfeito é 100=10^2, que fica aberto. A maior porta que não é quadrado perfeito e, portanto, fica fechada é 99.

Resposta

99

Exercícios relacionados