Probleme Arithmétique "chaine de divseurs"

[Burp]

Soit une chaine de diviseurs la séquence de nombres entiers croisaants tel que chaque element divise le suivant.
Soit C(n) le nombres des "chaines" commençant par 1 et finissant par n.
Montrer que le nombre des chaines avec une longueur paire P(n) et le nombre des chaines avec une longueur impaire I(n) sont égaux ou différents par 1.

Aidez moi!!!

[pascal16]

Personnellement, je suivrai la piste de la décomposition en facteur premier, sachant que chacun des diviseurs est composé de ces facteur premier élevés à la puissance 0 à i(j) ou i est l'exposant du jième facteur premier de la décomposition

[zygomatique]

salut

donc la décomposition de n en produit de facteurs premiers ...

on considère donc une chaîne avec

peut-être une idée : montre qu'à toute chaîne de longueur paire tu peux lui associer une chaîne de longueur impaire en intercalant un diviseur ... au bon endroit ...

[Burp]

ok , je vais l'essayer

[Burp]

aucun résultat

[Viko]

je pense avoir une idée mais pas sûr que sa marche et il reste pas mal de truc à justifier mais en gros ce qu'il faut dire dans un premier temps que chaque élément d'une chaîne est un diviseur de n, puis dans un second temps que en partant des deux chaînes les plus triviale :
1->n et 1->d-> n/d ->n où d est un diviseur de n on peut avec la première construire toutes les chaînes paires et avec la seconde toutes les chaînes impair et que donc qu'il y a autant chaînes pair et impair
je ne sais pas si j'ai été clair mais ce n'est qu'un début je reposterai quand j'en aurai trouvé plus...

[zygomatique]

salut

donc la décomposition de n en produit de facteurs premiers ...

on considère donc une chaîne avec

peut-être une idée : montre qu'à toute chaîne de longueur paire tu peux lui associer une chaîne de longueur impaire en intercalant un diviseur ... au bon endroit ...

et donc on a pour tout i : avec

ouais bof ...

[Burp]

J'ai une idéé comment la prouver mais j'ai besoin d'aide
Alors on peut toujours commnçer par la chaine 1-->n .Si on peut prouver qu'on peut toutes les chaines possibles en ajoutant ou enlevant un par un des divideurs de la chaine (ex: 1--> n devient 1-->d1-->n devient 1->d1->d3->n devient 1->d1->d2->d3->n devient 1->d2-*>d3->n ....etc) on a prouvé que les nombres des chaines paires at impaires ne diffère que par 1 car en ajoutant ou en enlèvant des nombres on est en train de balançer le nombre des chaines. En autre mot on peut correspandre une chaine paire a chaque chaine impaire.

Comment peut on prouver qu'on peut obtenir toutes les chaines possibles par cette méthode??

[Viko]

Comment peut on prouver qu'on peut obtenir toutes les chaines possibles par cette méthode??

C'est la que réside toute la difficulté du problème... En tout cas cela me semble trés hardu pour un exercice de lycée...

[Lostounet]

Hello,

Quelqu'un a-t-il réussi ?

[pascal16]

Je sais te construire une chaîne de parité différente facilement, mais sans bijection donc sans intérêt.
J'ai regardé si la différence était supérieure à 2 : bof
et le dénombrement mélangé à la récurrence : peut-être, mais trop fatigué ce soir pour m'y lancer

[Pseuda]

Bonjour,

Une idée. On part de n, sa décomposition en facteurs premiers, toutes ses chaînes 1-n, et on considère que P(n)-I(n) = -1, 0 ou 1.

On ajoute à n un nombre premier p, et on étudie les chaînes 1-n*p :

- si p ne figure pas dans la décomposition de n en facteurs premiers, p peut être inséré dans une chaîne, soit dans un "vide" (par multiplication du nombre précédent), soit "à la place" (d'un nombre de la chaîne en le multipliant). Dans les 2 cas, tous les nombres qui suivent dans la chaîne sont multipliés par p, et toutes les chaînes obtenues sont différentes.
Quand p est rajouté dans un vide, la longueur de la chaîne augmente de 1 et la parité de la chaîne change, quand p rajouté "à la place", sa longueur ne change pas et sa parité reste la même.
Comme il y a un "vide" de plus que de "places" dans une chaîne (le vide après n), et qu'une chaîne paire produit une chaîne impaire de plus que de chaînes paires et inversement, la différence P(np)-I(np) passe de -1 à 1, de 1 à -1, et 0 à 0.

- si p figure déjà dans la décomposition de n, c'est là que cela devient compliqué, aux endroits où il figure on obtient la même chaîne en rajoutant p dans le vide avant ou dans le vide après , donc une chaîne paire ou impaire produit autant de chaînes paires que de chaînes impaires, et comme il y a un vide de plus que de places, P(np)-I(np) passe de 1 à 0, -1 à 0, et 0 à 1 ou -1 (enfin je crois intuitivement).

Tout cela est assez approximatif, et me paraît bien compliqué pour un exercice du lycée, il y a sûrement plus simple.

[zygomatique]

j'avais exactement la même idée (sans la récurrence : passer de n à np) ... mais ça me semble bien compliqué ... et ta démonstration est tout à fait rigoureuse sur le fond (peut-être faut-il revoir la forme pour être plus précis mais l'idée est là)

