Frobenius inversé et le coffret magique

Salut.
Je ne sais pas si j'ai trop bien compris ta question, mais $$22 + 22 + 25\times 79$$ donne combien ? $$2019$$

Ah ! je n'ai pas tenu en compte le fait que a, b et c doivent être premiers deux à deux, mais ce n'est pas aussi dans le texte de @Snegourotcha

Considère l'équation diophantienne d'inconnue $(x_1,\dotsc,x_n) \in \mathbb{N}^n$
$$a_1 x_1 + \dotsb + a_n x_n = N$$
où $a_1,\dotsc,a_n$ sont des entiers naturels non nuls premiers dans leur ensemble et $N \in \mathbb{Z}_{\geqslant 1}$. On montre que cette équation a toujours une solution dans $\mathbb{N}^n$ pour $N$ suffisamment grand. Cela conduit à la définition suivante :

Définition. On appelle nombre de Frobenius le plus grand entier $N$ pour lequel cette équation n'a pas de solution dans $\mathbb{N}^n$. Cet entier est noté $g(a_1,\dotsc,a_n)$, notation due à Frobenius. Déterminer cet entier en fonction de $a_1,\dotsc,a_n$ s'appelle le problème de Frobenius.

Lorsque $n=2$, on pense que c'est Frobenius qui fut le premier à montrer que $g(a_1,a_2) = a_1 a_2 - a_1 -a_2$.

Lorsque $n > 2$, le problème devient ardu dans le cas général, même si certains cas particuliers ont été traités, par exemple lorsque les $a_k$ sont en progression arithmétique.

Il s'agit ici de déterminer trois entiers $a,b,c$ premiers dans leur ensemble tels que $g(a,b,c) = 2019$ avec $21 < a,b,c < 2019$.

Des résultats récents sont sortis pour le cas $n=3$, mais difficiles à appliquer si l'on n'a pas de renseignements supplémentaires sur $a,b,c$.

Bonsoir Noix de totos,

Pourrais-tu nous donner un lien sur les résultats récents dont tu parles. Merci.

Al-Kashi

Pour les lecteurs de ce fil, je pense qu'il serait intéressant de voir les calculs de $g(22,115,1121)$, $g(22,115,1351)$ et $g(22,115,1581)$,...

@Al-Kashi : une référence possible

A. Tripathi & S. Vijay, On a Generalization of the Coin Exchange Problem for Three Variables, J. Integer Sequences 9 (2006), Art. 06.4.6.

Encore une fois : c'est bien de donner des solutions, c'est encore mieux de montrer qu'elles conviennent.

En ce qui me concerne, je sais calculer des $g(a,b,c)$ à la main, mais ce n'est peut-être pas le cas de tout le monde.

J'invite donc à ce que les gens ci-dessus fournissent les détails, sinon ce fil n'aura pas un grand intérêt...

Salut et bonne année. Une façon d'y faire en générale, on se donne $F$ le nombre de Frobenius on résout (trouve) $x$ tel que $F+x+1=0 \pmod{ x-1}$ soit $F+x+1=(x-1)\alpha $ avec $x<\alpha+1$. Le semigroupe candidat sera $\langle x,\alpha+1, F+x\rangle$. Pour $2019 $ j'ai trouvé $\langle 44,49,2063\rangle$. Ce n'est pas exigeant mais ça marche.

Si on considère $x>\alpha+1$ on aurait $F$ comme nombre pseudo-Frobenius.

Oui, $\langle 44,49,2014\rangle$ marche en effet si vous voulez vérifier Wolfram https://www.wolframalpha.com/widgets/view.jsp?id=537b594c0c49cf9608f2b33e005f5522

Tu peux offrir un trésor à qui ouvre la clé pour un semigroupe à $4$ éléments $\langle a,b,c,d\rangle $, $F(S)=2019$, à plutard. (tu)

Personnellement, pour trouver la solution, j'ai utilisé la force brute de l'informatique. Un truc comme ça :

