Cliquez pour afficher

L'idée est de décomposer un entier n non nul en produit de facteurs premiers et d'isoler les facteurs à puissance paire des facteurs à puissance impaire (éventuellement une des deux parties n'existe pas !) :



les p_i et les q_j étant bien sûr des premiers distincts 2 à 2.

je définis mon application de dans ⁺ de la façon suivante :

0 0
1 1







il est un peu tard là, mais il me semble que c'est une bijection ...

 Cliquez pour afficher

A mon humble avis, comme tu me proposes là, je risque de passer des nuits blanches .
Ça doit certainement marcher !
Il existe une suite assez élégante, systématique et récursive pour classer les rationnels ...

 Cliquez pour afficher

juste un lien :

 Cliquez pour afficher

Plus judicieux serait l'Arbre de Calkin-Wilf . Mais les deux sont très étroitement liés.
Il semble que la découverte de cette bijection n'ait pas plus de 20 ans ... amusant !

 Cliquez pour afficher

Le théorème de Cantor-Bernstein est-il interdit?

 Cliquez pour afficher

Pourquoi le serait-il ? S'il permet de fournir une bijection explicite, alors let's go ...

 Cliquez pour afficher

J'ai trouvé un truc qui m'a l'air assez élégant :

Étant donné un rationnel p/q, on en construit deux autres : (p+q)/q et p/(q+p). Par exemple à partir de 8/3 on obtient 11/3 et 8/11.
Et bien je prétends qu'à partir de 1/1, on obtient un arbre binaire qui atteint tous les rationnels positifs.

En effet, étant donné un rationnel p/q, on veut savoir si on peut remonter à 1/1.
Deux cas :
1) supposons que p < q. Alors le père de p/q est p/(q-p). Alors le dénominateur du père est strictement inférieur à celui du fils, son numérateur est identique. Si le père p/(q-p) a son numérateur toujours inférieur à son dénominateur, on reproduit l'étape 1, sinon on considère le cas suivant.
2) supposons p > q. Alors le père de p/q est (p-q)/q : leur dénominateur est identique, le numérateur diminue. Alors soit p-q > q auquel cas on considère le cas 2, sinon on reprend le cas 1.

Donc étant donné p/q, dans tous les cas son père aura soit son numérateur qui diminue soit son dénominateur qui diminue. On arrivera donc toujours à remonter vers 1/1.

Reste à montrer que chaque p/q est unique dans l'arbre. J'ai pas vraiment la foi de le faire mais je pense qu'il doit y avoir un argument pas trop compliqué.

Maintenant que l'arbre des rationnels est ainsi construit, il suffit de numéroter chaque noeud, par exemple de gauche à droite et de haut en bas (0 pour 1/1, 1 pour 1/2 etc.) et on a bien construit une bijection telle qu'on voulait.

 Cliquez pour afficher

C'est effectivement le fameux Arbre de Calkin-Wilf auquel je pense. J'en parlerai plus longuement à la fin du topic

 Cliquez pour afficher

je suis parti aussi sur un truc qui ressemble à ça, mais je crois qu'on veut une bijection explicite... établir q_n en fonction de n ... et réciproquement ...
je crois que j'ai trouvé

j'ai pas le courage de rédiger ça ce soir, je le ferai demain.

ma proposition du 20/02 n'est pas sous forme de suite mais a l'avantage d'être explicitée.

 Cliquez pour afficher

Après quelques recherches sur le lien proposé par jsvdb, une relation explicite via cet arbre est donné par exemple par :



Où est le n-ième terme de la suite diatomique de Stern 0, 1, 1, 2, 1, 3, 2, 3, 1, 4... :

J'ai tout trouvé là-dedans :

 Cliquez pour afficher

Bon, c'est un peu tricher car la suite diatomique de Stern est elle-même définie par récurrence...

 Cliquez pour afficher

Bon, voilà, je crois que c'est à peu près au point... et en plus c'est amusant cette correspondance ! merci jsvdb !

1) je définis la suite : pour n strictement positif.

C'est évidemment une suite à valeur dans .

2)Tout rationnel positif se décompose de façon unique en fraction continue avec

par exemple

on rappelle que ces coefficients de se trouvent avec les divisions successives de l'algorithme d'Euclide jusqu'à un reste nul en prenant la suite de quotients obtenus.

3) on démontre assez aisément que si alors :

et

4) pour tout entier n, construisons la séquence d'entiers de la façon suivante :

on écrit n en base 2.
on fait un bloc avec les "1" consécutifs situés à droite de l'écriture. Ce bloc est vide si n est pair.
dans le reste de l'écriture (si il en reste !):
chaque suite de "1" consécutifs est groupé avec le "0" qui suit pour faire un bloc
les "0" restés seuls font chacun un bloc.
on remplace ensuite chaque bloc par son cardinal et on lit cette séquence de droite à gauche
un exemple !

donne la suite de blocs : (10 / 0 / 11) puis la séquence (2;1;2)

donne (10 / 0 / 0 / 0 / vide) puis la séquence (0;1;1;1;2)

donne ((110 / 0 / 110 / 1 ) puis la séquence (1;3;1;3)

on remarquera que correspond au nombre de "0" dans l'écriture de n en base 2, que seul le premier entier de cette séquence peut être nul et que le dernier entier de cette suite vaut toujours au moins 2.

5) avec le point (3), on démontre par récurrence que cette séquence engendrée à partir de n est l'écriture en fraction continue de

on peut ainsi expliciter et le calculer directement

par exemple

6) en explicitant la réciproque on démontre du même coup le caractère bijectif de cette correspondance :

si on considère un rationnel positif écrit en fraction continue (unique si )

on crée un entier n dont l'écriture en base 2 est constitué de la juxtaposition des blocs suivants :



et on a alors

par exemple : donne les blocs (10 / 10 / 111)

donc donc

voilà... en espérant qu'il n'y a pas d'erreur !