Frobenius, un cas particulier

Sneg · February 2019

Bonjour
À celles et ceux que cela intéresserait, je propose le petit problème suivant.

Si $a$ et $b$ sont deux entiers supérieurs à $1$ et premiers entre eux, quel est le nombre de Frobenius de l'ensemble $\{a, b, ab\}$ ?

Bon divertissement,
Sneg.

reuns · February 2019

https://fr.wikipedia.org/wiki/Problème_des_pièces_de_monnaie

Sneg · February 2019

Bonsoir, reuns.
Et merci.
Mais l'article que tu pointes ne donne pas la réponse au problème posé ici.

Al-Kashi · February 2019

Bonsoir,

Sauf erreur de ma part, il me semble évident que c'est $ab-a-b$.

Al-Kashi

Sneg · February 2019

Bien vu, Al-Kashi. Bravo !
Bonne fin de soirée.

claude quitté · February 2019

Bonjour Snég... (trop difficile à écrire)

Il est bon de ne pas oublier que, de manière structurelle, c'est un semi-groupe de $\N$ (à complémentaire fini), qui possède un nombre de Frobenius. Plutôt qu'une suite d'entiers premiers dans leur ensemble. Et comme $a\N + b\N = a\N + b\N + ab\N$, les deux semi-groupes que l'on voit dans cette égalité possède le même nombre de Frobenius. Vu que ces deux semi-groupes ne font qu'un.

Do you see what I mean ?
C'est juste une petite remarque.

Sneg · February 2019

Bonjour, claude quitté,

Bien sûr, appelle-moi comme tu préfères.
Un jour, tu m'as écrit que le pseudonyme "Snégourotchka" était trop compliqué. Tu n'as pas été le seul à me le dire. Alors, pour faciliter la vie de tout qui voulait m'écrire, j'ai aussitôt introduit une demande pour faire changer "Snégourotchka" en "Sneg" tout court. Mais cette demande n'a pas abouti. Je ne sais pas pourquoi. Peut-être parce que j'avais déjà changé une fois de pseudonyme, de "Gil Bill" en "Snégourotchka", peu de temps auparavant.

Pour ce qui est du sujet de ce fil, j'avoue que j'ai un peu honte de moi. C'est sans doute dû à l'euphorie du 14 février. Ma question ne présente évidemment pas le moindre intérêt. Merci malgré tout à reuns, Al-Kashi et à toi-même d'avoir bien voulu prendre la peine de me répondre. C'est très gentil.

Sneg

Poirot · February 2019

Souhait exaucé.

Sneg · February 2019

Un grand merci !
:-)

Sneg · February 2019

Bonjour,

Afin de me racheter de mon problème précédent, sans intérêt, je vous propose ci-dessous un autre problème, que j'espère un peu plus consistant. Il s’intitule «Conditions exceptionnelles !».
Le voici :

Considérons l'expression $mx+ny$, où $m$ et $n$ sont deux variables entières parcourant respectivement l'intervalle $[0;96]$ et l'intervalle $[0;102]$.

Quand on donne à $x$ et à $y$ une valeur entière, on obtient $9991$ additions différentes dont on peut, plus ou moins facilement selon les valeurs attribuées à $x$ et à $y$, calculer les $9991$ résultats. Justement, intéressons-nous à ces $9991$ résultats :

Si l'on veut - condition 1 - que le résultat de chacune des $9991$ additions soit congru modulo $9991$ à une valeur entière comprise entre $0$ et $9990$ distincte des $9990$ autres, il suffit de poser : $x\equiv 1$ et $y\equiv 97\pmod{9991}$.

Si l'on veut - condition 2 - que le résultat de l'addition où $m$ et $n$ ont la valeur la plus grande, c'est-à-dire $96x+102y$, soit congru modulo $9991$ à $2019$, il suffit de poser : $x\equiv 329$ et $y\equiv 4\pmod{9991}$.

Mais quelle valeur donner à $x$ et à $y$ si l'on veut que les deux conditions soient satisfaites ensemble ?

En croisant les doigts, je souhaite à celles et ceux qui seront intéressés un bon divertissement.
Sneg.

babsgueye · February 2019

En feuilletant mes écrits, j'ai retrouvé ces deux propositions que je n'ai pas encore le temps de vérifier, encore moins de démontrer.

Proposition1 : pour $a\in\mathbb{N}^*$, le nombre de Frobenius de $(a; 2a+1; 2a+2)$ est $(a-1)\times a$, si $a$ impair et $a^2$ si $a$ pair.

Proposition2 : pour $a\in\mathbb{N}^*$, le nombre de Frobenius de $(a; 2a-1; 3a-2)$ est $2(a-1)^2 - \lfloor\frac{a-1}{2}\rfloor\times a$

Qu'en penses-tu ?

Sneg · February 2019

Bonjour, babsgueye,

Je n'ai pas testé la proposition 2, mais je peux dire que je ne suis déjà pas d'accord avec la proposition 1.
En effet :
Pour $a=3$ : $g(3, 7, 8)\neq (3-1)\times3$
et
Pour $a=2$ : $g(2, 5, 6)\neq 2^2$