Pour i = 22 a 2018
   Pour j = i+1 a 2018
       si premier_2a2(i,j) alors 
           pour k = j+1 a 2018
               si premier_2a2( i,k) et premier_2_a2 (j,k) alors 
                   ok = vrai
                   si decomposable( 2019, i,j,k) = vrai  alors ok = faux
                   pour n = 2020 a 2019 + i
                         si ok = vrai alors ok = decomposable ( n, i,j,k )
                    fin
                    si ok alors info ( "solution trouvee", i,j,k)
                 fin
              fin  // boucle sur k
           fin   // si i premier avec j 
      fin  //  boucle sur j
fin // boucle sur i

On pouvait anticiper qu'il y aurait plein de solutions.
Des triplets (i,j,k) premiers 2 à 2, avec i,j,k entre 22 et 2019 il y en a 'beaucoup', plusieurs dizaines de millions.
Et le nombre de Frobenius d'un tel triplet, c'est souvent un nombre entre 2000 et 20000. Dans les grandes masses, on peut estimer que pour chaque nombre $N$ entre 2000 et 20000, le nombre de triplets qui vont donner $N$ est supérieur à 100.

@Snégourotchka : il est préférable, en mathématiques, de démontrer plutôt que d'affirmer, c'est plus intéressant pour le lecteur. Un algo est aussi un bon moyen de présenter les choses.

Il existe maintenant, dans la littérature, des méthodes de calculs explicites de $g(a,b,c)$. Voir par exemple l'article qu'Al-Kashi a fourni plus haut, et dont l'auteur s'est spécialisé depuis plusieurs années dans le problème de Frobenius.

En utilisant le Théorème 3 de ce papier, on a successivement (avec ses notations) $k=9$, $\ell = 13$, $q=2$ et $r=4$. On a donc bien $\ell > k$ et $br = 460 < cq = 2242$. De plus, $\lambda = 0$, de sorte que
$$g(22,115,1121) = -22 + 115 \times( 22-13-1)+1121 \times (2-1) = 2019.$$

Snégourotchka écrivait:

---

> Sans condition particulière sur $a,b,c,d$ ?
> Alors $(11, 55, 203, 1015)$.

55 étant un multiple de 11, on pourrait réduire cette proposition à $(11, 11, 203, 1015)$
Et du coup, plutôt que chercher une nouvelle solution, on aurait pu garder la solution de la première énigme : $(22, 22, 115, 1121)$ , ou encore $(22, 44, 115, 1121)$

Il y a une formule qui permet de trouver F(a,b,c), connaissant a b et c ... Peut-être , je ne la connais pas, mais admettons que cette formule existe.
Ca ne suffit pas. On va devoir balayer plein de triplets (a,b,c) avant de tomber sur 2019.

Ici, on cherchait l'inverse. Connaissant F(a,b,c) = 2019, trouver (a,b,c).
Avant de me résoudre à un programme informatique brutal, j'ai voulu trouver une solution analytique, et il y a des pistes.
Avec 2 nombres premiers entre eux, on trouve facilement que $F(a,b) = (a-1)*(b-1)-1$

Si on cherche a,b,c tels que $F(a,b,c) = 2019$, alors, nécessairement , a et b vérifient $F(a,b) >= 2019$ Et avec les autres contraintes qu'on a sur a <b < c < 2019, on peut même dire $F(a,b)>2019$

On va introduire une nouvelle notation $F_i, _j (a,b) = F(a,b) -ia-jb$

L'ensemble des $F_i,_j (a,b)$ est donc l'ensemble des entiers qui ne peuvent pas être décomposés en combinaison linéaire de a et b.

Si $F(a,b,c) =2019$ , 2019 doit donc faire partie de cet ensemble des $F_i,_j (a,b)$ . Et dans mon idée, 2019 devait être égal à $F_i,_j (a,b)$, avec i et j relativement petits.
Dans les faits, si on prend la solution (22,115,1121), $2019 = F(22,115) -17*22 = F_i,_0 (22,115)$ avec i=17 ! et je n'ai pas poussé l'exploration manuelle jusqu'à ce nombre 17.

