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 50 armários dispostos e numerados de 1 a 50.
  • Inicialmente todos os armários estão com as portas fechadas.
  • Passam 50 alunos, numerados 1 a 50. O aluno de número k 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 k.
  • Depois do aluno 50 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 n (com 1\le n\le50). Cada vez que um aluno de número k passa, ele inverte a porta do armário n exatamente quando k divide n, ou seja, quando k é um divisor de n.
Portanto, o número de vezes que o armário n é invertido (ou seja, o número de “toggles”) é exatamente o número de divisores positivos de n. Denotemos esse número por \tau(n) (ou seja, \tau(n) = quantidade de divisores de n).

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 n ficará aberto exatamente quando \tau(n) for ímpar.

Passo 4

Agora uma propriedade importante sobre divisores: os divisores de n aparecem em pares do tipo (a,b) tal que a\cdot b=n. Para cada divisor a distinto existe o divisor b=n/a. Assim, quando os divisores aparecem sempre em pares distintos, \tau(n) é par. A única situação em que um divisor não tem par distinto é quando a=b, isto é, quando a^2=n. Isso acontece exatamente quando n é um quadrado perfeito.
Conclusão lógica: \tau(n) é ímpar se, e só se, n 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 50. São:
1^2=1,\;2^2=4,\;3^2=9,\;4^2=16,\;5^2=25,\;6^2=36,\;7^2=49.
Note que 8^2=64>50, então paramos em 7^2.
Como checagem rápida: por exemplo, o armário 12 tem divisores 1,2,3,4,6,12 (seis divisores, par) e portanto fica fechado; já o armário 36 tem divisores 1,2,3,4,6,9,12,18,36 (nove divisores, ímpar) e portanto fica aberto. Isso confirma a regra prática.

Resposta

1, 4, 9, 16, 25, 36, 49

Exercícios relacionados