Viens voir mes nuggets

Attention: l’article qui va suivre est parrainé par le site mangerbouger.fr. L’abus de mathématiques n’est absolument pas dangereux pour la santé et est vivement encouragé.

Un des produits phare d’une grande chaîne de restauration rapide sont les nuggets de poulet (aussi appelées croquettes de poulet par nos chers amis canadiens). Ils sont vendus en France dans des boites de 4, de 6 ou de 9 si j’en crois le site officiel de la gastronomie fine. Imaginons un client particulièrement chiant (nous dirons plutôt soucieux de son apport calorique quotidien) qui déciderait aujourd’hui de ne consommer que 11 de ces nuggets. La caissière du McDo va-t-elle devenir folle lorsqu’elle devra lui donner sa commande ?

Une équation diophantienne

Formulons le problème de manière plus mathématique. Etant donné un entier naturel n, à quel condition est-il possible de trouver une décomposition de n de la forme 4x +6y+9z=nx,y et z sont des entiers naturels ?

Il est clair que si n vaut 1, 2 ou 3 alors on ne pourra jamais trouver de telle décomposition. Autrement dit, il est impossible de commander 1, 2 ou 3 nuggets exactement dans ce fast-food. C’est soit 4, soit rien. Pas de demi-mesure. A la rigueur un petit jouet avec, mais c’est tout. En revanche, on peut tout à fait obtenir 14 nuggets en commandant deux boites de 4 et une boite de 6 (d’après la décomposition 14=4 \times 2 + 6 \times 1 + 9 \times 0).

Nous allons résoudre l’équation diophantienne 4x +6y+9z=n et voir si cette pauvre caissière pourra bel et bien fournir 11 nuggets exactement à notre client affamé. On pourra même dire s’il est possible d’obtenir 473 nuggets exactement.

Ménage à trois

L’équation précédente est une équation diophantienne du 1er degré à trois inconnues. Elles sont plus techniques à résoudre que celles classiques à deux inconnues (c’est-à-dire celles du type ax+by=c qu’on apprend à résoudre en Terminale S normalement) mais elles ne sont pas si dures que cela si on s’y prend bien. Cependant, j’ai rarement vu de textes expliquant la résolution d’une équation diophantienne du 1er degré à 3 inconnues, donc c’est l’occasion pour nous de détailler une méthode.

Soit n un entier naturel fixé.  Avant de revenir à notre problème de Nuggets, nous allons commencer par résoudre l’équation 4x +6y+9z=n dans \mathbb{Z} (c’est-à-dire que les solutions x,y et z sont des entiers relatifs). L’avantage dans \mathbb{Z}, c’est qu’on sait que l’équation 4x +6y+9z=n admet au moins une solution (x_0,y_0,z_0) (par exemple, le triplet (n;n;-n) est une solution particulière). Pour donner la forme explicite des solutions, nous allons successivement résoudre deux équations du 1er degré à deux inconnues. Pour ceux qui ne se souviendraient plus comment elles se résolvent, vous pouvez consulter cette page.

Résolution de l’équation

Commençons par remarquer que notre équation est équivalente à 2(2x +3y)+9z=n. Donc, si on pose X=2x+3y (habile changement de variable !), nous nous retrouvons à résoudre l’équation 2X+9z=n.

Comme 2 et 9 sont premiers entre eux, cette dernière équation admet des solutions qui s’obtiennent à partir de solutions particulières. Nous avions dit plus haut (faut suivre !) qu’il existe au moins un triplet d’entiers relatifs (x_0,y_0,z_0)  qui est solution, c’est-à-dire tel que 4x_0 +6y_0 +9 z_0 = n. Ainsi, 2(2x_0+3y_0)+9z_0 =n. Donc, le couple (2x_0+3y_0, z_0) est une solution particulière de l’équation 2X+3z=n. On en déduit la solution générale de cette équation: ce sont les couples (X,z) tels que

\exists k \in \mathbb{Z}, \, \begin{cases}  X = (2x_0+3y_0) + 9k \\  z = z_0 -2k \\  \end{cases}