Bonne après-midi.

lourrran · February 2019

Je pense que vous n'avez pas la même définition du nombre de Frobénius.
Pour Sneg, FS(a,b,c) ne peut pas s'écrire comme combinaiseon linéaire à coefficients positifs de (a,b,c), et c'est le plus grand entier ayant cette propriété.
Pour Basbsgueye, FB(a,b,c) peut s'écrire comme combinaison linéaire à coefficients positifs de (a,b,c) ; FB(a,b,c) =FS(a,b,c)+1.

C'est évident que a(a-1) ou a² ne peut pas être le nombre de Frobénius de (a,b,c), avec la définition de Sneg.

Sneg · February 2019

Bonjour, lourrran,

Personnellement, je me réfère à la définition du "nombre de Frobenius" telle qu'elle est énoncée sur la page Wikipédia intitulée "Problème des pièces de monnaie", d'ailleurs pointée plus haut par reuns.

Si tu dis vrai, et sans vérification de ma part, alors la vision de babsgueye correspondrait à la définition du "problème de Frobenius" tel qu'il est énoncé sur la page du cnrs-images des mathématiques intitulée "Semigroupes numériques et conjecture de Wilf", écrite par Shalom Eliahou, paragraphe "Le problème de Frobenius" (notion de seuil critique…).

Si je cite ces sources, c'est juste pour qu'on ait les idées claires.

Cela dit, le problème intitulé "Conditions exceptionnelles !", pour lequel j'avais créé un nouveau fil mais qui a été déplacé à l'intérieur de ce fil-ci consacré à Frobenius, n'a rien du tout à voir avec le nombre de Frobenius. C'est dommage. Il y a un risque évident de confusion.

babsgueye · February 2019

@Sneg et @lourrran c'est bien ça, nous n'avons pas la même définition. Je l'avais remarqué auparavant, mais oublié de le noter à @Sneg. D'ailleurs c'est l'article de Shalom Eliahou dont parle @Sneg que j'ai lu.

nodgim · February 2019

Salut Snegorouskaïa, ô fille du Père Noël vénérée par la très grande et très sainte Russie éternelle.

Une petite remarque sur ton énigmatique question :

Si 96 * 329 + 102 * 4 vaut bien 2019 [9991], 329 et 4 ne sont pas des solutions modulo 9991. On s'en rend compte en écrivant :

96 * ( 329 - 102k) + 102 ( 4 + 96 k ) = 2019 [9991]

qui donne comme autres solutions positives ( x, y ) = (231, 100) ou ( 129, 196) et (27,292).

Cela étant dit, je n'ai pas compris ce que tu demandais.

Sneg · February 2019

Bonjour, nodgim,

Quelle envolée lyrique ! Mais je préférerais, s'il te plaît, que tu me voies comme la petite-fille de Ded Moroz, ... pas sa fille ! :-( :-)

(A propos, est-il possible avec LaTeX d'écrire en alphabet cyrillique ? J'ai déjà essayé, ça ne marche pas.)

Pour en venir au problème, c'est simple. Imagine le fameux tableau à deux entrées que tu utilises pour trouver le nombre de Frobenius lié à trois entiers (encore ce Frobenius !?!) :
En abscisses, de gauche à droite, les multiples de x, soit : 0x, 1x, 2x, 3x, … , jusqu'à 96x,
En ordonnées, de bas en haut, les multiples de y, soit : 0y, 1y, 2y, 3y, … , jusque 102y,
avec, dans la case inférieure gauche du tableau, aussi bien 0x que 0y. Et dans toutes les autres cases du tableau, on trouve une addition : l'addition du multiple de x et du multiple de y qui s’entrecroisent horizontalement et verticalement.
Une fois qu'une valeur entière aura été affectée à x et à y, chaque case pourra contenir une valeur, produit ou somme, qui sera ici ramenée à une valeur comprise entre 0 et 9990, car calculée "modulo 9991" (pour autant que tout ceci ait un sens aux yeux des mathématiques officielles. C'est pour ça que, dans l'énoncé du problème, j'ai plutôt abordé la question sous l'angle plus officiel des congruences).Tu as fait ce genre de tableau des dizaines de fois, je parie.

Résoudre le problème revient à trouver x et y de façon que :
1) chacune des 9991 cases du tableau contienne une valeur différente des autres.
2) la case supérieure droite du tableau contienne la valeur 2019.

Dresser le tableau à la main serait presque irréalisable. En tout cas fastidieux. Il faut donc trouver un raisonnement prouvant que les valeurs données à x et à y remplissent le tableau comme souhaité.

Remarque que, puisque chaque case du tableau contient un résultat différent des autres, ce tableau rectangulaire ne contient qu'un seul zéro, dont tu devines l'emplacement.

J’espère que mon explication est claire. Ce n’est pas facile d’expliquer le principe du tableau à double entrée avec des mots. Cela aurait finalement été plus facile de dresser directement le tableau avec LaTeX.

Sneg.

Frobenius, un cas particulier

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 9