avec ce que j'avais écrit à 22h46 si on a une chaîne de diviseurs et qu'on prend un facteur p ""encore possible"" (ie p n’apparaît pas avec sa puissance maximale alors il y a les deux cas comme tu dis :

p apparaît avec sa puissance non maximale et on ne change pas le cardinal de la chaîne
p n’apparaît pas et on le rajoute au bon endroit et le cardinal de la chaîne augmente de 1 (quel que soit le cardinal de la chaîne au départ)

(en multipliant tous les diviseurs suivant par p bien sur)

[Pseuda]

Bonsoir,

Une démonstration sans récurrence est toujours préférable (plus simple), mais je ne comprends pas vraiment l'idée, le lien avec le résultat à obtenir.

A mon avis il y a une méga-astuce qui nous échappe. Bizarre ce problème donné au lycée, surtout qu'il relève à la fois de la S spé maths (arithmétique) et de la ES spé maths (graphes).

Et je ne suis pas vraiment satisfaite de ma solution, indépendamment du fait qu'elle soit compliquée.

[zygomatique]

l'idée étant qu'entre deux chaines paires je peux intercaler une chaine impaire et inversement ... mais il n'y a pas unicité ... c'est pour quoi je n'avais pas poster ...

[zygomatique]

où as-tu trouvé cette question ?

[Ralopisticulatrice]

J'ai une démonstration mais ce n'est pas du niveau lycée.

On identifie un entier par la liste des exposants dans sa décomposition en nombres premiers. Pour simplifier l'exposé je suppose qu'on se limite à deux facteurs premiers ou moins, mais c'est pareil s'il y en a plus (on peut aussi faire une preuve unifiée sans avoir besoin de limiter le nombre de facteurs premiers mais ce n'est pas important).
On a deux fonctions I et P de ℕ² vers ℤ, donnant le nombre de chemins pairs pour l'une et le nombre de chemins impairs pour l'autre. On regarde I et P comme des séries formelles dans ℤ[[X,Y]]. On a alors des relations de récurrence liant I et P. En posant , ces deux relations s'écrivent comme suit.

1) P = 1 + A I
2) I = A P

Initialement, j'avais résolu ce système (pas difficile), mais on peut se contenter du calcul suivant. On pose D ≔ P-I et on obtient D = 1-AD en faisant la différence des deux relations plus haut. On trouve donc D = (1-X)(1-Y).

Pour conclure, l'expression de la différence est donc très simple : s'il y a des facteurs premiers doubles, c'est zéro, et sinon c'est 1 ou -1 suivant la parité du nombre de facteurs premiers.

[nodgim]

Pour un ordre des exposants donnés, c'est exactement le même problème de la grenouille qui monte un escalier de n marches, il y a 2 ^(n-1) façons de le passer selon chaque marche qui est étape (1) ou non (0). En écrivant tous les mots binaires, il est évident qu'il y a autant de mots avec un nombre impair de 1 que de mots avec un nombre pair de 1 (à l'unité près).

[Ralopisticulatrice]

Pour un seul facteur premier d'accord, mais comment généralises-tu à plus de facteurs premiers ? Dans le cas d'un seul facteur premier, effectivement on a une bijection simple consistant à inverser les 0 et les 1 dans la représentation d'un chemin avec un mot binaire. Mais sinon je ne vois pas.

[nodgim]

Quand j'écrivais: " pour un ordre des exposants donné " cela implicitement concernait les exposants des différents facteurs premiers.
Exemple n = 2^4 * 3 ^ 3 * 5= 22223335.
Un ordre, c'est par exemple 23225323.
Alors tu passes de 1 à N en découpant 23225323 de toutes les façons que tu veux, avec 7 étapes max. Si tu regardes bien tu as 2^7 façons de le faire: du code 0000000 (aucune étape, tu passes directement de 1 à N) au code 1111111 (tu franchis toutes les étapes: 2 puis 23 puis 232, etc...)