Inscription / Connexion Nouveau Sujet
Le problème du cavalier
Bonjour,
Un cavalier situé sur une case quelconque se déplace selon une direction horizontale ou verticale de deux cases dans un sens choisi puis d'une case sur la direction perpendiculaire. Ainsi, le cavalier situé en E4 peut atteindre au coup suivant l'une des cases : C3, C5, D2, D6, F2, F6, G3, G5.
Le problème est le suivant : un cavalier est placé sur la case B1. On veut savoir combien de coups au minimum seront nécessaires au cavalier pour atteindre la case H8 et de combien de manières il peut atteindre cette case en un nombre minimal de coups.
Attention : il ne suffit pas de trouver une réponser mais aussi d'être sur qu'il ne peut pas y avoir d'autre réponse. Pour cela, on peut utilier les outils mis à disposition par les mathématiques. Par exemple ici, la façon dont on peut repérer un point dans un plan, ou encore la façon dont on peut décrire un déplacement à l'aide d'un vecteur.
Il faut 5 coups au minimum.
3 coups (2 cases à droite et 1 vers l'avant). Appelons ces coups, des coups de type A.
1 coup (1 case à droite et 2 vers l'avant). Appelons ce coup, un coups de type B.
1 coup (1 case à gauche et 2 vers l'avant). Appelons ce coup, un coups de type C.
On ne peut pas jouer le coup de type C en dernier, sinon on sort de l'échiquier.
Possibilités:
CAAAB
CBAAA
CABAA
CAABA
BCAAA
ACBAA
ACABA
ACAAB
BACAA
ABCAA
AACBA
AACAB
BAACA
ABACA
AABCA
Il y a 15 manières de jouer.
-----
Sauf si je me suis planté. 
Merci beaucoup !
Par contre, la prof veut (apparemment) qu'on utilise les vecteurs, or je ne vois pas comment on peut s'en servir pour montrer que 5 est le minimum de coups...
Pourquoi pas avec des vecteurs.
Les déplacements possibles d'un cavalier en vecteurs sont:
(1 ; 2) (+1 case en abscisse et +2 cases en ordonnées)
(2 ; 1)
(-1 ; -2)
(-2 ; -1)
(1 ; -2)
(2 ; -1)
(-1 ; 2)
(-2 ; 1)
Or pour passer de la case B1 à H8, cela représente un vecteur (6 ; 7)
Pour obtenir 7 (en ordonnées), le plus court est 2 + 2 + 2 + 1
mais alors l'autre composante est au max de 1 + 1 + 1 + 2 = 5 alors qu'il faut 6.
--> on ne peut pas y arriver en 4 coups.
On essaie alors en 5 coups:
2 + 2 + 1 + 1 + 1 par exemple pour une composante, l'autre étant:
1 - 1 + 2 + 2 + 2
--> c'est possible en 5 coups minimum.
-----
Sauf distraction.
Bonsoir,
3 mois après, la prof nous a enfin rendu ce devoir. Voici la correction qu'elle nous a donnée:
J-P, tu pourras voir qu'il y avait 19 positions de se déplacer.
On choisit un repère (O;I,J) : par exemple, la case E4 est associé au point (5;4).
Les coordonnées des vecteurs qui décrivent les mouvements du cavalier sont :
(-2;-1);(-2;1);(-1;-2);(-1;2);(1;-2);(1;2);(2:-1);(2;1).
Les coordonnées sont toujours pour l'une des composantes 1 ou -1 associées à 2 ou -2 pour l'autre composante. La somme des valeurs absolues des deux coordonnées pour un vecteur est toujours 3 ce qui correspond au déplacement d'une case dans une direction et de deux cases dans la direction perpendiculaire.
Si un cavalier est situé sur une case blanche, en un coup, il ne peut atteindre qu'une case noire. Si au départ, le cavalier se trouve sur une case noire, en un coup, il ne peut atteindre qu'une case blanche.
Un trajet du cavalier pour aller de la case B1 à la case H8 peut être décrit par les coordonnées des points suivants : (2;1)->(4;2)->(6;3)->(8;4)->(7;6)->(8;8)->.
Si l'on nomme u le vecteur de coordonnées (2;1), v celui de coordonnées (-1;2) et w celui de coordonnées (1;2), ce trajet correspond à la translation de vecteur d=u+u+u+v+w.
Un deuxième déplacement qui permet au cavalier d'atteindre la case H8 en partant de la case B1 peut être : (2;1)->(3;3)->(4;5)->(5;7)->(7;6)->(8;8). Si w (1;2) et t (2;-1), on a d'=w+w+w+t+w.
Dans les deux cas, le nombre de coups nécessaires est impair. En effet, comme B1 est une case blanche et H8 une case noire, le nombre de coups doit donc toujours être impair.
Combien de coups au minimum seront nécessaire au cavalier pour atteindre la case H8 ?
Si l'on observe les coordonnées du vecteur égal à la somme des déplacements, par exemple du vecteur d ou d' dans les deux cas précédents, ce vecteur doit avoir pour coordonnées (6;7). Avec des 2 et 1, on peut décomposer additivement 7 de la façon suivante : 7=2+2+2+1. Ce qui correspondrait à trois fois le vecteur u et une fois le vecteur w. Et il faudrait un minimum de 4 coups. Mais on a dit que le nombre de coups devait être impair. Comme on a trouvé un déplacement possible en 5 coups, le nombre minimum est donc 5.
On doit décomposer additivement 6 et 7 à l'aide de cinq termes pris parmi les nombres 2,-2, 1 et -1.
Le déplacement d qui convient correspond à 6=2+2+2-1+1 et 7=1+1+1+2+2 (trois termes égaux à 2). Le déplacement d' correspond à 6=1+1+1+2+1 et 7=2+2+2-1+2 (un terme égal à 2).
Si l'on voulait ne mettre aucun terme égal à 2 dans la décomposition de 6, on obtiendrait au mieux 5 comme somme donc c'est impossible (1+1+1+1+1=5).
Si l'on voulait mettre deux termes égaux à 2 dans la décomposition de 6, on ne peut obtenir que 7 ou 5 donc c'est impossible (2+2+1+1+1 ou 2+2+1+1-1).
Si l'on voulait mettre quatre termes égaux à 2 dans la décomposition de 6, il faudrait avoir 2+2+2+2-2=6, mais alors on ne pourrait obtenir 7 on aurait au mieux 1+1+1+1+1=5.
Il est bien sûr impossible de décomposer 6 avec 5 termes égaux à 2.
Ainsi, les seules décompositions possibles sont celles correspondants à d=u+u+u+v+w et d'=w+w+w+t+w. Mais les positions des vecteurs u, v et w dans d et celles de t et w dans d' peuvent être différentes. Pour d, le vecteur v peut occuper les quatre premières places mais pas la cinquième (on sortirait de l'échiquier) et pour chaque position de v, il y a quatre positions de w, ce qui donne 4x4=16 manières de se déplacer. Pour d', le vecteur t ne peut occuper ni la première position, ni la dernière (on sortirait de l'échiquier) mais il y a trois positions possibles et donc trois autres manières de se déplacer.
Il y a en tout 19 manières de se déplacer pour le cavalier en un nombre minimal de coups de la case B1 à la case H8.
Salut Estelle,
3 mois après, la prof nous a enfin rendu ce devoir.
Ha ha, c'est bien de donner des devoirs a la maison rigolos et interessants mais il faut les corriger !!
Cela dit, cela valait le coup d'attendre parce que la demo est belle.
Si les problemes de cavalier t'interessent, un autre exercice consiste a visiter une fois et une seule toutes les cases de l'echiquier avec un cavalier, en circuit ferme ou ouvert.
minkus
Bonjour Minkus,
je pense qu'on aura aussi le devoir sur les moyennes dans 3 mois !!
Pour le pb du cavalier qui visite toutes les cases de l'échiquier, on peut partir de n'importe quelle case ??
Bonjour,
Oui la case de depart n'a pas d'importance. Il y a des circuits fermes ou la case d'arrivee est la meme que la case de depart mais ce n'est pas une obligation.
)
Annuler
connectez vous