Accueil

Orientation générale

Barre de recherche

DicoNombre

DicoMot Math

DicoCulture

Atlas des maths

Rubriques

Index alphabétique

Nouveautés

Actualités

Références

Édition du: 01/03/2023

M'écrire

Brèves de Maths

 

INDEX

Partitions

Dénombrement

Graphes

Algorithmes

Problèmes modernes

Jeux et énigmes

Pesées – Partitions  

Pesée avec des 4 et des 7

Mc Nugget

Poids-étiquettes

Sac à dos

Chameau et bananes

Somme sous-ensemble

Faites un double-clic pour un retour en haut de page

 

 

Nombres McNUGGET

& Problème de Frobenius

 

Ce fast-food ne sert que des barquettes de nuggets de 4, 6 ou 20 pièces. Est-il possible d'acheter toutes les quantités de pièces que l'on veut ?

 

Le problème de Frobenius ou des pièces de monnaies est une généralisation avec des barquettes de différentes tailles. Barquettes ou pièces de monnaie ou poids pour la pesée ou ...

  

 

Sommaire de cette page

>>> McNugget

>>> Cas de deux valeurs

>>> Problème de la ferme (ou de la ville de Hamlet)

>>> Le problème des pièces de monnaie

>>> Le problème du rendu de monnaie

>>> Le problème des timbres postaux

>>> Calculabilité

>>> Démonstration du théorème des McNugget

  

Débutants

Nombres

 

Glossaire

Nombres

 

 

Mc Nugget

haut

 

Le problème

Le restaurant ne sert que des barquettes de Nuggets de 4, 6 ou 20 pièces. Est-il possible d'acheter n'importe combien de pièces ?

Non, mais à partir d'une certaine quantité, c'est toujours possible. Quelle est la valeur limite ?

 

Les quantités impossibles ne sont pas des nombres McNugget.

 

La limite est appelé nombre de Frobenius.

 

 

Barquettes 6, 9 et 20

 

Nombres NON-McNugget

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43.

Nombre de Frobenius: 43.

 

En ajoutant une barquette de quatre nuggets, toutes les combinaisons sont possibles sauf 1, 2, 3, 5, 7 et 11.

    

 

 

Tableau des commandes possibles

 

En colonne de droite, s est la quantité qu'il est possible de commander en combinant les boites de nuggets.

La quantité minimale est 6; les nombres 1, 2, 3, 4 et 5 ne sont donc pas Mc Nugget.

Idem  pour les valeurs 7 et 8.  Etc.

À partir de 44, toutes les valeurs de s sont possibles.

 

Partitions

 

On a ainsi les partions possibles du nombre s avec les nombres 6, 9 et 20.

 

Certaines partitions sont multiples comme: 18 = 6 + 6 + 6 = 9 + 9 (double partitions).

Il s'agit de deux partitions particulières parmi les 385 possibles pour le nombre 18.

 

Formule des nombres MC Nuggets

N = 6x + 9y + 20z

 

 

 

Voir Brève 49-968

 

 Cas de deux valeurs avec exemples

haut

 

Le théorème des Chicken McNugget ou problème du timbre-poste ou problème de la pièce de Frobenius.

 

Pour deux entiers positifs premiers entre eux m et n, le plus grand entier qui ne peut pas être écrit sous la forme am + bn pour les entiers non négatifs a, b est mn – m – n.

 

Une conséquence du théorème est qu'il existe exactement:

entiers positifs qui ne peuvent pas être exprimés sous la forme am + bn.

 

Démonstration

La preuve est présentée in fine (*niveau supérieur).

Montré en 1884 par James Sylvester.

 

 

Origine la plus populaire

 

À l'origine, McDonald's vendait ses nuggets en boites de 9 et 20.

Sachant cela, les férus de maths ont vite calculé le plus grand nombre de nuggets qui n'aurait pas pu être achetées avec ces packs. Dans ce cas c'est 151.

9 x 20 – 9 – 20 = 151

La société a vite ajouté des barquettes de 4 pièces.

 

Le théorème des Chicken McNugget est aussi appelé: problème des pièces de monnaie de Frobenius ou problème de Frobenius. Le mathématicien allemand Ferdinand Frobenius (1849-1917) s'est enquis de la plus grande valeur qui n'aurait pas pu être atteinte avec certains types de pièces.

 

 

Autres exemples

Le peintre achète sa peinture en pots de 2 ou 7 litres. Quelle est la plus grande quantité que le peintre ne peut pas obtenir ?

2 × 7 – 2 – 7 = 5

   

 

Au football américain, on compte 3 points pour un essai et 7 points pour un essai transformé. Quel est le plus grand score qui ne sera pas plausible pour un match ?

3 × 7 – 3 – 7 = 11

 

Nombres 2-McNugget jusqu'à 100

Nombres de la forme mn – m – n avec m et n premiers entre eux.

 

