Math 'O Man : le Blog des Maths

Le jeu d’échecs tri-dimensionnel




Les maths et les échecs vont bien ensemble. Enfin c'est ce que beaucoup de gens pensent, mais si on regarde de plus près je pense que parmi les matheux il n'y en a pas beaucoup plus de joueurs d'échecs sérieux que parmi d'autres professions (c'est une conjecture de ma part, à confirmer...). Personnellement je ne joue presque jamais aux échecs, je n'en ai même pas un jeu à la maison, mais mon grand-père était un excellent joueur, champion de sa ville qui gagnait d'impressionnantes parties simultanées où il passait entre vingt tables différentes.

Evidemment un côté fascinant aujourd'hui pour les mathématiciens-informaticiens c'est de construire des machines qui gagnent contre les humains. Il n'existe qu'un nombre fini de parties d'échecs possibles, et ce fait joue en faveur des ordinateurs car il suffit d'y aller par la force brute et de stocker en mémoire toutes ces parties...

Voici un petit problème.

Combien de tours tri-dimensionnelles faut-il pour dominer un échiquier dans l'espace ?



Partagez-le sur Facebook Tweetez-le ! S'abonner à ce blog ? Envoyer cet article à un ami ? Le soumettre à Netvibes Ajoutez-le à Google Bookmarks

Commentaires


1. Le mercredi 6 octobre 2010 à 22:17, par ana

pour l'instant, j'ai trouvé que le nombre est au plus 64


2. Le jeudi 7 octobre 2010 à 08:52, par JLT

Voici un exemple avec 50 tours :
On place une tour en (8,8,8).
On place une tour sur chaque triplet (i,j,k) tel que 1\le i,j,k\le 7 et tel que i+j+k soit divisible par 7.

Reste à voir si cette configuration est optimale ou non.

P.S. 1. J'ai très peu joué aux échecs dans ma vie.
P.S. 2. Le titre de ce billet aurait pu être "Echec et maths" mais c'est déjà le titre d'un livre de Stella Baruk.


3. Le jeudi 7 octobre 2010 à 17:45, par JLT

Je ferais mieux de réfléchir avant de poster, car il y a une solution avec 32 tours.


4. Le lundi 11 octobre 2010 à 18:30, par JLT

Voici donc ma solution.

On repère les cases de l'échiquier par des numéros de ligne, de colonne et d'étage (donc on considère un échiquier tridimensionnel comme une superposition de 8 échiquiers classiques).

Soient A l'ensemble des cases dont toutes les coordonnées sont \le 4 et B l'ensemble des cases dont toutes les coordonnées sont \ge 5. On place une tour sur chaque case (i,j,k) appartenant à A ou à B telle que i+j+k soit divisible par 4. Il y a ainsi 32 tours. Si (x,y,z) est une case quelconque, alors deux des coordonnées sont \le 4 ou bien deux des coordonnées sont \ge 5. Supposons par exemple que x,y\le 4. Il existe alors un unique k tel que k\le 4 et tel que x+y+k soit divisible par 4, donc la case (x,y,z) est bien dominée par l'une des tours.

Réciproquement, supposons qu'on ait 31 tours. Montrons qu'elles ne dominent pas tout l'échiquier. Comme 8x4=32, il y a un étage contenant au plus 3 tours. Quitte à permuter les étages, on se ramène au cas où il s'agit de l'étage 1. Supposons par exemple que l'étage 1 contienne exactement 3 tours. Soient l (resp. c) le nombre de lignes (resp. colonnes) occupées par ces 3 tours. On a l,c\le 3. De plus, dans l'étage 1, il y a (8-l)(8-c) cases qui ne sont pas dominées par l'une de ces 3 tours, donc il doit y avoir au moins une tour au-dessus. Le nombre total de tours est donc au moins de 3+(8-l)(8-c), ce qui donne l'inégalité (8-l)(8-c)\le 28. Comme 6x5=30, la seule possibilité est que c=l=3.

Le même raisonnement dans le cas où l'étage 1 contient 0, 1 ou 2 tours conduit à une contradiction. On a ainsi montré que l'étage 1 contient exactement 3 tours, qui sont sur 3 lignes et 3 colonnes distinctes. Quitte à permuter les lignes et les colonnes, on se ramène au cas où les tours occupent les cases (1,1,1), (2,2,1) et (3,3,1). Le raisonnement ci-dessus montre qu'au-dessus de chaque case (i,j,1) avec i,j\ge 4 se trouve au moins une tour, ce qui fait déjà 3+25=28 tours. Il y donc au maximum 3 tours qui sont en dehors de l'étage 1 et dont l'indice de ligne ou de colonne est \le 3. Quitte à permuter encore les étages, on peut supposer que ces 3 tours T, T' et T" se trouvent dans les étages 2,3 et 4. Considérons alors les cases (1,2,5), (1,3,5), (2,1,5) et (2,3,5). L'une de ces cases n'est pas à la verticale de l'une des tours T, T' et T'' donc n'est dominée par aucune des 31 tours.


Ajouter un commentaire

Pourquoi ne pas lire aussi :


Vision dans l'espace


Dessin d'un cube transparent et deux interprétations possibles

Quand on dit que quelqu'un a une bonne vision dans l'espace, c'est pour exprimer que cette personne est capable de restituer à partir des informations d'un dessin 2-dimensionnel (par exemple sur une feuille de papier ou à l'écran de votre ordinateur) la position d'un objet dans l'espace 3-dimensionnel.

Ce qui est facile pour certains peut être difficile pour d'autres. Cette vision dans l'espace n'est pas innée à tout le monde, c'est une capacité qu'on peut entraîner ; et dans certaines professions elle est indispensable, par exemple en architecture.

Quand on passe d'une configuration à 3 dimensions vers un dessin à 2 dimensions, forcément on perd certaines informations. Ainsi le dessin d'un cube transparent ci-haut admet deux "vues" possibles qu'on a representées avec deux cubes opaques.
Tandis que la première de ces deux possiblilités ne semble pas poser beaucoup de problèmes, la deuxième n'est pas évidente pour tous. C'est pourquoi ci-dessous je la reprends en ajoutant deux hommes, l'un portant le cube, l'autre se promenant dessus. Cela clarifie la perspective.

Une cube transparent et deux interprétations possibles

Exercice
Vous pouvez maintenant faire un exercice : cachez les deux cubes à droite, fixez le cube à gauche et essayez de passer d'une perspective à l'autre ! C'est un bon entraînement...

Souvent on utilise aussi des traits en pointillets pour distinguer les bords invisibles des bords visibles:

Une cube transparent et deux interprétations possibles

Un autre exercice
Voici un autre exercice basé sur le même concept mais qui exige plus d'imagination.

Quelle jambe est levée, la gauche ou la droite ?

On peut voir de deux manières la silhouette de la danseuse ci-dessus:

  • La fille nous montre son dos. Alors sa tête est légèrement inclinée vers sa droite et c'est sa jambe droite qui est levée.
  • Nous voyons le visage de la fille. Alors sa tête est légèrement inclinée vers sa gauche et c'est sa jambe gauche qui est levée.

Essayez de passer d'une vue à l'autre ! C'est beaucoup plus dur qu'avec les cubes. Et ça devient encore plus difficile, si elle tourne.

  • Soit elle tourne sur sa jambe gauche. Un oiseau au-dessus d'elle la verrait alors tourner dans le sens des aiguilles d'une montre.
  • Soit elle tourne sur sa jambe droite. Un oiseau au-dessus d'elle la verrait alors tourner contre le sens des aiguilles d'une montre.

Fille qui tourne

Quant à moi, je vois spontanément la première possibilité. Mais quelques fois j'arrive à adopter la deuxième vue, et seulement si je fais un effort. Et j'y reste bloqué, c'est-à-dire immédiatement après je ne peux plus revoir la première vue.

Il est aussi intéressant de tenir compte de l'ombre de la jambe soulevée. Comme on ne voit qu'une silhouette de la danseuse on déduit que l'éclairage est placé derrière la fille ; donc quand l'ombre du pied soulevé appraît en bas de l'image cela signifie que ce pied est plus loin du spectateur que pendant la phase où l'ombre est hors du cadre. Le seul sens possible est alors le deuxième !

Paradoxes
Lorsqu'on essaie de coder un objet 3D dans un dessin 2D, on peut perdre de l'information, mais on peut aussi créer des informations contradictoires, c'est-à-dire on peut faire des représentations pour lesquels il n'existe pas d'objet dans l'espace à 3 dimensions l'ayant pour image — ce qu'a fait l'artiste Maurits Cornelis Escher avec son escalier impossible

Maurits Cornelis Escher : Escalier

ou le mathématicien Roger Penrose avec son fameux triangle impossible (aussi tripoutre ou tribarre).

triangle de Penrose, triangle impossible