Mathématiques - 3 entiers en 1

3 entiers en 1
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: semaj_james

Bonjour,

Je voudrais a partir de 3 entiers n'en faire plus qu'un et pouvoir les retrouver ensuite.
Par exemple si l'on a x, y et z on obtient w.
Comment faire pour retrouver x, y et z a partir de w ?
Ceci porte il un nom ?

Cordialement

Posted by: Imod

Oui cela porte un nom : incompréhensible .

Imod

Posted by: sandrine_guillerme

Posted by: Zebulon

Bonsoir,
dans la même idée que l'autre exercice, on peut poser $\Large f(x,y,z)=2^x3^y5^z$ . Alors pour tout entier naturel w, il existe un unique entier naturel x, un unique entier naturel y et un unique entier naturel z tels que f(x,y,z)=w.

Posted by: yos

Il s'agit d'exhiber une injection de $\mathbb {N}^3$ dans $\mathbb N$ . L'exemple de Zébulon me semble OK.

Posted by: Zebulon

Citation:

Posté par semaj_james

Ceci porte il un nom ?

Ca me fait penser à une fonction de hachage dite "à brêche secrète", c'est-à-dire une fonction injective difficilement inversible. Elle est facilement inversible pour les nombres premiers 2, 3 et 5 que j'ai choisis, mais si on prend de très grands nombres premiers, en pratique on ne sait pas retrouver x, y et z si on ne connaît pas les nombres premiers.
On peut faire ça avec autant d'entiers qu'on le souhaite puisqu'il y a une infinité de nombres premiers.

Posted by: Zebulon

Qui connaît d'autres fonctions de ce type (définie sur $\mathbb{N}^r$ à valeurs dans $\mathbb{N}$ , injective et difficilement inversible) ?
Je cherche mais je ne vois que ça.

Posted by: yos

$\displaystyle{(a,b)\mapsto\frac{1}{2}(a+b)(a+b+1)+ b}$ doit être bijective.

Posted by: semaj_james

Citation:

Posté par Zebulon

Bonsoir,
dans la même idée que l'autre exercice, on peut poser $\Large f(x,y,z)=2^x3^y5^z$ . Alors pour tout entier naturel w, il existe un unique entier naturel x, un unique entier naturel y et un unique entier naturel z tels que f(x,y,z)=w.

Comment fait on pour retrouver x,y,z a partir de w ?
De meme pour un cas plus general si on veut passer de n entiers a 1 seul et pouvoir a partir de cet entier retrouver tous les entiers de depart, comment faire pour les retrouver ?
on fait $\Large f(x,y,z,a,...)=2^x3^y5^z7^a....$ mais ensuite quelle genre de fonction devrait on utiliser pour les retrouver ?

Posted by: semaj_james

Citation:

Posté par yos

$\displaystyle{(a,b)\mapsto\frac{1}{2}(a+b)(a+b+1)+ b}$ doit être bijective.

Comment retrouve t on x et y ?

Citation:

x y z
0 0 0
0 1 1
1 0 2
0 2 3
1 1 4
2 0 5
0 3 6
1 2 7
2 1 8
3 0 9
0 4 10
1 3 11
2 2 12
3 1 13
4 0 14
1 4 16
2 3 17
3 2 18
4 1 19
2 4 23
3 3 24
4 2 25
3 4 31
4 3 32
4 4 40

Posted by: Zebulon

Vous en auriez d'autres où x=0 ? Ca ressemble à des coefficients du binôme :
$\Large (0,1)\to 1$
$\Large (0,2)\to3$
$\Large (0,3)\to6$
$\Large (0,4)\to10$
On peut penser que $\Large (0,n)\to{n+1\choose n-1}$ .
Je continue de chercher.
C'est dans quel contexte au fait ?

Posted by: Zebulon

On dirait aussi que $\Large (n,0)\to{n+2\choose n}-1$ .
Je dis peut-être n'importe quoi § C'est la première fois que je cherche ce genre de trucs !

Posted by: semaj_james

X Y z --- X Y z

