Matheux qui s'amusent le soir...

[Zebulon]

Bonjour à tous, ce matin je suis d'humeur à vous proposer une petite énigme...

n mathématiciens se rendent à un congrès. Le soir, ils logent tous dans le même hôtel, dans le même couloir et leur porte (ainsi que leur badge) porte un numéro de 1 à n. La porte et le badge de chaque mathématicien porte le même numéro.

Comme ils s'ennuient, chacun à son tour, ils vont passer dans le couloir et "changer l'état de chaque porte" si et seulement si le numéro de la porte est un multiple du numéro du badge du matheux. J'entends par "changer l'état de la porte" l'ouvrir si elle est fermée et la fermer si elle est ouverte.
Avant le passage du matheux numéro 1, toutes les portes sont fermées.

Ainsi, le mathématicien numéro 1 ouvre toutes les portes, le numéro 2 ferme les portes de numéro pair, le mathématicien numéro 3 ferme la porte numéro 3, ouvre la porte numéro 6, ferme la porte numéro 9, etc...
On demande : combien de portes se retrouvent-elles ouvertes après le passage des n mathématiciens?

Bon courage à ceux qui chercheront!

[scelerat]

Partie entiere de racine de n ?

[Zebulon]

Oui, c'est ça. Comment le prouves-tu?

[scelerat]

Oui, c'est ça. Comment le prouves-tu?

Pour la porte i, je regarde les decompositions de i sous la forme j*k, avec j inferieur ou egal a k. Les effets des matheux j et k sur la porte i s'annulent deux a deux, sauf evidemment si j et k ne font qu'un, j=k. Les portes qui resteront ouvertes sont donc celles dont le numero i est un carre parfait j*j, et il y en a partie entiere de racine de n entre 1 et n.