Adhérer ou faire un don

Enquête au restaurant.

(récréation arithmétique)

Julien Moreau

Le petit problème ci-après a une intéressante particularité : il met en jeu, comme le montre la généralisation présentée ensuite, quelques notions de base d’arithmétique et constitue donc un bon exercice pour ceux des élèves de terminale S qui suivent l’enseignement de spécialité, mais il peut aussi être traité en ne se servant que des connaissances de l’école élémentaire.

1. Le problème

  • 1.1. Une énigme policière
    Le célèbre détective Nestor Poirot vient dans le non moins célèbre restaurant l’Escopette enquêter sur un client suspect.
    « Oui, monsieur, fait le maître d’hôtel, il a mangé ici tous les midis pendant pas mal de temps. Quand il était seul, il prenait le menu touristique à 39 € tout compris.
    Quand il avait des invités, il prenait pour tout le monde le menu gastronomique à 50 €. Toujours les mêmes, ces invités, deux jeunes femmes, sauf une fois où il y a eu en plus un vieux monsieur. Radin avec ça, jamais un supplément, jamais un pourboire. Et comme c’était un ami du patron, il ne s’est pas pressé pour payer : la semaine dernière seulement, et il y en avait pour 1 861 € ! ».
    Nestor rentre chez lui, réfléchit longuement, rappelle le restaurant, demande le maître d’hôtel :
    « Dites-moi, mon ami, êtes-vous bien sûr des chiffres que vous m’avez donnés ?
    - Je suis désolé, monsieur. J’avais complètement oublié que le client avait payé au gérant un acompte de 1 000 €. Je peux même vous dire combien de fois il est venu et combien de fois il a eu des invités.
    - Inutile, fait dignement Nestor, je trouverai bien tout seul. »
  • 1.2. Comment aurait dû faire le détective
    Soit x le nombre de repas à 39 € et y le nombre de repas à 50 €.
    C’est à juste titre que le détective a trouvé louche l’équation 39x + 50y = 1 861.
    Elle donne en effet $39x \equiv 11$ (mod 50), soit encore $39x\equiv -39$ (mod 50), donc, puisque 39 et 50 sont premiers entre eux, $x \equiv -1$ (mod 50) ; x est donc de la forme $-1 + 50\lambda$, avec $\lambda$ entier relatif. Mais il nous faut de plus $0 < x \leq\frac{1 861}{39}$, avec $\frac{1 861}{39}\simeq 47,7$. On arrive donc à une impossibilité.
    Prenons maintenant l’équation rectifiée 39x + 50y = 2 861. Elle donne encore $39x \equiv 11$ (mod 50), ce dont on tire comme précédemment $x \equiv -1$(mod 50) ; x est donc de la forme $-1 + 50\lambda$. Mais $0 < x\leq\frac{2 861}{39}$ ; or $\frac{2 861}{39}\simeq 73,4$. La seule possibilité est donc x = 49. On en déduit 50y = 2 861 − 49 × 39 = 950, donc y = 19.
    Lors des repas gastronomiques, il y a eu 3 personnes chaque fois, sauf une fois où il y en a eu 4. Il y a finalement eu 6 repas de ce type.
    Au total, le client est venu 55 fois.
  • 1.3. Comment le détective a fait en réalité
    Nestor Poirot ignore tout de la divisibilité et a fortiori des congruences. Il ne connaît guère en mathématiques que la table de multiplication et le maniement d’une calculette bas de gamme. Mais cela lui a suffi.
    Il a d’abord remarqué que le prix total des repas à 39 € a pour chiffre des unités 1.
    Comme il sait encore par cœur sa table du 9, il en a déduit que le nombre de repas à 39 € finit par un 9. Mais, si l’addition était de 1 861 €, le nombre de repas à 39 € serait inférieur à $\frac{1 861}{39}\simeq 47,7$. Il a donc essayé 9, 19, 29, 39 qui donnent respectivement comme coût total des repas gastronomiques :
    1 861 − 39 × 9 = 1 510, 1 861 − 39 × 19 = 1120,
    1 861 − 39 × 29 = 730, 1 861 − 39 × 39 = 340.
    Les multiples de 50 finissant tous par 50 ou 00, il en a conclu que le maître d’hôtel s’était trompé.
    La seconde fois, il a recommencé le travail, sachant que le nombre de repas à 39 € finit là encore par un 9. Ce nombre est de plus inférieur à $\frac{2 861}{39}\simeq 73,4$. Les deux derniers chiffres de l’addition n’ayant pas changé et ceux du coût total des repas gastronomiques étant toujours 50 ou 00, il faut encore exclure 9, 19, 29, 39 ; il suffit d’essayer 49, 59, 69. Or 2 861 − 39 × 49 = 950, 2 861 − 39 × 59 = 560, 2 861 − 39 × 69 = 170.
    La seule possibilité est donc la première, soit 49 repas à 39 € et 19 à 50 €.

