Barre utilisateur

[ID: 3225] [Date de publication: 18 novembre 2022 15:34] [Catégorie(s): Nombres premiers ] [ Nombre commentaires: 1] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]

Solution(s)

Solution(s)

Exercice 1491
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 15:34

1. Plaçons nous du point de vue d’une porte. Elle sera ouverte après le passage des mathématiciens si son état (ouvert/fermé) a été modifié par un nombre impair de mathématiciens (et fermée sinon). Autrement dit elle sera ouverte in fine si son numéro \(m\) admet un nombre impair de diviseurs (positifs). On décompose \(m\) en facteurs premiers : \(m = \prod_{p \in \mathbb{P}} p^{\nu_p(m)}\). Les diviseurs \(d\) de \(m\) s’écrivent donc \(d = \prod_{p \in \mathbb{P}} p^{\nu_p(d)}\) avec \(\forall\,p \in \mathbb{P}, \;\nu_p(d)\leqslant\nu_p(m)\). Pour chaque choix de nombre premier \(p\) divisant \(m\) on a \(\nu_p(m)+1\) puissances de \(p\) qui divisent \(m\), à savoir \(1, p, p^2,\ldots,p^{\nu_p(m)}\) il y a donc un total de \(\prod_{p \in \mathbb{P}}(\nu_p(m)+1)\) diviseurs de \(m\). Maintenant un produit de facteurs est impair si et seulement si chacun des facteurs est impairs, donc dans notre cas on doit avoir tous les \(\nu_p(m)+1\) impairs c’est-à-dire tous les \(\nu_p(m)\) pairs ce qui signifie que \(m\) est un carré parfait.
   Une autre façon de voir : Si \(d\) est un diviseur de \(m\) alors \({\scriptstyle m\over\scriptstyle d}\) est aussi un diviseur de \(m\). On peut ainsi regrouper les diviseurs de \(m\) deux par deux, sauf si, par extraordinaire, \(m\) et \({\scriptstyle m\over\scriptstyle d}\) sont égaux, c’est-à-dire lorsque \(m = d^2\) donc lorsque \(m\) est un carré parfait.
   Notre problème devient donc : Combien y a-t-il de carrés parfaits entre \(1\) et \(n\) ? Il y en a \(\lfloor \sqrt n \rfloor\).
   

2. Plaçons nous du point de vue du mathématicien numéro \(k\). Il change l’état (ouvert/fermé) des portes \(k, 2k, \ldots\). De combien de portes change-t-il l’état ? En \(n\) combien de fois \(k\) ? Il va \(\left\lfloor \dfrac nk \right\rfloor\). Il y a donc eu au total \(\sum_{k=1}^n\left\lfloor \dfrac nk \right\rfloor\) changement d’état. Si on enlève les \(\lfloor \sqrt n \rfloor\) portes exceptionnelles, toutes les portes ont changé un nombre pair de fois. C’est bien dire que \(\sum_{k=1}^n\left\lfloor \dfrac nk \right\rfloor - \lfloor \sqrt n \rfloor\) est un entier pair.