A partir de là, l’idée est d’exprimer les entiers x et y à partir de X en résolvant l’équation 2x+3y=X (où X est fixé). Il s’agit là aussi d’une équation diophantienne, et comme 2 et 3 sont premiers entre eux, elle admet des solutions. On remarque que (5X,-3X) est une solution particulière (car 2(5X)+3(-3X) =X) et donc (x,y) est solution de l’équation 2x+3y=X si, et seulement si:

\exists m \in \mathbb{Z}, \, \begin{cases}  x = 5X + 3m \\  y= -3X -2m \\  \end{cases}

On remplace X par l’expression que nous avions trouvé précédemment (X=2x_0+3y_0+9k): si (x,y,z) est une solution de l’équation 4x + 6y +9z=n alors:

\exists k \in \mathbb{Z} , \exists m \in \mathbb{Z}, \, \begin{cases}  x = 10x_0 + 15y_0 + 45k + 3m \\  y = -6x_0 - 9y_0 -27k -2m \\  z = z_0 - 2k\\  \end{cases}

On peut finir en remplaçant x_0, y_0 et z_0 par n, n et -n, ce qui nous donne:

\exists k \in \mathbb{Z} , \exists m \in \mathbb{Z}, \, \begin{cases}  x = 25n + 45k + 3m \\  y = -15n -27k -2m \\  z = -n - 2k\\  \end{cases}

Comme nous avons procédé uniquement par conditions nécessaires, il faut vérifier que si on remplace x,y et z par leurs valeurs dans l’expression 4x+6y+9z alors on trouve bien n. Je vous épargne le calcul, je l’ai fait à votre place, et si vous me faites confiance (ce qui est le cas si vous avez lu cet article jusqu’à ce point-ci) alors vous comprenez que nous avons décrit l’ensemble des solutions de cette équation diophantienne à trois variables (et un paramètre — n).  Je vous encourage cela dit à faire cette vérification, car c’est tellement magique de voir tous ces termes s’annuler pour ne laisser à la fin que ce petit n tout seul…

Revenons à nos nuggets

Bon, c’est pas tout, mais ce qui nous intéresse, ce sont les nombres n pour lequels il y a des solutions (x,y,z) qui sont positives. L’idée va être d’attacher à chaque n une solution (x,y,z) qui caractérisera le fait qu’il y a des solutions positives ou non. Si pour l’instant, cela reste flou, c’est normal, car personne de sensé ne peut comprendre cette phrase à ce stade de l’article.

On commence par démontrer la proposition suivante:

Soit n \in \mathbb{N}. Il existe une unique solution (x;y;z) à l’équation 4x+6y+9z=n telle que: 0 \leq y \leq 1  et 0 \leq z \leq 1.

L’explication est très simple et se base sur la forme des solutions qu’on a donné auparavant. Commençons par z: on sait qu’il est de la forme z=-n - 2k k \in \mathbb{Z} (rappelons que n est fixé). Si on réécrit cette égalité, on a donc -n= 2k + z. Là, vous allez me dire que je me fous de votre gueule. Mais non voyons ! Car si on impose que 0 \leq z \leq 1, l’égalité -n = 2k + z devient alors la division euclidienne de -n par 2. Ainsi, k est nécessairement le quotient de cette division dont on sait qu’il est unique. Ainsi, il n’y qu’un seul z tel que 0 \leq z \leq 1.

L’unicité de y se fait de la même façon: on vient de voir qu’il n’y a qu’un seul k pour lequel z est compris entre 0 et 1. On fixe donc ce k et on va chercher pour quel m le nombre y= -15n -27k -2m est compris entre 0 et 1. Si on réécrit la relation précédente, on voit que -15n-27k=2m + y. Donc, 0 \leq y \leq 1 si, et seulement si y est le reste de la division euclidienne de -15n-27k par 2 et dans ce cas, l’unique nombre m correspondant est le quotient de cette division. D’où l’unicité de y.

A partir de là, nous avons quasiment fini. Voici la caractérisation (très attendue) des nombres n pour lequels il n’est pas possible de servir des nuggets:

L’ensemble des nombres n tels que l’équation 4x+6y+9z=n n’admet aucune solution positive est
\{ 4x+6y+9z \text{ tel que } x <0 , 0 \leq y \leq 1 , 0 \leq z \leq 1 \}

