Nombre de déplacements minimaux et maximaux — Les-mathematiques.net The most powerful custom community solution in the world

Nombre de déplacements minimaux et maximaux

Bonsoir
Je cherche des pistes de recherches/démonstrations autres que par la programmation informatique du problème suivant.

Dans un échiquier classique (8x8), quel est le nombre de déplacements minimaux et maximaux d'une tour pour paver tout l'échiquier sans repasser par le même point.
Une tour se déplaçant horizontalement ou verticalement.

J'ai essayé de poser le problème sous forme de programmation linéaire.
Si h et v sont le nombre de déplacements horizontaux et verticaux, on a :
v <= 64
h <=64
On cherche le minimum ou maximum de v+h

Je n'arrive pas à écrire la contrainte : "paver tout l'échiquier sans repasser par le même point."
Merci pour vos pistes.
JeremyJeff

Réponses

  • Bonjour

    Nombre minimum: 63 puisqu'il faut passer au moins une fois par chacune des 64 cases. Ceci est vraie avant même de parler de la moindre méthode.
    Nombre maximum: 63 puisqu'il est interdit de repasser par le même point. Ceci est vraie avant même de parler de la moindre méthode.

    Quel était l'esprit du problème de départ ?
  • Que veut dire "paver" dans ce contexte ? Cela veut-il dire "survoler les cases" ?
    Dans ce cas, on peut arriver à bien moins de déplacements.
  • Bonsoir,

    Paver , signifie passer une et une seule fois par chaque case de l'échiquier.

    En cherchant des déplacements sur des longueurs de 2 ou de 1 (la tour se déplace verticalement ou horizontalement) , j'arrive à 56 déplacements, qui est le nombre de déplacements maximaux que je trouve.
    L'idée étant la suivante: Pour un déplacement de tours assez grand (> 3), on peut trouver une déplacement intermédiaire.


    Pour le nombre de déplacements minimaux, on essaie de se déplacer au maximum dans une direction (disons horizontalement) (7 ou 8 cases) et au minimum dans une autre (une case).
    J'arrive alors à 16 déplacements.

    Une autre approche serait de dire , comment décomposer le nombre 64 en sommes maximales ou minimales:

    MIN : 64 = ( 8 + (1 + 7) + (1 + 7) + (1 + 7) + (1 + 7) + (1 + 7) + (1 + 7) + ( 6 + 1 + 1) ) , et on arrive à 16 termes, donc 16 déplacements

    MAX : 64 = ( 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + + ( 1 + 1 + 1 + 1 + 1 + 1 ) + 2 + ( 1 + 1 + 1+ 1 + 1) + 2 + ( 1 + 1 + 1 + 1 + 1 +1 ) + 3 + .... ) et on arrive à 56 termes donc 56 déplacements


    Ceci est plus de la "bidouille" qu'autre chose.

    Peut-on théoriser ceci et trouver une démonstration qu tienne la route.
    Décomposition d'entiers, théorie des graphes ... Je suis preneur.

    Merci
  • Ahhhhh. Donc c'est Bisam qui avait raison. Une case survolée est une case parcourue.

    Par contre, pour le maximum, j'en démords pas. 63 déplacements pour atteindre les 64 cases. Pas 56. Sinon, tu en as oublié.
    Pour le minimum, il y a plus rapide. 15 coups, partant de a1, en atteignant le centre par un mouvement spiral ou escargot.

    Quant à la démonstration, j'aurais tendance à faire une exploration informatique. :-) Considères-tu la démonstration du théorème des quatre couleurs par l'informatique comme valide ? Ici, c'est pareil.
  • bonsoir,

    il me semble que le nombre maximum de déplacements est 63 et le nombre minimum 15
  • Jeremyjeff a écrit:
    Paver , signifie passer une et une seule fois par chaque case de l'échiquier.
    et s'y poser ? Ou la survoler ?
    Il y a deux interprétations, ce qui donne un dialogue de sourds.

    Cordialement.
  • Survoler

    La tour passe, sans forcément s'arrêter à toutes les cases, mais elle laisse une trace (imaginons la trace d'une craie).
    A la fin du parcours, toutes les cases ont été recouvertes.
    Du coup je trouve moins que 64 pour le maximum.

    Théorème des quatre couleurs pour démonstration ? intéressant
    Et quelles sont les quatre couleurs ?

    Cordialement, jeremyJeff
  • Et si on rajoute comme hypothèse, de former un circuit fermé ?
    On part d'un point et on parcourt tout l'échiquier (en le survolant) , sans passer par le même point, jusqu'à arriver au point de départ.

    Tout cela pour dire qu' une contrainte supplémentaire peut changer complètement la méthode de résolution.
    Sauf, que de méthodes, je n'en ai pas ....
  • Au départ, tu cherchais une chaîne hamiltonienne dans le graphe dans lequel les 64 nœuds sont les positions possibles de la tour et les arêtes sont les déplacements possibles. Maintenant que tu parles de "circuit fermé", tu cherches un cycle hamiltonien dans le même graphe.

    "Du coup je trouve moins que 64 pour le maximum. "
    Oui. 63.
  • Bonsoir,

    Pour le nombre de déplacements maximum, en circuit fermé, j'ai fait une figure.
    Voici ce que je trouve.

    Voyez-vous d'autres circuits ?


    Cordialement110322
  • Il suffit de s'arrêter à toutes les cases.110324
    110326
  • Exact, et si on rajoute une contrainte supplémentaire :
    Nombre de virages maximal ou minimum

    Du coup on cherche des graphes hamiltoniens de 64 noeuds, mais comment exprimer cette contrainte ?
    La solution est-elle unique ?

    A tâtons ?

    Cordialement
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!