Exemple m = 3 et n = 8 (qui sont premiers entre eux):
mn – m – n = 24 – 11 = 13

 

 

 

OUI de la forme mn – m – n

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 35, 37, 39, 41, 43, 47, 49, 51, 53, 55, 59, 63, 65, 67, 69, 71, 79, 83, 89, 95, 97.

 

NON (hors tous les nombres pairs)

21, 33, 45, 57, 61, 73, 75, 77, 81, 85, 87, 91, 93, 99.

 

 

Problème de la ferme (ou de la ville de Hamlet)

Problème

Cette ferme compte 3 personnes par cheval, 4 moutons par vache et 3 canards par personne.

Quel est le total de personnes, de chevaux, de moutons, de vaches et de canards qui ne pourra jamais être atteint ?

 

Solution

 

 

Le problème des pièces de monnaie

haut

 

Il s'agit de déterminer le montant le plus élevé que l'on ne peut pas représenter en n'utilisant que des pièces de monnaie de valeurs faciales fixées.

Ou plus généralement des nombres donnés, valeurs des pièces ou autres, comme des poids pour la pesée.

Les valeurs sont première entre elles (PGCD = 1).

 

Le tableau montre quelques exemples de types de barquettes (a, b et c) et indique en colonne de gauche (s) la limite telle qu'au-delà, il est possible de commander n'importe quelle quantité.

 

Exemple

Aves des barquettes de 2 et 3 pièces, toutes les combinaisons supérieures à 1 sont possibles.

 

Avec des barquettes de 7 et 13 pièces, il faut atteindre 71 pour que les valeurs suivantes soient toutes atteignables.
Son calcul est 7
× 13 – 7 – 13 = 71

 

 

 

S

a

b

c

1

2

3

 

5

3

4

 

2

3

4

6

7

3

5

 

4

3

5

7

23

5

7

 

13

5

7

11

29

6

7

 

17

6

7

8

43

6

9

20

49

6

10

20

49

6

11

48

7

11

 

30

7

11

13

71

7

13

 

45

7

13

23

 

 

Anglais: Coin problem

 

Le problème du rendu de monnaie

haut

 

Étant donnée une somme (s) à payer quelle est le minimum de pièces ou billets pour rendre la monnaie.

C'est à nouveau un problème de partition: quelle est la partition de s minimale avec des nombres donnés.

 

Ce problème est identique au précédent avec s = somme à rendre à l'acheteur.

 

Notre expérience de tous les jours semble montrer que la résolution de ce problème est simble. Pas toujours le cas pour de grandes valeurs !

 

 

 

Exemple 1

Prix: 14 euros

Paiement: billet de 20 euros

Pièces disponibles:1, 2, 5 euros

Monnaie rendue: 6 = 5 + 1 ou 2 + 2 + 2 = 1 + 1 + 1 + 1 + 1 + 1.

Minimum: 5 euros et 1 euro.

 

 

Exemple 2

9,34 euros pour 10.

À rendre: 66 cts = 50 + 10 + 5 + 1

  

 

 

Le problème des timbres postaux

haut

 

Énigme mathématique

Quelle est la plus petite valeur d'affranchissement qui ne peut pas être placée sur une enveloppe, si

*      celle-ci ne peut contenir qu'un nombre limité de timbres, et

*      ceux-ci ne peuvent avoir que certaines valeurs faciales spécifiées.

 

Formulation mathématique

Étant donné un entier m et un ensemble V d'entiers positifs, trouver le plus petit entier z qui ne peut pas être écrit comme la somme v1 + v2 + ··· + vk d'un certain nombre k ≤ m d'éléments (pas nécessairement distincts) de V.

   

 

Exemple

L'enveloppe ne peut contenir que trois timbres et les valeurs de timbre disponibles soient 1 cent, 2 cents, 5 cents et 20 cents.

Alors la solution est de 13 cents; puisque toute valeur inférieure peut être obtenue avec au plus trois timbres (par exemple 4 = 2 + 2, 8 = 5 + 2 + 1, etc.).

Mais pour obtenir 13 cents, il faut utiliser au moins quatre timbres.

 

Voir Pliage de timbres

 

 

 

Calculabilité

Pour deux valeurs de pièces, il existe une formule de calcul du nombre de Frobenius, mais aucune pour plus de deux valeurs.

 

En revanche, il existe un algorithme qui calcule le nombre de Frobenius en temps polynomial, à condition de connaitre les valeurs des pièces données à priori (algorithme glouton).

 

Pas possible dans le cas général de valeurs de pièces données comme variables. Le problème est dit NP-difficile.

 

 

English corner

The Chicken McNugget theorem, also known as the Frobenius coin problem, states that for any two relatively prime integers m and n, the largest integer that cannot be expressed in the form am + bn for non-negative integers a and b is mn − m − n.

