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 ?
pour l’instant, j’ai trouvé que le nombre est au plus 64
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.
Je ferais mieux de réfléchir avant de poster, car il y a une solution avec 32 tours.
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 8×4=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 6×5=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.
La 3D est décidément partout, il va falloir que je me remettre aux échecs, un jeu qui met vraiment en relief nos aptitudes mathématiques.