0 0 0 --- 4 3 32
0 1 1 --- 5 2 33
1 0 2 --- 6 1 34
0 2 3 --- 7 0 35
1 1 4 --- 1 7 37
2 0 5 --- 2 6 38
0 3 6 --- 3 5 39
1 2 7 --- 4 4 40
2 1 8 --- 5 3 41
3 0 9 --- 6 2 42
0 4 10 --- 7 1 43
1 3 11 --- 2 7 47
2 2 12 --- 3 6 48
3 1 13 --- 4 5 49
4 0 14 --- 5 4 50
0 5 15 --- 6 3 51
1 4 16 --- 7 2 52
2 3 17 --- 3 7 58
3 2 18 --- 4 6 59
4 1 19 --- 5 5 60
5 0 20 --- 6 4 61
0 6 21 --- 7 3 62
1 5 22 --- 4 7 70
2 4 23 --- 5 6 71
3 3 24 --- 6 5 72
4 2 25 --- 7 4 73
5 1 26 --- 5 7 83
6 0 27 --- 6 6 84
0 7 28 --- 7 5 85
1 6 29 --- 6 7 97
2 5 30 --- 7 6 98
3 4 31 --- 7 7 112

Posted by: Zebulon

Je suis trop bête ! Je n'avais pas vu qu'il y avait un ordre très simple !

Posted by: semaj_james

Citation:

Posté par Zebulon

C'est dans quel contexte au fait ?

C'est pour faire du codage en informatique

Posted by: Zebulon

Il semblerait que $\Large z={(x+y)(x+y+1)\over2}+x$ , non ?
C'est la fonction que proposait Yos.

Posted by: semaj_james

Citation:

Posté par Zebulon

Il semblerait que $\Large z={(x+y)(x+y+1)\over2}+x$ , non ?
C'est la fonction que proposait Yos.

oui c'est ca. Je cherche une fonction pour retrouver x et une fonction pour retrouver y.
Je voie qu'il y a quelque chose:
x y z

0 0 0

0 1 1
1 0 2
la somme x+y fait 1
on decremente y a partir de cette somme jusqu'a 0
on incremente x pour arriver a cette somme en partant de 0

0 2 3
1 1 4
2 0 5
la somme x+y fait 2
on decremente y a partir de cette somme jusqu'a 0
on incremente x pour arriver a cette somme en partant de 0

0 3 6
1 2 7
2 1 8
3 0 9
la somme x+y fait 3
on decremente y a partir de cette somme jusqu'a 0
on incremente x pour arriver a cette somme en partant de 0

et ainsi de suite mais je voie pas comment retrouver x et y.

Posted by: Zebulon

Oui, c'est comme ça que j'ai trouvé la fonction. D'ailleurs, vous auriez pu dire que vous la connaissiez !
A part en listant comme ça, je ne vois pas comment retrouver x et y à l'aide de la formule.
Je l'ai trouvée en remarquant que ce qui variait, c'est la somme n=x+y.
Pour n=0, un seul couple : (0,0)
Pour n=1, deux couples : (1,0)) et (0,1)
$\Large\vdots$
Pour n quelconque, n+1 couples : (0,n) ; (1,n-1) ; ... (n-1,1) ; (n,0).

Posted by: Zebulon

Citation:

Posté par Zebulon

Il semblerait que $\Large z={(x+y)(x+y+1)\over2}+x$ , non ?

En fait, non. Ce n'est pas exactement ça. C'est $\Large z={(x+y+1)(x+y+2)\over2}+x$ .

Posted by: Zebulon

Citation:

Posté par semaj_james

Je cherche une fonction pour retrouver x et une fonction pour retrouver y.

On peut commencer par chercher dans quel bloc n se trouve le z donné.
On a $\Large n=max\{m\in\mathbb{N}\ |\ m(m+1)\leq2z\}=min\{m\in\mathbb{N}\ |\ 2z\leq(m+1)(m+2)\}$ je suppose qu'il est plus facile de trouver un min qu'un max, mais bon, je donne les deux.
Et donc $\Large x=z-{n(n+1)\over2}$ et $\Large y=n-x$ .
J'ai corrigé en fonction de votre message de 23h29 : en effet, j'avais mal recopié la liste et c'est $\Large z={(x+y)(x+y+1)\over2}+x$ .
La "formule de Yos" ...

Posted by: semaj_james

Citation:

Posté par Zebulon

En fait, non. Ce n'est pas exactement ça. C'est $\Large z={(x+y+1)(x+y+2)\over2}+x$ .

non c'est bien la formule de yos.
la formule: $\Large z={(x+y+1)(x+y+2)\over2}+x$ donne

X Y z

