Carrés Magiques

Définition

Un carré magique de côté L contient les nombres entiers compris entre 1 et L², disposés de telle sorte que la somme des nombres contenus dans une même ligne, une même colonne ou une même diagonale soit la même dans les trois cas.

Il existe naturellement des variantes de ce genre de problème. Par exemple, on peut imposer que le carré ne contienne que des nombres premiers. On peut au contraire relâcher les contraintes, par exemple en n'imposant plus que les nombres présents soient tous distincts.

Généralités

Pour obtenir la somme commune aux lignes, aux colonnes et aux diagonales, il faut additionner les nombres qui se trouvent dans le carré, et diviser la somme par le côté L du carré. Si la somme ( appelons-la S ) n'est pas multiple de L, c'est qu'il n'existe pas de carré magique de côté L contenant ces nombres.

Exemple pour les nombres de 1 à L² : S = (L²(L²+1)/2)/L donc S = (L²+1)L/2

L'indication ci-dessus montre clairement qu'il n'existe pas de carré magique de côté trois contenant les neuf nombres premiers de 2 à 23, car leur somme n'est pas multiple de trois.

Si l'on n'impose pas que les cases du carré ne contiennent que des nombres entiers, alors on peut montrer que l'ensemble de ces carrés est un espace vectoriel de dimension (L-1)²-1. La démonstration n'est pas difficile, mais elle est un peu calculatoire. Pour la parcourir, cliquer ici.

Méthode par superposition de deux masques.

Cette méthode est assez ancienne, puisque Frenicle du Bessy, au XVIIème siècle, l'utilisait déjà. Elle donne beaucoup de carrés magiques, sans les donner tous puisque elle n'est pas valable pour toutes les dimensions.

Pour simplifier, on remplira le carré avec les nombres de 0 à L²-1.

On commence par remarquer que les nombres de 0 à L²-1 s'écrivent, en base L, sur deux chiffres compris entre 0 et L-1.

Un carré magique peut donc être considéré comme la superposition de deux carrés ( pas forcément magiques ) contenant le premier et le second de ces chiffres. On appellera de tels carrés "masques".

Exemple pour L = 5 :

:       0 | 1 | 4 | 3 | 2 |   | 2 | 4 | 0 | 3 | 1 |   | 2  | 9  | 20 | 18 | 11 |
:       3 | 2 | 0 | 1 | 4 |   | 0 | 3 | 1 | 2 | 4 |   | 15 | 13 | 1  | 7  | 24 |
: 5   * 1 | 4 | 3 | 2 | 0 | + | 1 | 2 | 4 | 0 | 3 | = | 6  | 22 | 19 | 10 | 3  |
:       2 | 0 | 1 | 4 | 3 |   | 4 | 0 | 3 | 1 | 2 |   | 14 | 0  | 8  | 21 | 17 |
:       4 | 3 | 2 | 0 | 1 |   | 3 | 1 | 2 | 4 | 0 |   | 23 | 16 | 12 | 4  | 5  |

En particulier, on peut créer un carré magique en additionnant deux masques magiques, i.e. deux carrés magiques ne contenant que les nombres de 0 à L-1. (C'est le cas pour l'exemple ci-dessus )

La méthode de créations de masques exposée ci-dessous est valable pour créer des carrés magiques dont le côté n'est multiple ni de 2, ni de 3 ( on le montre plus loin ).

A chaque ligne, l'abscisse de la case 0 augmente d'un nombre n.

Quand on arrive à droite du carré, on recommence en partant de la gauche ( pour l'exemple, n=2 et 3, respectivement pour le premier et le second masque ).

Le choix de n doit respecter certaines conditions données ci-après.

Pour créer un des masques, on commence par écrire, sur la première ligne, les nombres 0 à L-1, dans un ordre quelconque, de gauche à droite. Puis on fait de même avec les lignes suivantes, en conservant le même ordre, mais en décalant de n cases vers la droite par rapport à la ligne précédente.

Comme chaque ligne contient les nombres de 0 à L-1, la somme des nombres d'une ligne est indépendante de la ligne. La somme des nombres présents sur une colonne ou une diagonale doit être la même que pour une ligne : une condition suffisante est que chaque colonne et chaque diagonale contienne tous les nombres de 0 à L-1. Ceci impose :

pgcd( n, L ) = 1 ( condition sur les colonnes ) (*)
pgcd( n-1, L ) = 1 ( condition sur la première diagonale ) (**)
pgcd( n+1, L ) = 1 ( condition sur la seconde diagonale ) (***)

Pour obtenir le carré final, on multiplie par L la valeur de chaque case du premier masque, et on l'additionne à la case correspondante du second.

Pour créer le premier masque, on prend n=x, et pour le second n=y. Pour être sûr que le carré résultant de l'addition des deux masques soit bien magique, il faut prendre x et y parmi les valeurs admissibles pour n, en imposant de surcroît :

pgcd( x-y, L ) = 1. (****)

En effet, deux occurrences d'une valeur donnée dans l'un des masques doivent correspondre à des valeurs différentes dans l'autre masque, si l'on veut que le carré résultat contienne des nombres tous différents ( c'est à cause de l'unicité de l'écriture en base L ).

Résumé : il suffit donc de remplir les conditions (*), (**), (***), (****) pour obtenir un carré magique par cette méthode.

Validité de la méthode:

Comme, les trois nombres consécutifs n-1, n et n+1, comptent au moins un multiple de deux et un multiple de trois, les trois premières conditions imposent que L ne doit être multiple ni de 2 ni de 3. On trouve alors que n doit être de la forme n=6k+1 ou n=6k+5, avec k entier.

Si, pour L vérifiant cette condition, on prend x=L-1 et y = L-2, alors les quatre conditions sont vérifiées, ce qui démontre la validité de cette méthode de construction pour de telles valeurs de n. On peut prendre d'autres valeurs de x et y !

Nombre de carrés obtenus :

Si on suppose x et y fixés, on a, pour chaque masque, L! manières d'écrire la première ligne.

Cela conditionne le résultat et on a donc (L!)² carrés magiques imaginables, à x et y fixés. Le nombre total de carrés que l'on peut obtenir par cette méthode est donc de (L!)² multiplié par le nombre de manières de choisir x et y en respectant les quatre conditions.

Pour en savoir plus, vous pouvez regarder l'autre page du site sur les carrés magiques, ou bien aller voir les liens.