Abonnez-vous

Hexagones magiques


Gianni Sarcone



« Nihil novi sub sole ! » (soit « Rien de nouveau sous le soleil ») affirmaient déjà nos ancêtres. Cela s'applique tout particulièrement au monde des jeux.

 

L’aristocrate Choi Seok-jeong (1646–1715), qui était féru de mathématiques, était par ailleurs un petit fonctionnaire du gouvernement coréen durant la période Joseon, qui s’étend de 1392 à 1897. En 1700, il écrivit et publia le Gusuryak, un recueil de mathématiques médiévales, dans lequel figure l’une des premières études sur les carrés latins… précédant sur ce sujet le Suisse Leonhard Euler (1707–1783) d’au moins soixante-sept ans ! Seok-jeong est, en effet, l’un des premiers à réaliser un carré gréco-latin en superposant deux carrés latins orthogonaux l’un à l’autre.
 





 




Un carré latin d’ordre n est un tableau de n lignes et n colonnes contenant n symboles (par exemple les entiers de 1 à n) de sorte que chacun d’entre eux apparaisse une fois, et une seule, dans chaque ligne et chaque colonne. Deux carrés latins sont orthogonaux s’ils ne possèdent aucun symbole en commun.
Deux carrés latins C et S étant donnés (avec les symboles c1, c2… cn pour C et les symboles s1, s2sn pour S), un carré gréco-latin G d’ordre n est alors un tableau de n lignes et n colonnes contenant les n2 couples du produit cartésien C × S, tel que toute ligne et toute colonne de G contienne exactement une fois chaque symbole de C (en première position) et chaque symbole de S (en seconde position). Si C et S sont orthogonaux, leur superposition produit un carré gréco-latin (en posant que l’élément à l’intersection de la ligne i et de la colonne j de G est (ci, sj)).

Seok-jeong est même allé plus loin dans ses recherches. Il a inventé un problème nouveau, très captivant, dénommé problème de la tortue hexagonale (connu en anglais sous l’acronyme HTP). Il s’agit d’un graphe « magique » à réseau hexagonal, ressemblant aux motifs que l’on retrouve sur les carapaces de certaines tortues, d’où le nom.
Le but de ce jeu est d’assigner aux N sommets du réseau hexagonal les entiers de 1 à N de telle sorte que la somme des nombres aux sommets de chaque hexagone soit la même (la constante magique).


 





La constante magique est égale à 93.


 

L’originalité du jeu est que la constante magique varie si les nombres de 1 à 30 sont réarrangés différemment ! Par exemple, dans la figure suivante, on vous dévoile comment résoudre un HTP de constante magique 95. À votre tour, sauriez-vous résoudre des HTP, avec N = 30, ayant des constantes magiques allant de 77 à 109 ?

 

 


Ici, la constante magique vaut 95.

 



Bien que, comme pour beaucoup de problèmes combinatoires de ce genre, il n’existe pas à ce jour d’algorithmes performants capables de générer des solutions optimales pour un HTP arbitraire, le graphe peut se simplifier en un réseau rectangulaire.

 







 Du réseau hexagonal à une matrice rectangulaire.