0 0 1
0 1 3
1 0 4
0 2 6
1 1 7
2 0 8
0 3 10
1 2 11
2 1 12
3 0 13
0 4 15
1 3 16
2 2 17
3 1 18
4 0 19
1 4 22
2 3 23
3 2 24
4 1 25
2 4 30
3 3 31
4 2 32
3 4 39
4 3 40
4 4 49

Posted by: Zebulon

J'ai corrigé mon précédent message qui donne x et y en fonction de z.

Posted by: Imod

Ces interventions avec toute leur complexité me rappellent l'éblouissement que j'ai eu quand j'ai découvert la théorie des cardinaux et ordinaux "les bijections existent" mais de là à les expliciter ... Q en bijection avec N !!!!
Un gros coup de chapeau à Cantor .

Imod

Posted by: Zebulon

C'est bien une des grandes différences entre mathématiciens et informaticiens.

Citation:

Posté par Imod

"les bijections existent"

c'est grâce aux mathématiciens qu'on le sait

Citation:

mais de là à les expliciter

C'est le boulot des informaticiens !
Imod, je pensais que vous alliez confirmer (ou infirmer) ce que j'ai trouvé. Vous pouvez regarder quand même s'il vous plaît ?

Posted by: yos

Ah tiens je croyais que ma formule donnait une bijection. C'est seulement injectif à ce que je vois.

Posted by: semaj_james

Citation:

Posté par Zebulon

J'ai corrigé mon précédent message qui donne x et y en fonction de z.

Je vais regarder tout ca. la je vais me coucher car demain le travail. Je te remercie d'avoir passer autant de temps a m'aider. merci beaucoup

Posted by: Zebulon

Non, c'est bon. La première formule de Yos $\Large (x,y)\to {(x+y)(x+y+1)\over2}+y$ donne bien une bijection. Ici, ce n'est pas tout à fait la même car c'est $\Large (x,y)\to {(x+y)(x+y+1)\over2}+x$ , on a interverti les colonnes X et Y par rapport à la première formule de Yos.
Quand je l'ai trouvée, je ne m'attendais pas du tout à retomber sur ce résultat ! Vous la connaissiez avant ou vous l'avez trouvée spontanément ? Et dans ce cas, comment vous l'avez trouvée ?

Posted by: Zebulon

Citation:

Posté par semaj_james

Je vais regarder tout ca. la je vais me coucher car demain le travail. Je te remercie d'avoir passer autant de temps a m'aider. merci beaucoup

De rien. Moi aussi j'aimerais bien aller me coucher (demain, 9 heures de Maths...

)

Posted by: alben

Citation:

Posté par yos

Ah tiens je croyais que ma formule donnait une bijection. C'est seulement injectif à ce que je vois.

