Chaîne de diviseurs

Bonjour,

Soit une chaîne de diviseurs correspondant à la séquence de nombres entiers croissants tel que chaque élément divise le suivant.
Soit C(n) le nombre de "chaînes" commençant par 1 et finissant par n.
Montrer que le nombre de chaînes avec une longueur paire P(n) et le nombre de chaînes avec une longueur impaire I(n) sont égaux ou diffèrent de 1.

Avez-vous une idée ? Merci d'avance.

Réponses

  • Posons, pour $n\in\mathbb{N^*}$, $f(n)=I(n)-P(n)$. Si $n>1$, on a $P(n)=\sum\limits_{\substack{d\,|\,n \\ d\not=n}}I(d)$ et $I(n)=\sum\limits_{\substack{d\,|\,n \\ d\not=n}}P(d) $, d'où $f(n)=-\sum\limits_{\substack{d\,|\,n \\ d\not=n}}f(d)$. On peut vérifier que $f(1)=1-0=1=\mu(1)$ donc il est facile d'en déduire que pour tout $n\in\mathbb{N}^*$, $f(n)=\mu(n)\in\{-1,0,1\}$, où $\mu$ est la fonction de Möbius.
  • Merci bien. Ce problème posé au lycée, ne me paraissait pas en rapport, j'en ai confirmation (fonction de Möbius). Par contre, j'aurais dit que I(1)=0 et P(1)=1, chaîne 1 de longueur nulle, donc paire. Cela ne doit pas changer le résultat.
  • Le mot "fonction de Mobius" n'est qu'un nom qu'on donne. Ca n'implique pas une intraitabilité d'office au lycée (ça ne veut pas dire que d'autres raisons ne l'entrainent pas)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Non bien sûr, il peut y avoir d'autres solutions. Seulement, avec les moyens du lycée, cela paraît bien compliqué. On peut voir la relation de récurrence entre les chaînes paires et les chaînes impaires, mais le dénombrement de ces chaînes par une relation de récurrence est moins visible.::o
  • Pour moi, la longueur d'une chaîne est le nombre de "maillons". Il n'y a qu'une seule chaîne commençant en $1$ et finissant en $1$ : celle réduite au seul maillon $1$ (qui est donc de longueur $1$, impaire). Donc $I(1)=1$ et $P(1)=0$.

    Il y a peut-être une méthode qui n'utilise que des outils de terminale. À quelle occasion est-tu tombée sur ce problème ?
Connectez-vous ou Inscrivez-vous pour répondre.