2. Un travail possible avec une classe

Il s’agit ici d’étudier l’équation 7x + 4y = n, où est n un entier naturel donné, x et y des inconnues entières strictement positives.

  • 2.1. Étude d’un cas particulier
    Prenons l’équation 7x + 4y = 82. Une condition nécessaire pour qu’un couple d’entiers relatifs la vérifie est $7x \equiv 82 $ (mod 4), c’est-à-dire encore $7x \equiv 2 $(mod 4) ; en remarquant que $7x\equiv {-x}$ (mod 4), la condition devient $x \equiv -2$ (mod 4), soit encore $x \equiv 2$ (mod 4).
    Comme nous exigeons que x soit un entier strictement positif, il est de la forme $2 + 4\lambda$, avec $\lambda$ entier naturel. Il vient alors $7(2 + 4\lambda) + 4y = 82$, qui équivaut à $y = 17 - 7\lambda$. Les conditions x > 0 et y > 0 reviennent à $0 \leq\lambda<\frac{17}{7}$ .
    Ainsi $\lambda$ ne peut prendre que les trois valeurs 0, 1 et 2. Il y a donc trois solutions :
    (2 ; 17), (6 ; 10) et (10 ; 3).
  • 2.2. Généralisation : équation 7x + 4y = n (n, x, y entiers strictement positifs)
    Une condition nécessaire pour qu’un couple (x, y) d’entiers relatifs vérifie cette équation est $7x \equiv n$ (mod 4), c’est-à-dire encore $x \equiv -n$ (mod 4). Cette remarque permet de discuter aisément l’équation selon la valeur de n modulo 4.
    Supposons par exemple que n soit du type 4k + 1 (les autres cas se discutent de la même façon). Alors 7x + 4y = n exige $7x\equiv 1$ (mod 4), soit $x \equiv -1$ (mod 4).
    Comme nous exigeons que x soit un entier strictement positif, il est de la forme $3 + 4\lambda$ avec $ \lambda \geq 0$. Il vient alors 7(3 + 4l) + 4y = 4k + 1, c’est-à-dire $y = k - 7\lambda$ avec la condition y > 0, qui revient à $\lambda<\frac{k-5}{7}$. Il y a donc des solutions si et seulement si $k \geq 6$. Leur nombre [1] est évidemment $1+\frac{k-5}{7}$. En revenant à n, on voit que ce nombre est $1+ \frac{4k-20}{4x7}$, soit $1+ \frac{n-21}{4x7}$ et finalement $\frac{n}{4x7}$.

