ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

L'auberge d'Euler     équation en nombres entiers ax + by = c

On doit à Euler ce petit problème d'arithmétique que l'on peut résoudre mathématiquement par des critères de divisibilité, l'usage du théorème de Bézout (en fait de Bachet) ou par essais successifs grâce à un "bête" petit programme JavaScript :

Un jour, dans une auberge, s'arrêtent plusieurs diligences.
Des hommes, mais aussi des femmes, en moindre nombre, mais tout autant affamées s'attablent.

Il est convenu à l'issue du repas que les hommes paieront chacun 19 sous et les femmes 13 sous chacune.
L'aubergiste récolte ainsi exactement 1000 sous.

Combien d'hommes et de femmes sont descendus ce soir-là à l'auberge ?

Il y a des femmes et des hommes en plus grand nombre, donc au moins trois hommes et deux femmes. Le nombre d'hommes h ne peut donc excéder (1000 - 26)/19, soit 51. Il s'agit de résoudre en nombres entiers l'équation :

19h + 13f = 1000      sous les conditions :  3  ≤  h  ≤  51, f < h

C'est une application de la célèbre identité de Bézout. Comme pgcd(19,13) = 1, l'équation ne se réduit pas. On résout d'abord l'équation 19u + 13v = 1 avec u et v entiers relatifs. Or 3 × 13 = 39 et 2 × 19 = 38, donc 19 × (-2) + 13 x 3 = 1. Par conséquent , une solution particulière est u = - 2000, v = 3000. La solution générale est alors h = -2000 - 13k, f = 3000 + 19k. Mais h ≥ 3 et f < h; par conséquent, il nous faut résoudre maintenant -2000 - 13k ≥ 3 et -2000 - 13k > 3000 + 19k. Ce qui fournit k ≤ -157

• k = - 157 : h = 41 et f = 17;
• k = - 158 fournit 54 hommes, c'est déjà trop !

 ➔   La solution est 17 femmes et 41 hommes

Solution "bête" (mais efficace...) pour jouer à programmer : h et f désignant respectivement le nombre d'hommes et de femmes, il y a au moins 3 hommes, donc f ne peut excéder (1000 - 57)/13, soit f ≤ 72. Il y a au moins deux femmes, donc h ne peut excéder (1000 - 26)/19, soit 51. Vu h > f, c'est f qui varie de 1 à 51 et h de f + 1 à 51. On arrête là l'analyse et l'ordinateur se débrouillera si le programmeur n'est pas trop mauvais...