1. 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 k reverte o estado de todos os armários cujos números são múltiplos de k. Por exemplo, a pessoa de número 4 mexe nos armários de números 4,8,12, \ldots, 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á 900 armários numerados de 1 a 900, todos inicialmente fechados. Em seguida, passam 900 pessoas numeradas de 1 a 900. A pessoa de número k “inverte” (abre se fechado, fecha se aberto) todos os armários cujos números são múltiplos de k. A pergunta é: ao final de todas as 900 pessoas, quais armários ficarão abertos?
Informações relevantes dadas:
  • 900 armários, numerados de 1 a 900.
  • Todos começam fechados.
  • Para cada k\in\{1,\dots,900\}, a pessoa k inverte o estado de todos os armários cujos números são múltiplos de k.
  • Precisamos indicar exatamente quais armários estarão abertos no fim.

Passo 2

Observação-chave: cada armário de número n é invertido exatamente uma vez para cada divisor positivo d de n.
Explicação: se d divide n, então a pessoa d touchará o armário n (pois n é múltiplo de d). Não há outra forma de alguém alterar o armário n salvo quando o seu número é divisor de n. Logo, o número total de inversões que o armário n sofre é igual ao número de divisores positivos de n. Denotando por \tau(n) a quantidade de divisores de n, o armário n é invertido \tau(n) vezes.

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:
  • n ficará aberto ao final se, e somente se, \tau(n) for ímpar.
  • n ficará fechado ao final se, e somente se, \tau(n) for par.

Passo 4

Caracterização de quando \tau(n) é ímpar: os divisores de n normalmente vêm em pares (d,\,n/d). Por exemplo, para n=12 temos os pares (1,12),(2,6),(3,4) — três pares, total \tau(12)=6, par. A única situação em que um divisor “fica sozinho” (ou seja, não forma um par com um divisor distinto) é quando d = n/d, isto é, quando d = \sqrt{n}. Isso só acontece se \sqrt{n} for inteiro, ou seja, quando n é um quadrado perfeito. Conclusão:
  • \tau(n) é ímpar se, e somente se, n 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 900. Precisamos, então, listar todos os quadrados perfeitos m^2 com m inteiro positivo e m^2\le 900.

Passo 6

Calcular a maior raiz inteira cujo quadrado não ultrapassa 900: \sqrt{900}=30. Logo os quadrados perfeitos entre 1 e 900 são exatamente 1^2,2^2,\dots,30^2.

Passo 7

Escrever a lista explícita dos quadrados perfeitos de 1 a 30:
1^2=1,\;2^2=4,\;3^2=9,\;4^2=16,\;5^2=25,\;6^2=36,\;7^2=49,\;8^2=64,\;9^2=81,\;10^2=100,
11^2=121,\;12^2=144,\;13^2=169,\;14^2=196,\;15^2=225,\;16^2=256,\;17^2=289,\;18^2=324,\;19^2=361,\;20^2=400,
21^2=441,\;22^2=484,\;23^2=529,\;24^2=576,\;25^2=625,\;26^2=676,\;27^2=729,\;28^2=784,\;29^2=841,\;30^2=900.
Portanto há 30 armários abertos ao final, exatamente estes listados acima.

Resposta

1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900

Exercícios relacionados