Non non c'est bien une bijection de N
Je l'inverse de manière un peu différente de Zebulon (ent=partie entière) :
$n=ent(\frac{\sqr{8z+1}-1}{2})$ et $y=z-\frac{n(n+1}{2}$ x=n-y
Bien sur, ça doit revenir au même mais c'est plus facile à programmer

Posted by: Imod

Désolé Zebulon , ça attendra demain , ces problèmes ne sont pas simples et à l'approche de minuit je ne suis plus que l'ombre de moi même .

Imod

Posted by: Zebulon

Citation:

Posté par alben

$n=ent(\frac{\sqr{8z+1}-1}{2})$ et $y=z-\frac{n(n+1}{2}$ x=n-y

Ca, c'est pour ce que j'ai appelé la première formule de Yos. Ici, c'est l'autre : z=truc + x et pas z=truc + y donc il faut intervertir x et y par rapport à votre formule pour être dans le cas de Semaj_james.

Posted by: alben

Oui, j'ai du rater quelques épisodes
Mais une chose est certaine, c'est que si on fait un tableau avec les valeurs de x en colonne et y en ligne (ou l'inverse) et la valeur de la fonction de yos aux intersection, les diagonales / sont intéresssantes.
On visualise bien la construction de la bijection qui ressemble à celles que l'on fabrique pour mettre en bijection N² et N et démontrer que Q est dénombrable. On peut aussi faire un remplissage avec les carrés des nombres en diagonale \

Posted by: Zebulon

Attention quand même, la formule de Yos donne une bijection de $\mathbb{N}^2$ sur $\mathbb{N}$ , mais elle n'est pas définie sur $\mathbb{Q}$ . En effet, quelle est l'image de 1 ? C'est Yos(1,1) ? Ou Yos(346422,346422) ?

Posted by: yos

Citation:

Posté par Zebulon

Attention quand même, la formule de Yos donne une bijection de $\mathbb{N}^2$ sur $\mathbb{N}$ , mais elle n'est pas définie sur $\mathbb{Q}$ . En effet, quelle est l'image de 1 ? C'est Yos(1,1) ? Ou Yos(346422,346422) ?

Je songe à réclamer des droits d'auteurs. Bien que je n'aie pas inventé cette formule évidemment.
J'ai cru un instant que ce n'était pas bijectif en voyant les tableaux de valeurs de semaj_james. Il faut plutôt faire un tableau à double entrée (x et y) et on voit que les entiers naturels se présentent dans l'ordre dans les diagonales du tableau.
Cet exo (classique) se trouve par exemple dans le livre de Luc Moisotte : 1850 exercices pour le Capes. Livre assez ancien, du temps où une épreuve orale du capes consistait en la résolution d'un exo sans préparation. Si vous voyez ce livre chez un bouquiniste, vous pouvez l'acheter les yeux fermés. C'est d'une richesse inouïe et surtout, délice suprème, les exos ne sont pas corrigés.

Posted by: Imod

Une bonne nuit de sommeil et ce matin je me suis souvenu d'un exercice qui définissait très simplement et explicitement ( mais par récurrence ) une bijection de $\mathbb{N}^*$ dans $\mathbb{Q}_+^*$ . Une petite fouille dans mes notes et voilà :
$f\ :\ \mathbb{N}^*\rightarrow \mathbb{Q}_+^* \ : \ f(1)=1\ ; \ f(2n)=1+f(n)\ ;\ f(2n+1)=\frac{1}{f(2n)}$ .

Une remarque , en posant $f(0)=0$ et $f(-n)=-f(n)$ , on définit une bijection de $\mathbb{Z}$ dans $\mathbb{Q}$ .

Amusez-vous bien !

Imod

Posted by: alben

Bonsoir,

Pour inverser ta bijection, je propose
décomposition en fraction continue
puis passage en binaire
qu'il suffira de convertir en décimal.

Posted by: Imod

Bonjour alben .

J'avais pensé à la même chose mais j'ai trouvé une démonstration vraiment élémentaire . Quelqu'un d'autre la trouvera ?

Imod

Posted by: alben

Bonsoir Imod,
Démontrer quoi ? Que c'est une bijection ? l'injection me semble découler de la construction même de la fonction (à partir de considération d'ordre de grandeur) Pour la surjection, on peut construire une suite récurrente mais ça me semble équivalent au passage par les fractions rationnelles ou à Bezout

Posted by: Imod

Oui alben je suis d'accord pour le côté évident de l'injection mais la surjectivité me gène beaucoup plus , peut être que je passe à côté de quelque chose d'évident ?

Imod

Posted by: alben

Je ne vois pas de méthode qui ne revienne pas à exhiber l'antécédant d'un rationnel. Et pour cela, je ne peux pas éviter les puissances de 2 (ou l'écriture en binaire, ce qui revient au même).
J'ai essayé si l'on ne pouvait pas montrer globalement la surjectivité avec Bezout mais sans succès. On retombe sur l'algorithme d'Euclide généralisé.
Toutefois, le calcul de l'antécédent à partir d'une suite double finie n'est pas bien complexe.

On peut peut-être en posant
$A=\{q\in N |\exist p\in N \; pgcd(p,q)=1\; et \; p<q \; et \;\frac{p}{q}\notin f(N)\}$
A doit avoir un élément minimal -> contradiction...

Posted by: Imod

Encore une fois d'accord à 100% avec ce que tu dis , j'ai aussi utilisé une interprétation qui se ramène à une décomposition en base 2 pour faire apparaître une contradiction sur l'existence d'un maximum d'un ensemble qui s'apparente au tien . C'est quand j'ai voulu mettre au propre les "on voit bien que " et les "il est clair que" que j'ai tenté une nouvelle approche mais je me suis peut être enfermé dans un rigorisme inutile . Je poste ma solution dès que j'aurais trouvé un moment pour la taper .

En tout cas merci de t'intéresser au problème

Imod

Posted by: alben

Mais non, la dernière démarche dont j'ai eu l'idée en rédigeant le post marche parfaitement :

N* est inclus dans f(N*) puisque f(2^k)=k
on définit $A=\{q\in N |\exist p\in N \; pgcd(p,q)=1\; et \; p<q \; et \;\frac{p}{q}\notin f(N)\}$
A est une partie de N qui possède donc un élément minimal : q
(en supposant A non vide)
donc il existe p/q irréductible qui n'a pas d'antécédent.
Soient k=ent(q/p) et q'=q-kp.
Si q'/p avait un antécédent n alors $f(n.2^{k}+1) =\frac{p}{q}$
Donc q'/p ne peut avoir d'antécédent.
Mais alors p€A et p<q --> contradiction
Donc A est vide : $(\forall q\in N)(\forall p\in N)(pgcd(p,q)=1\; et \; p<q )\;\Rightarrow\;\frac{p}{q}\in f(N)\$
En d'autres termes $]0,1[\subset f(N)$
On généralise à Q* par division euclidienne en utilisant le point 1

Voilà une démo qui me semble à peu près exhaustive et qui n'est pas très lourde.
Est-ce la tienne ?

PS ton équation me rappelle de vieux souvenirs. Je ne lache pas l'affaire mais je n'ai pas trouvé le temps de m'y remettre

Posted by: Imod

Désolé alben , soit je prends un moment pour tapper mon texte soit je lis le tien , j'ai choisi la première solution mais je te lis demain bien sûr .
A la fonction f on associe un arbre de sommet principal f(1)=1 et chaque sommet génère deux fils , l'ainé f(2n) et le cadet f(2n+1) . L'ensemble des sommets est clairemant en bijection avec N* car chaque génération comporte $2^n$ éléments : $\{f(x)\ : \ x \in \{2^n;2^n+1;2^n+2;...2^{n+1}-1\}\}$ . Par construction le fils ainé de a/b est (a+b)/b et le cadet b/(a+b) . Réciproquement , si a/b est un fils , il est l'ainé de (a-b)/b ou le cadet de (b-a)/a .
On vérifie facilement que les fractions qui définissent les différents enfants sont irréductibles , que les ainés sont supérieurs à 1 , que les cadets sont inférieurs à 1 et que deux frères sont inverses l'un de l'autre .

1°) Tout rationnel positif apparaît dans l'arbre .

Supposons par l'absurde qu'il existe des rationnels positifs a/b n'apparaissant pas dans l'arbre , considérons parmi eux ceux qui ont un dénominateur minimal et parmi eux celui dont le numérateur est minimal .

- Si a<b alors (a+b)/a figure dans l'arbre et c'est un fils ainé . Le frère de son père est a/b . Contradiction .
- Si b<a alors (a-b)/a figure dans l'arbre ainsi que son fils ainé a/b . Contradiction .

2°) Aucun rationnel n'apparaît deux fois .

Toujours par l'absurde , s'il existe des rationnels a/b qui apparaîssent deux fois , on considère le plus petit ( au sens du 1°)

- Si a<b , a/b est un cadet , son père (b-a)/a figure aussi deux fois . Contradiction .
- Si b<a , a/b est un ainé , son père (a-b)/b figure aussi deux fois . Contradiction .

Le bref coup d'oeil que j'ai posé sur ton texte me dis que nous allons dans le même sens , mais j'ai toujours adoré "habiller" les exercices pour mieux les assimiler ( mon niveau d'abstraction atteind vite ses limites ) . A demain , ou plutôt à tout à l'heure , je n'avais pas vu l'heure et à huit heures au travail !