Démonstration: Soit (x,y,z) l’unique solution de l’équation 4x+6y+9z=n telle que 0 \leq y \leq 1 et 0 \leq z \leq 1.

  • Si x \geq 0, alors évidemment l’équation admet des solutions positives.
  • Si x<0 alors nous allons montrer qu’il n’y a aucune solution positive. S’il y avait une solution positive (x',y',z') alors on aurait nécessairement y'>1 ou z'>1 (si ce n’était pas le cas, l’unicité de y et z entrainerait x'=x ce qui est impossible car x<0 et x' \geq 0 !).
    Supposons par exemple que y'>1 (ce qui entraine y'>y). En soustrayant les deux équations 4x'+6y'+9z'=n et 4x+6y+9z=n, on aurait donc la relation 4(x'-x) + 6(y'-y) = 9(z-z').
    Or, x'-x > 0 (car x<0 et x' \geq 0) et y'-y > 0 donc  4(x'-x) + 6(y'-y) >0. Ainsi, cela impose dans le membre de droite que z-z' >0 et donc z=1 et z'=0. Cela implique alors l’égalité 4(x'-x) + 6(y'-y) = 9 ce qui est impossible car 9 n’est pas un nombre pair. Il ne peut donc y avoir de solution positive si x<0.
    (L’idée est en fait que 0 < z-z' \leq 1  et donc z-z' n’est pas divisible par 2. Cela pourrait éventuellement se généraliser au cas où on aurait une équation dans laquelle il y a une unique solution pour laquelle z qui serait compris entre 0 et un nombre N.)

La caissisère deviendra-t-elle folle ?

La réponse est oui. Il est impossible de former 11 nuggets à partir de boites de 4, 6 et 9. En effet, on remarque que 11=4\times (-1) + 6\times 1 + 9 \times 1 qui bien est de la forme 4x+6y+9z avec x<0, 0 \leq y \leq 1 et 0 \leq z \leq 1.

En fait, 11 nuggets est le plus grand nombre qui ne peut pas être formé à partir de boites de 4, 6 et 9 car c’est le plus grand élément (maximum) de l’ensemble \{ 4x+6y+9z \text{ tel que } x < 0 , 0 \leq y \leq 1 , 0 \leq z \leq 1 \}. En effet, si x<0 alors x \leq -1 et donc 4x+6y+9z \leq 4 \times (-1) + 6 \times 1 + 9\times 1 =11.

Donc, à partir de 12 nuggets, on pourra toujours trouver une combinaison. Vous pouvez donc sans inquiétude commander 473 nuggets et la caissière vous donnera fièrement (par exemple) 116 boites de 4, 0 boites de 6 et 1 boites de 9.

(Pour ceux qui se demandent comment j’ai trouvé ces valeurs, j’ai repris certaines étapes de la démonstration: (non je n’ai pas utilisé de programme brute force):

  • On fait la division euclidienne de -n par 2:  -473 = 2 \times (-237 ) + 1. Donc k=-237 et z=1.
  • Ensuite, on fait la division euclidienne de -15n-27k=-156 par 2: -156 = 2 \times (-78). Donc m=-78 et y=0.
  • On détermine x facilement: 4x + 6 \times 0 + 9 \times 1 = 473 donc x=116.

Bien entendu, il y avait sans doute plus simple dans ce cas particulier mais j’ai envie de dire qu’on s’en tartine le nugget avec de la sauce barbecue).

Notes:

  • Pour la fin de la démonstration je me suis inspiré de cet article de artofproblemsolving.com, que j’ai adapté.
  • Vous pouvez consulter la page Wikipédia à ce sujet, dans laquelle l’étude est faite, d’une façon différente, pour des boites de 6, 9 et 20.
  • Le nombre 11 s’appelle le nombre de Frobenius de l’équation 4x+6y+9z=n. C’est le plus grand nombre n pour lequel il n’y a aucune solution positive.
Advertisements
Cet article, publié dans Arithmétique, est tagué , , . Ajoutez ce permalien à vos favoris.

2 commentaires pour Viens voir mes nuggets

  1. Ping : Le théorème des restes Chinois… avec des sushis | Blogdemaths

  2. Ping : Le théorème des restes Chinois… avec des sushis | Actumaths

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s