Nous suivre Industrie Techno

Les 17 conquistadors

Rédaction Industrie et Technologies

Sujets relatifs :

,
Solution de l'énigme du n°871 d'octobre 2005
La résolution du problème des 17 conquistadors exige des connaissances mathématiques poussées en arithmétique. Une recherche par tatonnement est bien évidemment possible, mais elle risquerait de se révéler rapidement fastidieuse.
Il faut résoudre un système de trois équations facile à établir.
Si X est le nombre de pièces d'or au départ,
On a immédiatement :
X = 3  mod 17  (1)
Puis, puisque six conquistadors sont éliminés :
X = 4  mod 11  (2)
Et enfin, puisque il reste finalement six conquistadors :
X = 5  mod 6  (3)
La notation modulo signifiant, rappelons-le, que le reste de la division de X par 17 (par exemple) à pour reste 3.
La solution générale de ce système est donnée par le théorème du reste chinois (en effet, le célèbre probléme ici proposé, est généralement posé dans la littérature avec... des pirates et un cuisinier chinois. Nous l'avons simplement transposé.)
Ce théorème dit que pour un système de n équations du type :
X = x1 mod m1 ; X = x2 mod m2 ;....X = xi mod mi,
La solution s'écrit :
X = x1 M y1 + x2 M y2 +...xi M yi     (mod M )
Il existe donc une infinité de solution modulo M.
Dans cette expression, les xi sont les restes successifs des divisions par mi, tandis que M est le produit de tous les coefficients mi :   M= m1m2....mi.
Quant aux yi, ils sont obtenu à partir des valeurs Mi définies par :    Mi = M/mi.
De quelle façon ? Ce sont les transformés des Mi  par l'algorithme d'Euclide.
Ils sont donnés par la formule : yi Mi - 1 = km
(Cette formule est issue du théorème de Bezout appliqué aux couples (Mi, mi).
Ce théorème dit que si deux nombres entiers a et b sont premiers entre eux, on peut toujours trouver deux nombres entiers u et v tels que : au + bv = 1
Pour (Mi, mi) on a donc : yi Mi - 1 = v m    (ou  yi et v sont uniques)
Pour notre système la solution est donc :
X = x1 M1 y1 + x2 M2 y2 + x3 M3 y3   (mod M)
Avec :
M = 17.11. 6 = 1122
M1 = 11.6 = 66
M2 = 17. 6 = 102
M3 = 17.11 = 187
On a donc :
X = 3.66.y1 + 4.102.y2 + 5.187.y3   (mod 1122)
Pour les yi on trouve aisément :
y1 = 8    (8.66 - 1 = 31.17)
y2 = 4
y3 = 1
(la valeur de chaque v dans la formule de Bezout, n'intervient pas dans la solution)
Et finalement :
X = 3.66.8 + 4.102.4 + 5.187.1   (mod 1122)
Soit :
X = 1584 + 1632 + 935 = 4151   (mod 1122)
La plus petite solution est donc obtenue en divisant autant de fois que possible 4151 par 1122 et en gardant le reste.
On voit aisément que la division peut être effectuée trois fois (puisque 3 fois 1122 = 3366) : 
Donc 4151/3366 = 3 et il reste 785
La solution est donc :
X = 785 pièces d'or

 

Bienvenue !

Vous êtes désormais inscrits. Vous recevrez prochainement notre newsletter hebdomadaire Industrie & Technologies

Nous vous recommandons

Dossier composites : comment ils vont surpasser les métaux

Dossiers

Dossier composites : comment ils vont surpasser les métaux

Les composites ne cessent d'innover pour rester compétitifs face aux autres matériaux. L'innovation porte sur les matériaux eux-mêmes, mais aussi sur[…]

Les colloques à venir - Au 12 juin 2009

Agenda

Les colloques à venir - Au 12 juin 2009

Les Nanotechnologies, vous connaissez ?

Les Nanotechnologies, vous connaissez ?

IT 911 mai 2009

IT 911 mai 2009

Plus d'articles