CultureMath

Vous pouvez retrouver cette question au format pdf.

Question du jeudi #59 : Dans un certain sport, les actions peuvent rapporter $6$, $9$ ou $20$ points. Quel est le plus grand score qui soit impossible à atteindre ?

Commençons par déterminer les nombres de points que l'on peut obtenir en n'exécutant que les actions qui rapportent $6$ et $9$ points. Puisque $6 = 3 \times 2$ et $9 = 3 \times 3$, il est déjà clair que l'on n'obtiendra de la sorte que des multiples de $3$.

Mais on peut dire mieux. Pour cela, démontrons un résultat intermédiaire.

Lemme. Tout nombre entier $\geq 2$ peut s'écrire sous la forme $a \times 2 + b \times 3$.

Preuve. La preuve de ce résultat est très simple, mais repose sur un principe qui nous resservira, que l'on va appeler le principe des scores consécutifs. Le point-clef est que $2$ et $3$ sont deux entiers consécutifs pouvant s'écrire sous la forme demandée (de façon tautologique, dans leur cas). En ajoutant $2$, on obtient qu'il en va alors de même de $4$ et $5$. En rajoutant $2$, de $6$ et $7$, et ainsi de suite pour tous les entiers successifs : comme $2$ est dans la liste des scores autorisés, il suffit de trouver $2$ scores consécutifs pour obtenir tous les scores supérieurs.

On a donc résolu notre question intermédiaire : les scores (strictement positifs) possibles à partir d'actions valant $6$ et $9$ points sont exactement les scores de la forme $3 \times n$, où $n$ est un entier $\geq 2$.

Que se passe-t-il si l'on s'autorise maintenant l'action à $20$ points ? Comme $6$ et $9$ sont toujours des multiples de $3$, il va falloir utiliser l'action à $20$ points pour obtenir des scores qui ne sont pas multiples de $3$. Plus précisément, comme $20 = 3 \times 6 + 2$ et $40 = 3 \times 13 + 1$, il va falloir au moins effectuer cette action une fois pour obtenir des scores de la forme $3k+2$ et au moins deux fois pour obtenir des scores de la forme $3k+1$. Cela démontre déjà que tous les scores de la forme $3k+1$ inférieurs à $40$ sont impossibles (le dernier est $37 = 3 \times 12 + 1$) et même que $43$ est impossible, car il faudrait pour l'obtenir marquer deux fois $20$ points, mais il est alors impossible de marquer les trois points manquants.

Pour vérifier que les nombres supérieurs à $43$ sont des scores possibles, on peut alors adopter plusieurs stratégies :

• On peut utiliser le principe des scores consécutifs, d'après lequel il suffit de trouver $6$ scores possibles consécutifs pour être sûr de pouvoir obtenir tous les scores suivants. Il est alors facile de démontrer que les entiers de $44$ à $49$ sont effectivement des scores possibles, par exemple avec les décompositions suivantes :
  \[ \begin{array}{c@{\qquad}c@{\qquad}c}
  44 = 20 + 6 \times 4, & 45 = 9 \times 5, & 46 = 20 \times 2 + 6\\
  47 = 20 + 9 \times 3, & 48 = 6 \times 8, & 49 = 20 \times 2 + 9.
  \end{array}\]
• On peut également faire une disjonction de cas suivant le reste de la division du nombre par $3$.
  1. Pour un nombre $\geq 6$  multiple de $3$, on a vu au début du raisonnement que l'on pouvait obtenir un tel score uniquement avec les actions à $6$ et $9$ points.
  2. Pour un nombre $n \geq 26$ de la forme $3k+2$, il suffit d'appliquer le cas précédent à $n-20$, qui est un multiple de $3$, et d'ajouter une action à $20$ points.
  3. Pour un nombre $n \geq 46$ de la forme $3k+1$, il suffit d'appliquer le premier cas à $n-40$, qui est un multiple de $3$, et d'ajouter deux actions à $20$ points.
  Comme tous les entiers $\geq 44$ sont dans l'une des trois catégories précédentes, cela démontre bien que $43$ est le plus grand score impossible.

Remarques.

• Les scores possibles dans un sport forment ce que l'on appelle un semigroupe numérique. Par exemple, on s'est intéressé ici au semigroupe $\langle 6, 9, 20\rangle$. On peut relativement facilement démontrer que si les nombres de points rapportés par les différentes actions (les générateurs du semigroupe) n'ont pas de diviseur commun $> 1$, alors tous les scores sont possibles à partir d'un certain rang (inclus), que l'on appelle le conducteur du semi-groupe (et l'entier qui le précède est appelé le nombre de Frobenius). Ici, on a donc démontré que le nombre de Frobenius de $\langle 6, 9, 20\rangle$ était $43$. Le problème de la détermination du nombre de Frobenius d'un semi-groupe numérique est un problème extrêmement compliqué et très largement ouvert. Pour en savoir plus sur ce sujet, on ne saurait trop recommander l'excellent article Semi-groupes numériques et conjecture de Wilf de Shalom Eliahou, paru sur Images des Mathématiques.
• Pour ces valeurs spécifiques, on parle parfois du problème des Chicken McNuggets, car ces produits étaient vendus par boîtes de 6, 9 et 20. On pourra consulter la vidéo correspondante de l'excellente chaîne Youtube Numberphile.