In other words, if I have boxes of 6 and 11 chicken nuggets, the largest number of chicken nuggets that is non-purchasable with a combination of these boxes is 6 × 11 − 6 − 11 = 49. Any number of chicken nuggets above 49 is purchasable.

Voir Anglais pour le bac  et pour les affaires 

 

 

 

Démonstration du théorème des McNugget*

haut

 

Théorème des McNugget :

Pour des entiers positifs premiers entre eux a et b, le nombre M = ab – a – b  ne peut pas être exprimé sous la forme ax + by pour tous les entiers non négatifs x et y. De plus, tout entier n > M peut être représenté par ax + by pour certains entiers non négatifs x et y.

 

 

Principe

Il existe des nombres qui sont atteints et d'autres non-atteints avec deux nombres a et b.

 

Deux volets à la démonstration:

*      1 – prouver que M = ab – a – b est non atteint

*      2 – prouver que tout nombre supérieur à M est atteint:

 

 

Cas 1

M = ab – a - b

n'est pas atteint

Preuve par contradiction: hypothèse

Si M = ab – a – b

est atteint

Alors il existe x et y

ab – a – b

= ax + by

En mod a (reste de la division par a = by)

ax + by

≡ by mod a

De manière semblable

ab – a – b

≡ -b mod a

En reprenant l'égalité

by mod a

≡ -b mod a

Or a et b sont premiers entre eux, il existe un inverse de b mod a (b'). En multipliant pa b'

bb'y mod a

≡ -bb' mod a

 

 

≡ (-1) × bb mod a

En simplifiant

y mod a

≡ -1

Même raisonnement en divisant par b

x mod b

≡ -1

Les nombres a et b sont positifs. D'où les plus petites valeurs positives(en ajoutant une fois ou plus le diviseur à chacun)

x

y

b – 1

a – 1

Reprenons notre égalité supposée

ab – a – b

= ax + by

et appliquons les inégalités

 

≥ a (b – 1) + b (a – 1)

≥ 2ab – a – b

≥ ab – a – b

Contradiction ! L'hypothèse est fausse

ab – a – b

≥ ab – a – b   n

 

Cas 2

  M > ab – a - b

est atteint

Preuve basée sur l'identité de Bézout

Si a et b sont des entiers, il existe deux entiers x et y  tels que:

ax + by = PGCD (a, b)

Dans notre cas, a et b sont premiers entre eux

PGCD (a , b) = 1

=>  (x, y) : ax + by = 1

Soit x' = nx et y' = ny

 

ax' + by' = n

Si

x' et y'

solution de ax' + by' = n

Alors

x' – kb et y' + ka

aussi solution

On choisit k pour que x' – kb soit entre 0 et b – 1  pour une valeur de k que l'on note k'

0 ≤ x' – kb ≤ b – 1 

 

Notons les valeurs correspondantes de x et y

x" = x' – k'b

y" = y' + k'a

Or selon Bézout, ces nombres sont solutions

x" et y"

solution de ax + by = n   n

Il reste à montrer que x" et y" ne sont pas négatifs.

 

 

x" l'est par définition

Cf:    0 ≤ x" ≤ b – 1

 

Ce que nous savons

ax" + by" = n

et n > ab – a – b

En rapprochant ces inégalités

ax" + by"

by" + b

b(y" + 1)

> ab – a – b

> ab –a – ax"

> a(b – 1 – x")

Or, on sait que

x"

b – 1 – x"

≤ b – 1

≥ 0

En multipliant par a qui est positif

a (b – 1 – x")

≥ 0

Remplacement par une quantité plus grande

b (y" + 1)

≥ 0

Or b est positif

y" + 1

y"

≥ 0

≥ 0    n

                 

Référence: The Chicken McNugget Theorem, Explained – Mike Beneschan

  

 

 

Haut de page (ou double-clic)

  

 

Retour

*           Pesée avec des 4 et des 7

Suite

*           Pesée des 9 billes

*           Pesée des douze billes

*           Nombres premiers et raison (progression arithmétique)

*           Problème du sac à dos

*           Permutations conduisant à total fixé

*           Problème impossible de la somme et du produit (Freudenthal)

Voir

*           Énigmes de transvasements

*           Énigmes en économie

*           Jeux, énigmesIndex

*           Partage – Énigmes classiques

Sites

*            Problème des pièces de monnaie – Wikipédia

*            McNugget Number – Wolfram MAthWorld

*            OEIS A065003 – Not McNugget numbers

*           Chicken McNugget Theorem – Xavier Lien

*           Chicken McNugget Theorem – AoPSOnLine

*           2015 AMC 10B Problems/Problem 15 – AoPSOnLin

*           Factoring in the Chicken McNugget Monoid** - Scott T. Chapman & Chris O'Neil

Vidéo

*           How to order 43 Chicken McNuggets – NumberphileVideo Youtube

Cette page

http://villemin.gerard.free.fr/aJeux1/Pesee/Nugget.htm