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
visitante abre todas; o
fecha as de número múltiplo de 2; o
inverte o estado das múltiplas de 3, e assim por diante até o
. Precisamos usar o fato de que cada porta
é “visitada” em cada divisor de
e, ao final, identificar a maior porta que ficou fechada.
Passo 2
Observe que a porta de número
sofre uma troca de estado a cada visitante cujo número divide
. Logo, o total de trocas é exatamente o número de divisores de
, denotado por
.
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:
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:
Passo 3
Um resultado clássico de teoria dos números diz que
é ímpar exatamente quando
é um quadrado perfeito (pois divisores se emparelham, salvo o fator
quando
é quadrado). Portanto:
e as demais portas (não-quadrados) ficam fechadas.
Passo 4
Entre 1 e 100, o maior quadrado perfeito é
, que fica aberto. A maior porta que não é quadrado perfeito e, portanto, fica fechada é 99.
Resposta
99