Solucion del Problema Elemental # 26
====================================

(1 de junio, 2001, por Andr'es Garc'ia Sandoval, Licenciatura en
Matem'aticas, Universidad de Guadalajara, Revoluci'on 1500,
Guadalajara, Jal., M'exico, 44420. e-mail gigoloney@yahoo.com.)


Un sapo modifica el estado de un foco (lo prende o apaga) si
el n'umero del sapo es divisor del n'umero de foco. De esto se
desprende que los focos que quedan prendidos ser'an aquellos que
tengan un n'umero de divisores par.

Como un n'umero k tiene un numero par de divisores si y solo si k no
es un cuadrado perfecto (justificaci'on al final), el n'umero de focos
que quedan APAGADOS es el n'umero de cuadrados perfectos entre 1 y
1000.

Como 31^2 < 1000 < 32^2, existen 31 cuadrados perfectos entre 1 y 1000.

Conclusion: quedan 1000-31=969 focos prendidos. 

----------------------

Observaci'on: k es un cuadrado perfecto si y solo si su n'umero de
divisores es impar.


Demostracion: si k es primo, el resultado es trivial (2 divisores, 1 y
k). Si k no es primo entonces k es un producto de potencias de primos,
k=p^a q^b r^c ... (descomposicion can'onica, seg'un el teorema
fundamental de la aritm'etica). De esto se sigue que el n'umero de
divisores de k est'a dado por (a+1)(b+1)(c+1)..., y este n'umero es
impar si y solo si todas las potencias a,b,c,... son n'umeros pares.
Pero esta es claramente tambien la condici'on que k sea un cuadrado
perfecto (el cuadrado de p^(a/2) q^(b/2) r^(c/2) ... ).