Ampoules

Énoncé

100 ampoules sont numérotées de 1 à 100 et ont chacune un interrupteur. Elles sont éteintes au début. 100 électriciens, numérotés eux aussi de 1 à 100, viennent faire des réparations. L'électricien numéro j appuie sur l'interrupteur des ampoules dont le numéro est un multiple de j : j, 2j, 3j... Combien d'ampoules sont allumées à la fin ?

Solution

L'ampoule numéro i est modifiée par chaque électricien ayant un numéro j qui divise i. Or, tout nombre entier qui n'est pas un carré a un nombre pair de diviseurs : en effet, si k est un diviseur de i alors i/k en est un autre, et les diviseurs peuvent ainsi être divisés en deux groupes de même taille. Ce raisonnement ne s'applique pas lorsque i=a², car alors a et i/a=a sont les mêmes nombres. Lorsque i n'est pas un carré, l'ampoule i est donc modifiée un nombre pair de fois et elle est éteinte à la fin. Lorsque i est un carré, elle est modifiée un nombre impair de fois et est allumée à la fin. Comme il y a 10 carrés entre 1 et 100 (1, 4, 9, 16, ..., 100), il y a 10 ampoules allumées à la fin.