Un peu d'arithmétique

[Doraki]

Existe-t-il deux ensembles A et B d'entiers naturels tels que la fonction
f : A*B -> Z définie par f(a,b) = a-b est une bijection ?

[bfure]

Très rapidement je vais réfléchir cette nuit à la solution :
premier ensemble : Tous les nombres pairs
deuxième ensemble : tous les nombres impairs Et 0

[Ben314]

Salut,
J'ai l'impression que oui, mais j'ai pas écrit la preuve "propre" :
Un énumère Z par exemple sous la forme 0,1,-1,2,-2,3,-3,... puis on fabrique "pas à pas" les ensembles A et B pour ajouter un à un les éléments de Z (s'ils ne sont pas déjà dans A-B).
Je pense qu'en ajoutant à A et B des éléments a,b "suffisament grands" on peut se débrouiller pour ajouter à A-B l'élément de Z manquant sans nuire à l'injectivité de la fonction (a,b)->a-b.


Edit : en regardant un peu plus, j'ai bien l'impression que ça marche, mais c'est pas trop "constructif".
Tu as un exemple "construit" d'un tel couple (A,B) ?

@bfure : tient, c'est bizare, mais j'aurais pas cru qu'il y avait une unique (=bijection) solution à l'équation 1=Pair-Impair...

[Ben314]

Bon, cette fois, j'ai un A et un B "construits" et pas compliqué du tout à définir :
trés joli énoncé ...

[beagle]

il me semble tenir un exemplaire,
à priori à base de:
0,2,5,9,14,...

[Ben314]

il me semble tenir un exemplaire,
à priori à base de:
0,2,5,9,14,...

Donc... ce n'est pas le même que le mien...
S'il y a des "fainéants" : UNE solution (simple) est : (en blanc)
A = entiers ne s'écrivant qu'avec des 0 et des 1 en base 4
B = entiers ne s'écrivant qu'avec des 0 et des 2 en base 4
mais je conseillerais de chercher : c'est... trouvable...

[beagle]

non, c'était faux pour moi.
Il était trop simple.

[Doraki]

Ben, la solution non constructive marche bien, et tu as la même solution constructive que moi.
Donc ça me va.

[beagle]

j'ai une soluce je pense,
faut que je vérifie plus dans les négatifs,
parce que la périodicité des positifs est bien calée,
celle des négatifs cela semble bien marcher, mais cela fait un peu peur au départ.Cela fait le grand écart, mais on retombe bien pour le moment.Je pousse pour voir ...

[Ben314]

De toute façon, la preuve "non explicite" montre qu'il y a une "foultitude" de solutions, mais je ne suis pas sûr qu'il y ait de beaucoup plus simple que celle de Doraki (à la rigueur, on peut remplacer assez simplement le 4 par un 9 ou un 16... voire même un 10, ce qui est effectivement légèrement plus "usuel"...)

[Doraki]

voire même un 10

C'est ma nouvelle solution préférée.

[Ben314]

C'est ma nouvelle solution préférée.

Moi aussi... :zen:

[beagle]

bon c'était encore faux, pour une autre raison.
je vois mieux où sont les différents soucis.
Mais problème il ne me semble pas comprendre la solution de Ben non plus, zut alors.

si, ça va, OK.
C'est super, zètes des bètes.Très joli.

[Ben314]

Je met la "nouvelle solution à la mode" (en blanc) :
A = les entiers ne s'écrivant qu'avec les chiffres 0,1,2,3,4 (en base 10)
B = les entiers ne s'écrivant qu'avec les chiffres 0 et 5 (en base 10)
Variante :
A = les entiers ne s'écrivant qu'avec les chiffres 0,2,4,6,8 (en base 10)
B = les entiers ne s'écrivant qu'avec les chiffres 0 et 1 (en base 10)
Question :
Liste de routes les "variantes" possibles (en base 10 ou en base quelconque) ?

[bfure]

Notons A et B les deux sous ensembles de N solutions du problème

notons a0,a1...an.... les éléments de A
et b0,b1....bn....les éléments de B

tels que

f(a0,b0) =0

et
pour n élément de N*
notons i=2n-1 et p=2n

f(ai,bi)=n
f(ap,bp)=-n

Nous ordonnons les ensembles A et B de tel façon à parcourir Z de la manière suivante
0, 1, 1, 2, -2 etc...

--------------------------------------------------------
1- f(a0,b0) = 0 <=> a0-b0=0 <=> a0=b0

posons a=c alors c appartient à A et à B

Ensemble A : c
Ensemble B : c
posons arbitrairement c=0 (le pb pourrait se généraliser avec c<>0)

2-pour tout k appartenant à N* et selon l'ordre adopté nous cherchons ai, bi, ap, bp tel que

ai-bi =k
ap-bp =-k
=>(ai+ap)=(bi+bp)
notons Sn la somme obtenue



---------------------------------------------------
pour obtenir k et -k

il existe un (n,m) élément de N2 tel que ai=n+k, bi=n, ap=m et bp=m+k

on obtient bien

Ensemble A : 0 n+k m
Ensemble B : 0 n m+k

notons tous résultats des différentes combinaisons entre A et B
1. c-c =0
2. c-n =-n
3. c-m-k =-m-k
4. n+k-c =n+k
5. n+k-n =k
6. n+k-m-k =n-m
7. m-c =m
8. m-n =m-n
9. m-m-k =-k


à ce stade pour que f(a,b) soit bijective il faut que

n<>0 sinon 1.=2.
m<>0 sinon 7.=1.
n<>m sinon 6.=8.=1.
n<>k sinon 2.=9.
m<>k sinon 5.=7.

et n+k<>m et n<>m+k
soit n-m<>k
----------------------------------------------------
cherchons un couple (n,m)pour k = 1

quelquesoit(n,m) élément de N2 tel que n>1, m>1 et n<>m fonctionnent
m<>n-k

par exemple n=2 et m=4

Ensemble A : 0 3 4
Ensemble B : 0 2 5

----------------------------------------------------
cherchons un couple (n,m) pour k = 2

le couple doit vérifier les mêmes conditions que précédemment mais de plus les résultats
des relations doivents être différents des relations trouvés pour k = 1

Il existe une infinité de solutions et bien sur il serait élégant d'optimiser
pour faire vite,
je prendrais n =10^k
et m =100^k

on vérifiera aisément
que les relations 1. à 9. pour k sont différentes des relations 1. à 9. pour k+1 etc...
CQFD

[Doraki]

J'avais cette variante-là :
A = les entiers ne s'écrivant qu'avec les chiffres 0,2,4,6,8 (en base 10)
B = les entiers ne s'écrivant qu'avec les chiffres 0 et 5 (en base 10)

Z/10Z est la "somme" de son sous-groupe isomorphe à Z/2Z et de son sous-groupe isomorphe à Z/5Z.

La solution initiale est tirée du fait que Z/4Z = {0,1} + {0,2}, mais c'est moins joli parceque c'est pas des sous-groupes.

[beagle]

Je ne pouvais jouer dans la mème cours, mais il était possible de chercher plus modestement.
Mais j'ai juste eu le temps de voir quelques ficelles, et j'ai craqué , j'ai regardé vos solutions.
Super.

[nodjim]

Pourquoi n'a t on pas le droit d'écrire: 0.1.3.7.12....?
Le résultat est dans la liste, mais ça reste une bijection, non ?

[Ben314]

Pourquoi n'a t on pas le droit d'écrire: 0.1.3.7.12....?
Le résultat est dans la liste, mais ça reste une bijection, non ?

Je comprend pas trop : ton 0.1.3.7.12.... , c'est les éléments de A ? de B ? ou d'autre chose ?

[Doraki]

Je crois qu'il veut prendre A = B, et avoir une infinité de moyens d'écrire 0 = a-b.