Si on cherche (a,b), tels que $F_1,_0 (a,b) = 2019$ , ça revient à chercher $F(a,b) = 2019 + a$
donc : $(a-1)*(b-1)-1 = 2019 + a$
donc : $(a-1)*(b-2)=2019$

Pas de chance , si on décompose 2019 en facteurs premiers, on trouve $2019 = 3*673$, et donc , avec la contrainte $22<= a<b$, cette piste mène à une impasse.


Manuellement, j'avais cherché aussi a et b , tels que $F_3,_0(a,b) = 2019$ ; on arrive à $a=34$ et $b=65$ si je me souviens bien (avec la contrainte a et b premiers entre eux, sinon on a plus de solutions), mais ça mène aussi à une impasse (ou en tout cas, je n'ai pas su trouver c manuellement à partir de ces 2 valeurs a=34 et b=65).

J'ai abandonné cette piste, pour en prendre une autre plus brutale.

Si on poursuit cette piste, et qu'on cherche (a,b), tels que $2019 = F_i,_j(a,b)$ avec $i=17$ et $j=0$ , ça revient à chercher (a,b) tels que
$(a-1)*(b-18) = 2019+18$
Or 2037 se décompose en 3*7*97, et ça nous donne bien a=22, b= 115 ... Et il reste à voir si on trouve une valeur de c qui va convenir. La démarche nous aurait finalement donné la réponse, mais c'est très long.

babsgueye
D'une erreur de calcul

Ca ne change pas fondamentalement la démarche ... et en l’occurrence, ça ne change pas l'idée : la démarche est longue et on n'est pas sûr d'aboutir à un résultat.

[Inutile de recopier le dernier message. AD]

@ Sneg :

Je ne comprends pas bien ta dernière intervention. Car avec tout couple (a,b) de nombres premiers entre eux, tu peux obtenir n'importe quel entier relatif sous la forme ax+by si x et y sont des entiers relatifs.

Moi ce qui m'étonne est que pourquoi vous parlez de Frobenius en ne restant pas dans $\mathbb{N}$ ? Ce $-1$ qu'est ce que ça fait ici .

Si on s'autorise les coefficients négatifs, la notion de nombre de Frobenius disparaît ; dès que a,b,c sont premiers entre eux, tout entier n peut s'écrire sous la forme $n= xa+yb+zc$ avec x,y,z éventuellement négatifs. Donc je ne vois pas ce qu'on cherche.

Soit, mais recenser les décompositions linéaires de 22, 115 et 1121 qui donnent 2019, en quoi ça fait avancer la réflexion ? Si Basbeygue t'a posé cette question quasi similaire, c'est que lui non plus ne voit pas où tu veux aller.

Tu tombes sur 3 combinaisons linéaires... ...
La propriété commune de ces 3 combinaisons linéaires, c'est de donner g(22,115,1121), c'est bien ça ?
En voici une 4ème : g(22,115,1121) = 222*22+0*1121-23*115

Donc la coïncidence en question n'est pas une coïncidence.

@ Sneg :

Je commence à comprendre ce que tu veux dire.

2019 n'est pas accessible par une combinaison 22x + 115y + 1121z. 2019 n'est pas divisible par 22. Or 2019 + 22 est accessible par une combinaison 22x + 115y + 1121z. Si cette combinaison devait comporter un coefficient non nul pour 22, alors (2019 +22) -22 = 2019 serait accessible et donc ne serait pas le Frobénius.
Il est donc normal que 2019 + 22 soit une combinaison 115y + 1121z.

Même démarche pour montrer que 2019 + 115 = 22x + 1121y et 2019 + 1121 = 22x + 115y.

Si j'ai bien compris ce qui te chagrinait.

Mais alors:

$g(22, 115, 1121) + 22 = 115\times 8 + 1121\times 1 = 2041$, $8$ étant $\leq 22$, et $m\times 22\neq n\times 115$ pour $n\leq 7$ et $m\lt 7$,je ne vois pas en quoi Tripathi fait avancer le schmilblick !

Je reviens sur les décompositions $2019=80*22+12*115-1121$ , et les 2 autres formules similaires.
En fait, je suis tenté d'écrire plutôt $2019+1121=80*22+12*115$ Et c'est une conséquence directe de la définition du nombre de Frobenius.
Je m'explique.
Soit un triplet (a,b,c) (ici 80, 115 et 1121)
Condition : le pgcd de (a,b,c) doit être égal à 1, sinon, on le sait, le nombre de Frobenius n'est pas défini.
Et on va conventionnellement considérer $a<b<c$ .
Soit N = g(a,b,c) = le nombre Frobenius du triplet (a,b,c).
Par définition, il n'existe aucun triplet d'entiers positifs ou nuls (x,y,z) tels que $xa+yb+zc=N$
Mais pour tout M strictement supérieur à N, il existe un triplet d'entiers positifs ou nuls (x,y,z) tel que $xa+yb+zc=M$

En particulier, regardons une valeur particulière de M : M=N+a ( $M=2019+22=2041$ dans notre exemple)
Donc par définition, il existe (x,y,z) tel que $xa+yb+zc=M$

Quelles sont les valeurs possibles pour x ? En particulier, x peut-il être différent de 0 ?
Raisonnons par l'absurde : si $M=xa+yb+zc$, avec x>0, alors $M-a=(x-1)a+yb+zc$
Or, $M-a$ , c'est notre nombre $g(a,b,c)$ , on aurait donc trouvé une décomposition de g(a,b,c) avec des coefficients (x-1,y,z), tous positifs ou nuls. C'est contraire avec la définition du nombre de Frobenius.

Conclusion. g(a,b,c)+a peut être écrit sous la forme xa+yb+zc , avec x nul et (y, z) positifs ou nuls.
Autrement formulé :

g(a,b,c) peut être écrit sous la forme yb+zc-a , avec (y, z) positifs ou nuls.
Et idem avec b ou c :
g(a,b,c) peut être écrit sous la forme xa+zc-b , avec x et z positifs ou nuls.
g(a,b,c) peut être écrit sous la forme xa+yb-c , avec x et y positifs ou nuls.

On a donc nos 3 décompositions avec à chaque fois un coefficient égal à -1, et les 2 autres coefficients positifs ou nuls.
Ici, j'ai détaillé la démonstration pour g(a,b,c) (3 nombres donc), mais la même démonstration est totalement valable pour g(a,b,c,d) ou pour g(a,b,c,d,e) etc etc

On a au moins 3 façons d'écrire g(a,b,c), avec à chaque fois un des coefficients égal à -1, et les 2 autres coefficients positifs ou nuls. Y a-t-il uniquement ces 3 décompositions, ou y en a-t-il plus ?

Là, je n'ai pas de démonstration complète, juste des ordres de grandeurs, des conjectures.

Si c est suffisamment grand, alors il y a plusieurs décompositions. Dès que c est supérieur à g(a,b)-a, g(a,b,c) est égal à g(a,b). Je n'ai pas vérifié, mais je pense que à partir de ce seuil, on a au moins 4 décompositions sous la forme voulue, et non plus 3. Il semblerait qu'en dessous de ce seuil, on ait seulement 3 décompositions.
Oublions la question sur l'unicité.

On a démontré que g(a,b,c) peut-être écrit à la fois sous la forme yb+zc-a, ou xa+zc-b ou xa+yb-c. $g(a,b,c)$ est probablement le plus petit entier qui vérifie ces 3 propriétés, et c'est probablement une piste pour déterminer g(a,b,c), ou plus généralement, pour déterminer $g(a_i, i=1 ,\ldots, n)$