- Em um corredor há 900 armários, numerados de 1 a 900 , inicialmente, todos fechados. 900 pessoas, numeradas de 1 a 900 , atravessam o corredor. A pessoa de número
reverte o estado de todos os armários cujos números são múltiplos de
. Por exemplo, a pessoa de número 4 mexe nos armários de números
, abrindo os que encontra fechados e fechando os que encontra abertos. Ao final, quais armários ficarão abertos?
Passo 1
O enunciado diz que há
armários numerados de
a
, todos inicialmente fechados. Em seguida, passam
pessoas numeradas de
a
. A pessoa de número
“inverte” (abre se fechado, fecha se aberto) todos os armários cujos números são múltiplos de
. A pergunta é: ao final de todas as
pessoas, quais armários ficarão abertos?
Informações relevantes dadas:
- Há
armários, numerados de a . - Todos começam fechados.
- Para cada
, a pessoa inverte o estado de todos os armários cujos números são múltiplos de . - Precisamos indicar exatamente quais armários estarão abertos no fim.
Passo 2
Observação-chave: cada armário de número
é invertido exatamente uma vez para cada divisor positivo
de
.
Explicação: se divide
, então a pessoa
touchará o armário
(pois
é múltiplo de
). Não há outra forma de alguém alterar o armário
salvo quando o seu número é divisor de
. Logo, o número total de inversões que o armário
sofre é igual ao número de divisores positivos de
. Denotando por
a quantidade de divisores de
, o armário
é invertido
vezes.
Explicação: se
Passo 3
Relação entre número de inversões e estado final: como todos começam fechados, se um armário é invertido um número par de vezes ele volta a ficar fechado; se é invertido um número ímpar de vezes ele ficará aberto. Portanto:
-
ficará aberto ao final se, e somente se, for ímpar. -
ficará fechado ao final se, e somente se, for par.
Passo 4
Caracterização de quando
é ímpar: os divisores de
normalmente vêm em pares
. Por exemplo, para
temos os pares
— três pares, total
, par. A única situação em que um divisor “fica sozinho” (ou seja, não forma um par com um divisor distinto) é quando
, isto é, quando
. Isso só acontece se
for inteiro, ou seja, quando
é um quadrado perfeito. Conclusão:
-
é ímpar se, e somente se, for um quadrado perfeito.
Passo 5
Aplicando ao nosso problema: os armários que ficarão abertos são exatamente aqueles cujos números são quadrados perfeitos menores ou iguais a
. Precisamos, então, listar todos os quadrados perfeitos
com
inteiro positivo e
.
Passo 6
Calcular a maior raiz inteira cujo quadrado não ultrapassa
:
. Logo os quadrados perfeitos entre
e
são exatamente
.
Passo 7
Escrever a lista explícita dos quadrados perfeitos de
a
:
Portanto há
armários abertos ao final, exatamente estes listados acima.