Un hôtel qui ne concurrence pas l'hôtel de Hilbert...

Un hôtel à 1000 chambres numérotées de 1 à 1000 a besoin d’entretien. Le premier concierge, après son ménage, s’assure que toutes les portes soient fermées. Le second concierge a la charge d’une chambre sur deux. Il ouvre la porte 2, la porte 4, la porte 6, et ainsi de suite. Le troisième a la charge d’une chambre sur trois. Il change l’état de la porte 3, 6, 9… c’est-à-dire qu’il ouvre les portes fermées et ferme les portes ouvertes. Le quatrième concierge et tous les autres agissent de la même façon avec une porte sur quatre, une porte sur cinq, une porte sur six…

Quelles portes seront fermées après que le millième concierge aura complété sa ronde de ménage?

I solved itMark it done Add to my listKeep it in your list

I like this problem1 like

Liked by

Catalpa@catalpa

Solutions

Reveal solutionsAre you sure? Give it a try first.

Solution by araucaria araucana

Discussions0 useful votes

Sans perte de généralité, on supposera que les portes étaient toutes ouvertes avant le premier concierge.
Une porte $n$ change d’état précisément lorsque le $d$ -ième concierge fait sa ronde, pour $d \mid n$ . De plus, une porte est fermée quand elle change d’état un nombre impair de fois (puisqu’elle était ouverte initialement). Ainsi, les portes qui seront fermées sont celles qui possèdent un nombre impair de diviseurs.
Si $(e_{i})_{i \in \N}$ est la famille des exposants des facteurs premiers d’un entier naturel $n$ , alors le nombre de diviseurs de $n$ est le produit des $e_{i}+1$ ; car pour chaque facteur premier d’un diviseur, on peut choisir l’exposant associé dans l’ensemble $\{0,...,e_{i}\}$ de cardinal $e_{i}+1$ . Il en résulte que $n$ a un nombre impair de diviseurs si et seulement si $e_{i}$ est pair pour tout $i$ , c’est-à-dire que $n$ est un carré.

Report