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 ?

Si vous séchez après avoir bien cherché : 


© Serge Mehl - www.chronomath.com


 

 

 

 

 

 

 

 

 

 

Solution :

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

   la solution est 17 femmes et 41 hommes

Théorie :         Identité de Bézout (programme JavaScript) :
 
Programmation de la méthode en JavaScript

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...

<SCRIPT LANGUAGE=JavaScript>
function go()
{
for(f=1;f<=51;f++)     //
 "boucle des femmes"
{
for (h=f+1;h<=51;h++)   //
 "boucle des hommes"
{if (19*h+13*f==1000)
{
alert("h = "+h+" , f = "+f);
d=1
}}}
if (d==0) {alert("Je ne trouve rien")}
}
</SCRIPT>

La seconde boucle (des hommes) démarre à f + 1 car on sait qu'il y a plus d'hommes (h) que de femmes (f).

 Si nous supprimons la condition h > f, il y a 4 solutions :

  • (41,17)
  • (28,36)
  • (15,55)
  • (2,74).

Le programme étant modifié en conséquence par la boucle f variant de 1 à 74 et la boucle h de 1 à 51.

L'ordinateur trouve l'unique solution :

h = 41, f = 17
 


© Serge Mehl - www.chronomath.com