Aide pour la séance 2
D. Vekemans
    Les isométries du carré sont :
    l'identité ;
    la symétrie centrale ;
    les symétries orthogonales par rapport aux diagonales (au nombre de 2) ;
    les symétries orthogonales par rapport aux médianes (au nombre de 2) ;
    et les rotations de centre l'intersection des diagonales (centre du carré), d'angles respectifs +90° et -90°.
    Au total, le groupe des isométries du carré contient huit éléments.
    Le problème des trois Dames n'admet trivialement pas de solution.
    Le problème des quatre Dames admet deux solutions (b1, d2, a3, c4 ; et c1, a2, d3, b4). Parmi les isométries du carré,
    les isométries positives (i.e. l'identité, la symétrie centrale et les deux rotations) laissent invariante chacune des deux solutions ;
    les isométries négatives (i.e. les symétries orthogonales) échangent les deux solutions.
    On dira que ce problème admet une solution génératrice (soit b1, d2, a3, c4, soit c1, a2, d3, b4), qui génère deux solutions (car en faisant agir le groupe des isométries du carré, on trouve les deux solutions du problème des quatre Dames).
    Le problème des cinq Dames admet dix solutions engendrées par deux solutions génératrices :
    b1, e2, c3, a4, d5 qui génère deux solutions (ici, les isométries positives (du carré) laissent invariante la solution génératrice) ;
    et b1, d2, a3, c4, e5) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).
    Le problème des huit Dames admet quatre-vingt douze solutions engendrées par douze solutions génératrices :
    a1, b5, c8, d6, e3, f7, g2, h4 ) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).
    et a1, b6, c8, d3, e7, f4, g2, h5 ) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).
    et a2, b4, c6, d8, e3, f1, g7, h5 ) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).
    et a2, b5, c7, d1, e3, f8, g6, h4 ) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).
    et a2, b5, c7, d4, e1, f8, g6, h3 ) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).
    et a2, b6, c1, d7, e4, f8, g3, h5 ) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).
    et a2, b6, c8, d3, e1, f4, g7, h5 ) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).
    et a2, b7, c3, d6, e8, f5, g1, h4 ) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).
    et a2, b7, c5, d8, e1, f4, g6, h3 ) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).
    et a3, b5, c2, d8, e1, f7, g4, h6 ) qui génère quatre solutions (ici, l'identité et la symétrie centrale laissent invariante la solution génératrice).
    et a3, b5, c8, d4, e1, f7, g2, h6 ) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).
    et a3, b6, c2, d5, e8, f1, g7, h4 ) qui génère huit solutions (ici, toutes les isométries (du carré) procurent des solutions différentes).

    Pour répondre au questionnaire concernant le problème des huit Dames sans exhiber toutes les solutions :
    L'une des solutions peut être individuellement stable (i.e. invariante) par une isométrie négative (i.e. par une symétrie orthogonale) du carré ? Non, car si on regarde l'une des symétries orthogonales, celle-ci envoie une case sur une case de la même diagonale (lorsque par rapport aux diagonales) ou celle-ci envoie une case sur une case de la même rangée (lorsque par rapport aux médianes).
    Chacune génère sept autres solutions en faisant agir le groupe des isométries du carré ?Non, sinon le nombre de solutions serait un multiple de 8, ce qui n'est pas le cas de 92.
    Il existe au moins douze solutions génératrices (i.e. douze solutions qui ne peuvent se déduire l'une de l'autre par l'une des isométries du carré) ?Oui, car une solution génératrice génère au plus huit solutions, et comme le nombre de solutions est de 92, le nombre de solutions génératrices est supérieur à 92/8=11,5 et donc supérieur ou égal à 12.
    Nous avons aussi pu mettre en lumière deux sous-groupes du groupe des isométries du carré :
    celui des isométries positives (i.e. l'identité, la symétrie centrale et les deux rotations) ;
    celui composé de l'identité et de la symétrie centrale.
    Il en existe d'autres :
    celui composé de l'identité et d'une des symétries orthogonales ;
    celui composé de l'identité, de la symétrie centrale et des symétries par rapport aux diagonales ;
    celui composé de l'identité, de la symétrie centrale et des symétries par rapport aux médianes.
    et enfin le sous-groupe trivial composé uniquement de l'identité.
    Pour dénombrer les solutions du problème des huit Tours, comme chacune des lignes et chacune des colonnes doit contenir une (et une unique) Tour, il convient de dire que
    la Tour dans la colonne "1" peut se placer sur n'importe quelle case de cette colonne (8 possibilités) ;
    la Tour dans la colonne "2" peut, ensuite, se placer sur n'importe quelle case de cette colonne à l'exception de celle de la rangée de la première Tour (7 possibilités) ;
    la Tour dans la colonne "3" peut, ensuite, se placer sur n'importe quelle case de cette colonne à l'exception de celles des rangées des deux premières Tours (6 possibilités) ;
    la Tour dans la colonne "4" peut, ensuite, se placer sur n'importe quelle case de cette colonne à l'exception de celles des rangées des trois premières Tours (5 possibilités) ;
    la Tour dans la colonne "5" peut, ensuite, se placer sur n'importe quelle case de cette colonne à l'exception de celles des rangées des quatre premières Tours (4 possibilités) ;
    la Tour dans la colonne "6" peut, ensuite, se placer sur n'importe quelle case de cette colonne à l'exception de celles des rangées des cinq premières Tours (3 possibilités) ;
    la Tour dans la colonne "7" peut, ensuite, se placer sur n'importe quelle case de cette colonne à l'exception de celles des rangées des six premières Tours (2 possibilités) ;
    la huitième et dernière Tour ne peut se placer sur les cases des rangées des sept premières Tours et a donc sa place imposée. (1 possibilité).
    Au final, on dénombre 8x7x6x5x4x3x2 solutions.
    Pour le problème des Fous, une solution est a1, a2, a3, a4, a5, a6, a7, a8, h2, h3, h4, h5, h6, h7 qui compte 14 Fous.
Retour à la page précédente

Retour à l'index