Imod

Posted by: alben

Suite : fonction réciproque:
La démo du fait que la fonction est bijective n'est pas suffisante pour les casseurs de codes et autres hackers. Il faut expliciter la fonction réciproque :
1 démarche avec les fractions continues
Soit y un rationnel que l'on développe en fraction continue sous la forme
$y=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+....} }}$
Ce développement est fini car y est un rationnel, soit an son dernier coef
posons $b_0=a_0;b_{k}=a_k+b_{k-1} \;si\; 0<k<n;b_n=a_n+b_{n-1}-1$ . Alors $f^{-1}(y)=\sum_{k=0}^n\;2^{b_k}$
En binaire c'est encore plus simple puisqu'il suffit de mettre 1 dans chaque position indiquée par les bi et de compléter par des zéros
exemple 65/17 donne la suite des a : (3,1,4,1,2) et des b : (3,4,8,9,10)
donc x=11100011000 (on a mis des 1 en 3ième, 4ième ...10ième position à compter de la droite, la position zéro est celle des unités)
1 démarche avec une suite double pour ceux qui sont allergiques aux fractions continues (ils ont tort

)
Soit y=p/q et les suites
$u_0=p;u_1=q;b_0=0;u_{n+1}=u_{n-1}-u_n(b_n-b_{n-1});b_n=b_{n-1}+ent(\frac{u_{n-1}}{u_n})$
Ces suites sont finies et l'on s'arrête quand un=1.
Il faut ôter 1 au dernier b et la suite bn se décode en décimal ou binaire comme ci dessus (sauf qu'ici on démarre de 1 et non de zéro)
Les deux méthodes sont, bien entendu strictement équivalentes et très faciles à programmer

EDIT je viens de voir ton message Imod, effectivement j'ai l'impression qu'on est proches mais il est trop tard et les histoires de familles m'ont toujours épuisé... je lirais demain tranquillement les aventures du frère du père (et en plus il ya des ainés et des cadets !)

Posted by: pedro_cristian

Citation:

Posté par alben

J'espere que je ne suis pas trop H.S., mais dans le genre bijection simple (je crois que je ne l'ai pas vu passer), il y a bien $z=2^x(1+2y)-1$ qui définit une bijection de |N^2 ver |N puisque tout nombre plus grand que 1 est une puissance de 2 multiplié par un nombre impair. Ce qui donne avec les compositions adéquates toutes les bijections de |N^n vers N.

