481
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.
Actualités et Informations
Base de ressources bibliographiques
Les Régionales de l’APMEP