Frobenius problem

Imaginez des pièces de 4 et 7 unités, disponibles en quantité illimitée. Certaines sommes sont possibles : 8 avec deux pièces de 4, ou 15 avec deux pièces de 4 et une de 7. D'autres résistent, comme 17.

Le problème de Frobenius cherche la dernière somme impossible. Avec 4 et 7, c'est 17 : toutes les sommes entières à partir de 18 peuvent être formées. Les quantités de pièces peuvent être nulles, mais jamais négatives.

Le problème de Frobenius porte sur une liste de nombres entiers strictement positifs, notés a₁, a₂, …, a_n. Il demande le plus grand entier impossible à obtenir en additionnant des multiples entiers positifs ou nuls de ces nombres. Si k₁, …, k_n désignent les nombres de fois où chaque valeur est utilisée, une somme représentable a la forme $k_1{a}_1+k_2{a}_2+\cdots +k_n{a}_{n}k\_1a\_1+k\_2a\_2+\backslash cdots+k\_na\_n$, avec chaque coefficient k_i supérieur ou égal à zéro. Le plus grand entier non représentable, lorsqu'il existe, est le nombre de Frobenius. On rencontre aussi les noms problème des pièces de monnaie, problème du numismate et nombre de Sylvester–Frobenius.

L'existence d'un dernier entier impossible suppose que le PGCD de toutes les valeurs soit 1. Pour une seule valeur, cette condition impose a₁ = 1 : tout entier positif est alors représentable et aucun nombre de Frobenius n'existe. Pour deux valeurs a₁ et a₂ premières entre elles, Sylvester a établi en 1884 la formule $g(a_1,a_2)=a_1{a}_2-a_1-a_{2}g(a\_1,a\_2)=a\_1a\_2-a\_1-a\_2$. Pour trois valeurs ou davantage, il n'existe pas de formule générale fermée, mais le nombre peut être calculé par des algorithmes efficaces.

On dispose de valeurs 4 et 7, dont le PGCD vaut 1. Les coefficients cherchés sont deux entiers positifs ou nuls : le premier compte les 4 et le second compte les 7. La formule de Sylvester annonce $4\times 7-4-7=174\backslash times7-4-7=17$.

1. Vérifions l'impossibilité. Avec zéro, une ou deux fois 7, les restes à former avec des 4 sont respectivement 17, 10 et 3. Aucun n'est un multiple de 4. Trois fois 7 dépassent déjà 17 : la somme 17 est donc impossible.

2. Formons quatre sommes consécutives : $18=7+7+4,19=7+4+4+418=7+7+4,\backslash quad19=7+4+4+4$, puis $20=4+4+4+4+4,21=7+7+720=4+4+4+4+4,\backslash quad21=7+7+7$.

3. Toute somme suivante s'obtient en ajoutant encore 4 à l'une de ces quatre sommes, selon son reste dans la division par 4. Ainsi, tous les entiers à partir de 18 sont représentables. Le contrôle confirme que 17 est bien le nombre de Frobenius de 4 et 7.

Avec deux formats de lots premiers entre eux, la formule de Sylvester donne immédiatement le dernier total impossible. Pour des lots de 4 et 7 objets, le seuil est 17 ; à partir de 18 objets, chaque total entier est réalisable.

Avant tout calcul, le premier geste consiste à vérifier le PGCD des tailles disponibles. S'il n'est pas égal à 1, chercher un dernier total impossible n'a pas de sens, car tous les entiers qui ne sont pas multiples de ce PGCD restent inaccessibles.

Avec trois tailles ou davantage, la formule réservée à deux valeurs ne convient plus. Il faut employer un algorithme de calcul et contrôler les représentations obtenues, puisque la source ne donne aucune formule générale fermée dans ce cas.

Une combinaison linéaire autorise, selon le cadre, des coefficients entiers négatifs. Dans le problème de Frobenius, les coefficients sont obligatoirement des entiers positifs ou nuls. Ainsi, 3 = 7 − 4 est une combinaison avec un coefficient négatif, mais pas une représentation admise avec les valeurs 4 et 7.

Le nombre de Frobenius n'est pas le plus petit entier non représentable. Avec 4 et 7, 1 est déjà impossible, mais 17 est le plus grand entier impossible ; tous les entiers supérieurs sont représentables.

Si le PGCD des valeurs dépasse 1, il reste une infinité d'entiers non représentables : tous ceux qui ne sont pas multiples de ce PGCD. Le symptôme est donc l'absence de dernier entier impossible. Il faut d'abord vérifier que le PGCD vaut 1.

Avec une seule valeur et un PGCD égal à 1, cette valeur est nécessairement 1. Tous les entiers positifs sont alors représentables : le nombre de Frobenius n'existe pas, même si la condition sur le PGCD est satisfaite.

La formule de Sylvester ne couvre que deux valeurs premières entre elles. L'appliquer à trois valeurs ou davantage est un mauvais raccourci ; dans ce cas, il faut utiliser un algorithme de calcul.

Les coefficients peuvent valoir zéro. Exiger qu'ils soient tous strictement positifs changerait le problème : la représentation 8 = 2 × 4 utilise zéro fois la valeur 7 et reste parfaitement admise.

Combinaison linéaire précise le rôle des coefficients et aide à comprendre pourquoi leur signe change la question.

Premiers entre eux éclaire la condition imposée aux deux valeurs dans la formule de Sylvester.

PGCD permet de tester la condition d'existence d'un plus grand entier non représentable.