Posted by: alben

Bonsoir,
Oui, elle n'est pas très éloignée de celle de yos et pas trop difficile à inverser.
En fait, je crois qu'à l'origine, c'était une bijection dont la fonction réciproque ne sois pas facile à déterminer qui était recherchée.

Posted by: pedro_cristian

Citation:

Posté par Imod

Ces interventions avec toute leur complexité me rappellent l'éblouissement que j'ai eu quand j'ai découvert la théorie des cardinaux et ordinaux "les bijections existent" mais de là à les expliciter ... Q en bijection avec N !!!!
Un gros coup de chapeau à Cantor .

Imod

Je trouve que la bijection entre les nombre rééls non transcendants et N est plus impressionnante. (j'espère que je ne dis pas de connerie..)

Posted by: Imod

Citation:

Posté par pedro_cristian

Je trouve que la bijection entre les nombre rééls non transcendants et N est plus impressionnante. (j'espère que je ne dis pas de connerie..)

Oui ( non trancendants = algébriques

) , mais je crois que lorsqu'on a réussi à digérer que N et Q sont équipotents , on est pret pour admettre que N est en bijection avec l'ensemble des nombres algébriques et pour bien d'autres choses .

Imod

Posted by: alben

Bonjour,
Je n'ai pas le souvenir d'une bijection explicite entre les algébriques et N.
As-tu ça pedro_cristian ?

Posted by: pedro_cristian

Citation:

Posté par alben

Bonjour,
Je n'ai pas le souvenir d'une bijection explicite entre les algébriques et N.
As-tu ça pedro_cristian ?

Non non, je n'ai pas le souvenir d'une bijection explicite.

Posted by: yos

Les algébriques sont en bijection avec les polynômes minimaux à coef entiers dont ils sont racines. Il suffit donc de ranger convenablement ces polynômes.
On peut prendre les polynomes $\sum_{k=0}^n a_kx^k$ qui vérifient $n+\sum_{k=0}^n |a_k|=M$ . Ils forment un ensemble fini $E_M$ . Et l'ensemble de ces polynômes est la réunion des $E_M$ , pour M décrivant $\mathbb N$ .
Une réunion dénombrable d'ensembles finis est finie.
Après, cela dépend ce qu'on appelle explicite. Ce qui précède l'est dans la mesure où il est facile d'ordonner chaque $E_M$ . Vouloir une "formule" me semble un peu vain.

Posted by: oss007

Bonjour,
dans l'exemple de zébulon, 7 et 141 , par exemple, n'ont pas d'antécédents.

Posted by: alben

Citation:

Posté par yos

Les algébriques sont en bijection avec les polynômes minimaux à coef entiers dont ils sont racines. Il suffit donc de ranger convenablement ces polynômes.
On peut prendre les polynomes $\sum_{k=0}^n a_kx^k$ qui vérifient $n+\sum_{k=0}^n |a_k|=M$ . Ils forment un ensemble fini $E_M$ . Et l'ensemble de ces polynômes est la réunion des $E_M$ , pour M décrivant $\mathbb N$ .
Une réunion dénombrable d'ensembles finis est finie.
Après, cela dépend ce qu'on appelle explicite. Ce qui précède l'est dans la mesure où il est facile d'ordonner chaque $E_M$ . Vouloir une "formule" me semble un peu vain.

Oui le fait que les algébriques soient dénombrables n'est pas très difficile à démontrer sachant qu'une réunion dénombrable d'ensembles finis ou dénombrables est dénombrable (qui résulte directement du fait que N² est en bijection avec N).
D'accord aussi sur la vanité de la démarche consistant à expliciter la bijection.
Mais est-ce plus vain que la recherche de la sempiternelle convergence d'une série truffée de log et de racines ?

Un point de détail :
Il me semble que les algébriques ne sont pas vraiment en bijection avec les polynomes minimaux à coef entiers, deux algébriques peuvent partager le même polynome minimal.
Ce n'est pas vraiment un argument car il suffit de prendre des coeff premiers entre eux pour la racine la plus faible et ensuite de multiplier par les nombres premiers successifs.
On peut facilement construire une injection dans N avec une technique similaire à celle de la fonction d'Imod

Posted by: Imod

Citation:

Posté par alben

Voilà une démo qui me semble à peu près exhaustive et qui n'est pas très lourde.

Une fois toutes les idées posées , on peut faire bien plus court ( garanti sans histoires de famille ) . $A=\{\frac{p}{q}\in \mathbb{Q}_+^* \text{ irreductible }/ \ \frac{p}{q}\ \notin \ f(\mathbb{N}^*)}$ . Si A est non vide , on peut choisir $\frac{p}{q}$ dans A avec p minimal pour q minimal , nécessairement p>q . En posant $k=ent[\frac{p}{q}]$ et p'=p-kq alors $\frac{p'}{q} \in A$ ce qui est impossible car p'<p .
En effet si $\frac{p'}{q} \ \notin \ A \ \exists \ n \ \in \ \mathbb{N}^* \ / \ f(n)=\frac{p'}{q}$ et alors $f(n.2^k)=\frac{p}{q}$ .

Imod

Posted by: alben

Citation:

Posté par Imod

Oui, j'avais vu qu'on n'était pas obligé de se limiter à ]0;1[. En revanche, construire A directement comme partie de Q et non de N me gêne. Je n'ai pas compris pourquoi p est nécessairement > à q

Posted by: Imod

Citation:

Posté par alben

p>q sinon car $\frac{q}{p}$ et $\frac{p}{q}$ sont simultanément dans A ou hors de A . Je vois bien aussi en quoi te gène le fait de choisir une partie de Q car rien ne garantit l'existence d'un plus petit élément c'est pour çà que je pris soin de prendre q ( entier ) minimal et parmi les $\frac{p}{q}$ avec ce q fixé , p ( entier ) minimal .

Imod

Posted by: alben

D'accord pour l'existence de l'élément doublement mini comme tu viens de le définir.
En revanche je ne comprends toujours pas p>q d'autant que p est le mini. En outre je ne pense pas que tu en ais besoin.
si p>q on arrive à p'<p comme tu l'as fait
si p<q q/p€A avec un q'=p<q
dans les deux cas contradiction.

Posted by: Imod

D'accord il y a contradiction dans les deux cas mais c'est parce que je n'avais pas envie d'étudier les deux cas que je précisais que p>q . Je détaille un peu . $\frac{p}{q} \ \notin \ A \Rightarrow \exists n \ \in \ \mathbb{N}^* \ / \ f(n) = \frac{p}{q}$ . Si n est pair $f(n+1)=\frac{q}{p}$ et si n est impair $f(n-1)=\frac{q}{p}$ donc $\frac{q}{p} \ \notin \ A$ . Alors $\frac{q}{p} \in \ A \Rightarrow \frac{p}{q} \in \ A$ . Si p était plus petit que q , en échangeant le numérateur et le dénominateur on contredirait le choix de q .

Imod

Posted by: alben

OK
Au fait tu la tires d'où cette bijection ? Elle évoque le nombres 2-adiques (dont je ne me souviens plus très bien)

Posted by: Imod

Je ne peux malheureusement pas te dire grand chose sur l'origine de l'exercice , j'ai dû le récupérer sur un forum ou dans un recueil d'épreuves d'olympiades et je l'ai recopié parce que je l'ai trouvé amusant mais je n'ai pas noté la source . Désolé !

Imod