Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
218 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Nombre de déplacements minimaux et maximaux

Envoyé par jeremyjeff 
Nombre de déplacements minimaux et maximaux
il y a sept mois
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



Edité 2 fois. La dernière correction date de il y a sept mois et a été effectuée par AD.
Re: Nombre de déplacements minimaux et maximaux
il y a six mois
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 ?
Re: Nombre de déplacements minimaux et maximaux
il y a six mois
avatar
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.
Re: Nombre de déplacements minimaux et maximaux
il y a six mois
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
Re: Nombre de déplacements minimaux et maximaux
il y a six mois
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. smiling smiley Considères-tu la démonstration du théorème des quatre couleurs par l'informatique comme valide ? Ici, c'est pareil.
Re: Nombre de déplacements minimaux et maximaux
il y a six mois
bonsoir,

il me semble que le nombre maximum de déplacements est 63 et le nombre minimum 15
Re: Nombre de déplacements minimaux et maximaux
il y a six mois
Citation
Jeremyjeff
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.
Re: Nombre de déplacements minimaux et maximaux
il y a six mois
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
Re: Nombre de déplacements minimaux et maximaux
il y a six mois
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 ....
Re: Nombre de déplacements minimaux et maximaux
il y a six mois
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.
Re: Nombre de déplacements minimaux et maximaux
il y a six mois
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 ?


Cordialement



Edité 2 fois. La dernière correction date de il y a six mois et a été effectuée par jeremyjeff.


Re: Nombre de déplacements minimaux et maximaux
il y a six mois
Il suffit de s'arrêter à toutes les cases.


Re: Nombre de déplacements minimaux et maximaux
il y a six mois
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
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 604, Messages: 1 497 695, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.


Ce forum
Discussions: 886, Messages: 7 497.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page