Probleme Arithmétique "chaine de divseurs"

Réponses à toutes vos questions de la 2nde à la Terminale toutes séries
Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21481
Enregistré le: 11 Nov 2009, 23:53

Re: Probleme Arithmétique "chaine de divseurs"

par Ben314 » 29 Oct 2017, 14:04

Salut,
nodgim a écrit: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...)
En procédant de la sorte, tu va avoir beaucoup beaucoup de mal à dénombrer le nombre de solution :
- Déjà, vu les répétitions, ça va pas être super aisé de dénombrer les "ordres" différents.
- Et ensuite, vu que tu va "découper" un ordre en morceaux, le même résultat pourra être obtenu en partant de plusieurs ordres différents. Par exemple partant de l'ordre 23225323, si je le découpe en 23/225/323, c'est exactement la même chose qu'en partant de l'ordre 32522332 que je découpe en 32/522/332.

Bref, de compter (voire même de "considérer") ce que tu appelle des "ordres", ça te mènera à rien vu la question posée.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius



nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: Probleme Arithmétique "chaine de divseurs"

par nodgim » 29 Oct 2017, 14:48

Oui Ben, tu l'as vu avant moi, j'écrivais justement pour dire que ça me marche pas.
Retour à la case départ....

Ralopisticulatrice
Messages: 4
Enregistré le: 27 Oct 2017, 23:22

Re: Probleme Arithmétique "chaine de divseurs"

par Ralopisticulatrice » 29 Oct 2017, 16:35

J'ai enlevé les séries formelles de ma preuve.

Précision : on considère que l'unique chaîne pour n=1 est de longueur 0.

On fait pour les nombres de la forme pour simplifier mais ça reste pareil pour plus de facteurs premiers. On identifie ce n par le couple (a,b) ∈ ℕ². On a les deux fonctions P,I : ℕ² → ℕ donnant les nombres de chaînes de longueurs paire et impaire, respectivement. On note (x,y) ≤ (a,b) pour dire que x ≤ a et y ≤ b. On note (x,y) < (a,b) pour dire que (x,y) ≤ (a,b) et (x,y) ≠ (a,b). On a alors les relations de récurrence suivante.




et pour (x,y) ≠ (0,0)





La justification est qu'un chemin de longueur paire jusqu'à (x,y), c'est un choix de (a,b) < (x,y) (la dernière étape), plus un chemin de longueur impaire jusqu'à (a,b). Symétriquement pour les chemins de longueur paire.

Soit D(x,y) ≔ P(x,y) - I(x,y). On obtient alors D(0,0) = 1 et pour (x,y) ≠ (0,0)


Autrement dit, on a pour tout (x,y) ≠ (0,0) la relation

et D(0,0) = 1.

On vérifie que le tableau suivant est solution (et comme il n'y a qu'une solution possible on a gagné).

1 | -1 | 0 | 0 | ⋯
-1 | 1 | 0 | 0 | ⋯
0 | 0 | 0 | 0 | ⋯


(Si on veut rajouter plus de facteurs premiers, il faut faire en plus de dimensions.)

-------

J'ai aussi trouvé une meilleure manière de faire en passant par les séries formelles. En reprenant le même A que plus haut, la solution en U de U = 1 + AU donne le nombre total de chaînes. Mais en ajoutant une variable formelle Z et en résolvant U = 1 + AZU, on récupère en plus l'information des longueurs de ces chaînes. On obtient .
Comme on veut la différence entre les longueurs paires et les impaires, il faut que les puissances paires de Z valent +1 et les puissances impaires -1. On évalue donc en Z=-1 et on trouve , ce qui donne le résultat voulu.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21481
Enregistré le: 11 Nov 2009, 23:53

Re: Probleme Arithmétique "chaine de divseurs"

par Ben314 » 29 Oct 2017, 17:41

Perso, je trouvais ta preuve avec les séries formelle plus jolie, et surtout plus simple vu qu'en fait tu n'a pas vraiment besoin de ton expression par récurrence pour avoir la série formelle correspondant aux décompositions paires respectivement impaires.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Viko
Membre Relatif
Messages: 209
Enregistré le: 19 Juin 2017, 01:51

Re: Probleme Arithmétique "chaine de divseurs"

par Viko » 29 Oct 2017, 17:48

maintenant il faut le refaire avec des outils lycée ^^
Qui ne maîtrise pas ses Cassinis, termine à Telecom Nancy

Ralopisticulatrice
Messages: 4
Enregistré le: 27 Oct 2017, 23:22

Re: Probleme Arithmétique "chaine de divseurs"

par Ralopisticulatrice » 29 Oct 2017, 18:21

Oui, je trouve aussi la rédaction avec les séries formelles plus jolies (@Ben) mais en fait j'ai fait ça justement pour rendre la preuve accessible au lycée (@Viko). C'est exactement la même chose mais dit différemment.

 

Retourner vers ✎✎ Lycée

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 42 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite