Numa escola, ao longo de um corredor comprido estão enfileirados 50 armários numerados consecutivamente de 1 a 50 com suas portas fechadas. 50 alunos da Escola também numerados de 1 a 50 resolvem fazer a seguinte brincadeira: o aluno número 1 passa pelo corredor e abre todos os armários; em seguida, o aluno número 2 passa e fecha todos os armários de número par; depois passa o aluno de número 3 e inverte a posição das portas de todos os armários múltiplos de 3 , isto é, ele os fecha se eles estiverem abertos e os abre se eles estiverem fechados; depois é a vez do aluno número 4 que inverte a posição das portas dos armários múltiplos de 4 e assim sucessivamente. O quinquagésimo aluno inverteu a posição do quinquagésimo (e último) armário. Quais armários ficaram abertos?
Passo 1
O enunciado dá as seguintes informações (vou listar com calma para não confundir):
- Existem
armários dispostos e numerados de a . - Inicialmente todos os armários estão com as portas fechadas.
- Passam
alunos, numerados a . O aluno de número percorre o corredor e inverte a posição (fecha se estiver aberto, abre se estiver fechado) de todo armário cujo número seja múltiplo de . - Depois do aluno
o processo termina. A pergunta é: quais armários ficaram abertos no final?
Passo 2
Vamos focar em um armário genérico, cujo número seja
(com
). Cada vez que um aluno de número
passa, ele inverte a porta do armário
exatamente quando
divide
, ou seja, quando
é um divisor de
.
Portanto, o número de vezes que o armário é invertido (ou seja, o número de “toggles”) é exatamente o número de divisores positivos de
. Denotemos esse número por
(ou seja,
= quantidade de divisores de
).
Portanto, o número de vezes que o armário
Passo 3
Relembre a consequência prática do número de inversões para o estado final:
- Como o armário começa fechado, se ele for invertido um número par de vezes ficará fechado no final.
- Se for invertido um número ímpar de vezes ficará aberto no final.
Logo, o armário
ficará aberto exatamente quando
for ímpar.
Passo 4
Agora uma propriedade importante sobre divisores: os divisores de
aparecem em pares do tipo
tal que
. Para cada divisor
distinto existe o divisor
. Assim, quando os divisores aparecem sempre em pares distintos,
é par. A única situação em que um divisor não tem par distinto é quando
, isto é, quando
. Isso acontece exatamente quando
é um quadrado perfeito.
Conclusão lógica:
é ímpar se, e só se,
for um quadrado perfeito. Portanto, os armários que ficam abertos são exatamente aqueles cujo número é um quadrado perfeito.
Passo 5
Basta listar os quadrados perfeitos menores ou iguais a
. São:
Note que
, então paramos em
.
Como checagem rápida: por exemplo, o armário
tem divisores
(seis divisores, par) e portanto fica fechado; já o armário
tem divisores
(nove divisores, ímpar) e portanto fica aberto. Isso confirma a regra prática.