3. Le problème mathématique sous-jacent

  • 3.1. Énoncé du problème général
    On donne deux entiers p et q au moins égaux à 2 et premiers entre eux. Pour tout entier naturel n, étudier l’existence et le nombre de solutions de l’équation $px + qy = n (E_n)$ (x et y entiers strictement positifs).
  • 3.2. Existence des solutions
    Pour n > pq, l’équation a toujours au moins une solution et, pour n = pq, elle n’en a aucune.
    Il existe deux entiers relatifs u et v tels que pu + qv = 1. Soit alors un couple x, y d’entiers relatifs. Ils vérifient l’équation px + qy = n si et seulement si p(x − nu) = −q(y − nv).
    Compte tenu du fait que p et q sont premiers entre eux, cela revient à dire qu’il existe un entier relatif $\lambda$ tel que $x = nu +\lambda q$ et $y = nv -\lambda p$.
    Il nous faut (et il nous suffit) que l’on ait de plus x > 0 et y > 0, soit $\lambda q > -nu$ et $\lambda p < nv$, autrement dit $-\frac{nu}{q} <\lambda <\frac{nv}{p} . $
    Remarquons que $\frac {-nv}{p}+\frac{nu}{q}= \frac{n}{pq} $ .
    La longueur de l’intervalle ouvert $\left] \frac{nu}{q}, \frac{nv}{p}\right.[$ est donc $\frac{n}{pq}$.
    Si on a n > pq, cette longueur est strictement supérieure à 1, donc l’intervalle contient au moins un entier.
    Le problème posé a donc au moins une solution dès que n > pq. Voyons ce qui se passe pour n = pq. Les extrémités de l’intervalle sont deux entiers consécutifs ; il n’y a entre eux aucun entier et le problème n’a pas de solution.
    Remarque  : pour n < pq, les deux cas peuvent se présenter (penser, par exemple à n = p + q et à n = p).
  • 3.3. Nombre de solutions
    Poussons un peu plus loin l’étude. Si $n \in\left]kpq , (k + 1)pq\right.[$, où k est un entier naturel, la longueur de l’intervalle ouvert est strictement comprise entre k et k + 1, donc [2] cet intervalle contient au moins k et au plus k + 1 entiers.
    Supposons maintenant que l’on ait n = kpq. L’intervalle ouvert $\left]kpq, (k + 1)pq\right.[$ est du type ]a, a + k[, où a est un entier relatif ; il contient donc les entiers a + 1, a + 2, …, a + k − 1,ce qui fournit donc k − 1 solutions. On peut aussi reprendre le travail directement sur l’équation px + qy = kpq. On voit aussitôt que q divise x et p divise y ; on arrive à x = qr, y = ps avec r et s entiers strictement positifs tels que r + s = k.
    De ce qui précède, nous pouvons déduire le résultat suivant :
    Le nombre de solutions en entiers strictement positifs de l’équation px + qy = n, où p, q, n sont des entiers strictement supérieurs à 1, p et q étant premiers entre eux, est $\frac{n}{pq}$ ou $\frac{n}{pq}+1$ si n n’est pas multiple de pq et $ \frac{n}{pq}-1$ si n est multiple de pq.
    Remarque : nous laissons au lecteur le soin de vérifier que, si l’on considère les deux équations $(E_n)$ et $(E_{n'})$, avec n’= n + pq, $(E_{n'})$, a exactement une solution de plus que $(E_n)$ , et que, si $(E_n)$ a des solutions, on peut déduire très simplement de celles-ci les solutions de $(E_{n'})$.
  • 3 . 4 . Variante
    Si on reprend le même problème en se contentant de solutions x et y positives au sens large, ce nouveau problème peut aisément être ramené au précédent.
    Si on pose X = x + 1, Y = y + 1, l’équation px + qy = n devient pX + qY = n + p + q, (X > 0, Y > 0) ce qui nous permet par exemple d’affirmer qu’il y a des solutions pour tout n > pq − p − q et qu’il n’y en a pas pour n = pq − p − q.
  • 3.5. Sur l’origine du problème
    L’étude de cette équation px + qy = n, où données et inconnues sont des entiers naturels, figure [3] dans le numéro d’avril 1858 (pages 126-130) des Nouvelles Annales de Mathématiques, qui n’était pas une revue savante, mais le « Journal des candidats aux écoles Polytechnique et Normale ».
    Le problème était posé par Charles Hermite, qui avait alors trente-six ans. Bien que déjà célèbre, il avait gardé un faible pour cette modeste revue dans laquelle il avait publié, en 1842, ses deux premiers articles. La solution publiée émanait d’un élève du lycée Saint-Louis. À la suite de cette solution figurait une étude d’Hermite lui-même, beaucoup plus approfondie que celle du lycéen … et que celle qui figure dans cet article.

[1] Avec la notation classique [z] pour la partie entière du réel z.

[2] Il n’est pas sans intérêt de faire effectuer au élèves une démonstration en forme de cette propriété intuitivement évidente.

[3] La rédaction de la revue signalait deux références plus anciennes, l’une étant l’Algèbre de Mayer et Coquet, dont la première édition est de 1832.