Análise combinatória

Relembrando a primeira mensagem :

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 4, 12 , ..., 900 abrindo os que encontra fechados e fechando os que encontra abertos. Ao final quais armários ficarão abertos?

Olá:

Aí vai uma sugestão de resolução:Para que o armário com o número n fique aberto é necessário e suficiente que n tenha um número ímpar de divisores. Por exemplo, n=4 tem três divisores: 1, 2 e 4.Como inicialmente o armário estava fechado, a pessoa com o número 1 abre esse armário, a pessoa com o número 2 fecha-o e a pessoa com o número 4 abre-o de novo.Se n tivesse um nº par de divisores, ficaria fechado. Por exemplo n=6. Os divisores são 1,2,3 e 6. A pessoa 1 abre-o; a pessoa 2 fecha-o; a pessoa 3 abre-o e a pessoa 6 fecha-o. Portanto o armário 6 fica fechado.

Ora, sabe-se que o número de divisores de um número n, decomposto em fatores na forma n=(p1)^a1.(p2)^a2....(pn)^an é igual a (a1+1)(a2+1)...(an+1). Ora este número só é ímpar se a1,a2,...,an forem todos pares. Logo, se os expoentes dos fatores primos de n são todos pares, então n é um quadrado perfeito. Ou seja, um número n tem um número ímpar de divisores se e só se n for um quadrado perfeito.

Logo, no final só ficam abertos 30 armários (1,4,9,16,....,900).