Grille et cavalier

kolotoko
kolotoko
dans Combinatoire et Graphes
Bonjour,
soit une grille carrée d'ordre n formée de n x n cases (si n = 8 la grille est un échiquier, si n = 10 la grille est un damier ).

Combien de segments reliant deux cases selon le pas du cavalier au jeu d'échec dénombrez-vous ?
On notera f(n) ce nombre de segments.

Bien cordialement.
kolotoko

Réponses

  • bisam
    bisam
    En premier jet, à brûle-pourpoint, je répondrais $f(n)=4(n-1)(n-2)$.
  • lourrran
    lourrran
    J'arrive à 4(n-4)(n+1)+24, c'est à dire comme bisam :)
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • PetitLutinMalicieux
    PetitLutinMalicieux
    Bonjour

    Pour tout segment [AB], il y a le déplacement de A vers B et le déplacement de B vers A. Je vais volontairement compter les segments en double et je diviserais par 2 à la fin.

    On considère 3 types de zones.
    • La zone suffisamment centrale pour permettre 8 mouvements.
    • Les zones latérales permettant seulement 4 mouvements.
    • Les zones encoignées qui ne permettent que 2 mouvements.

    Soit n, le nombre de cases sur le côté d'un plateau (damier, échiquier, goban, etc).
    Le nombre de segments longs de $\sqrt 5$ cases est $q=\frac{8(n-4)^2+4*4*2*(n-4)+4*2*2*2}{2}=4(n-2)^2$113762
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • bisam
    bisam
    Je compte ligne par ligne pour un déplacement de cavalier $(1,-2)$ en coordonnées cartésiennes :
    Il y a alors $n-1$ positions de départ sur la ligne du haut et $n-2$ lignes de départ.
    On multiplie par 4 le nombre de déplacements obtenus pour tenir compte des autres orientations sans qu'il y ait de doublons : il suffit de tourner 4 fois d'un quart de tour l'ensemble des positions obtenues. d'effectuer une symétrie axiale puis une rotation d'un quart de tour

    Finalement : $f(n)=4(n-1)(n-2)$.

    [Edit : Correction suite à une remarque pertinente de PetitLutinMalicieux]
  • nicolas.patrois
    nicolas.patrois
    J’ai dû m’y prendre à plusieurs fois pour comprendre ce que kolotoko demandait : le nombre d’arêtes du graphe sous-jacent.
    Remarquez que ce n’est pas le même avec un chameau (page 34).
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • PetitLutinMalicieux
    PetitLutinMalicieux
    (1;-2) et (2;-1) relevant de la symétrie axiale, j'ai un doute sur la rotation magique.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • PetitLutinMalicieux
    PetitLutinMalicieux
    @Nicolas : la page 34 du pdf qui est la page 29 du document. :-S Faut suivre. :-)
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • bisam
    bisam
    PetitLutinMalicieux : tu as raison. J'ai voulu simplifier à l'extrême et je me suis pris les pieds dans le tapis.
    Cependant, avec une symétrie axiale puis une rotation d'un quart de tour, on a le même compte et cette fois-ci pas de doublons.

    Je corrige plus haut.
  • lourrran
    lourrran
    @PLM
    Ii y a pas mal de cases qui permettent 6 déplacements, 4 (n-4) cases en l'occurrence, les cases B3 à B6 par exemple sur un échiquier classique.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • PetitLutinMalicieux
    PetitLutinMalicieux
    Ah ! Je me suis trompé. Il n'y a vraiment pas 3 zones mais 6. Dans chaque coin, il y a une case à 2 mouvements, 2 cases à 3 mouvements (notez l'imparité), et une case à 4 mouvements. Et même erreur dans les parties latérales. Certaines cases ont six mouvements et non 4.

    Nous sommes donc d'accord sur 4(n-1)(n-2).
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • kolotoko
    kolotoko
    Bonjour,

    on a bien f(n) = (2n - 3)2 - 1.

    Pour n>3, il y a des cases à 2 mouvements, des cases à 3 mouvements, des cases à 4 mouvements, des cases à 6 mouvements et des cases à 8 mouvements.
    On trouve la suite 0, 0, 8, 24, 48, 80, 120, 168, 224, 288, 360, .... pour n = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
    Bien cordialement.

    kolotoko
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 24

CidrolinEtienne91NicoLeProfOShineetanchemtho5 +18 Invités