J133. Mouvements de tours Imprimer
J. Jeux de plateaux

calculator_edit.png  

Problème proposé par Michel Lafond

Un échiquier de n × n cases contient au départ n tours sur la ligne du bas.

Chaque tour peut se déplacer comme aux échecs, mais son trajet doit être maximal, c’est-à-dire qu’elle ne peut s’arrêter que si elle rencontre un obstacle (le bord ou une autre tour). Il n’y a ni prise ni saut.
Il s’agit d’obtenir en D(n) déplacements les n tours alignées le long d’une diagonale.
Ci-dessous une solution avec D(4) = 9 qui n’est pas optimale.

J133e








Q1.  Essayez de minimiser D(n) pour n ? {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}.
Q2.  Si on note  M(n) le nombre minimal de mouvements nécessaires pour obtenir les n tours alignées le long d’une diagonale,démontrer que pour tout  n ? 2  on a  M(n) ? (n2+ n – 4)/2.

 Solution


L'auteur pdfMichel Lafondet pdfJean-Marie Bretonont résolu le problème.