.. title: Carrés magiques (suite)
.. raw:: html
.. _sommaire:
Programme des réjouissances
---------------------------
Cette page propose de montrer que les carrés magiques d'ordre n, (à
éléments réels) forment un espace vectoriel de dimension
``N = (n - 1)² - 1``. Pour cela, on procède en plusieurs étapes:
- `L'ensemble des carrés magiques d'ordre n est un espace
vectoriel. <#espace_vect>`__
- `Tous les coefficients du carré se déduisent de (n-1)² - 1
coefficients bien choisis. <#expr_coeffs>`__
- `Notations <#NOTATIONS>`__
- `Analyse <#ANALYSE>`__
- `Synthèse <#SYNTHESE>`__
- `Conclusion <#CONCLUSION>`__
- `Corollaires et exercices <#Corollaires_exercices>`__
.. _espace_vect:
L'ensemble des carrés magiques d'ordre n est un espace vectoriel
----------------------------------------------------------------
Tout d'abord, il est clair que l'ensemble des carrés magiques d'ordre n
est un sous-espace vectoriel de l'espace des matrices carrées d'ordre n
:
- Si on multiplie, par un réel k quelconque, tous les coefficients d'un
carré magique, on obtient un carré magique.
- Si l'on additionne deux carrés magiques, terme par terme, on obtient
encore un carré magique.
CQFD quand à la nature d'espace vectoriel.
`(retour au sommaire) <#sommaire>`__
.. _expr_coeffs:
Tous les coefficients en fonction de (n-1)²-1 coefficients bien choisis
-----------------------------------------------------------------------
| Montrons maintenant que la dimension de cet espace est
``N = (n - 1)² - 1``.
| Pour cela, procédons par analyse-synthèse : montrons d'abord que la
donnée de N coefficients du carré, bien choisis, impose la valeur des
autres coefficients. Puis vérifions que les coefficients ainsi
déterminés correspondent bien à un carré
`(retour au sommaire) <#sommaire>`__
.. _NOTATIONS:
NOTATIONS
~~~~~~~~~
| Divisons le carré en zones de couleur, dont chacune correspond à une
lettre (voir schéma).
| Pour ne pas alourdir les notations, la somme des coefficients d'une
zone est aussi désignée par la lettre qui correspond à la zone.
| Appelons en outre:
- t la somme des coefficients de la diagonale principale de D (celle
entre a et d, exclus)
- u la somme des coefficients de l'autre diagonale de D (entre b et c,
exclus)
.. raw:: html
Remarque : On a pris n=5 pour le schéma ci-dessus, mais la démonstration
qui suit concerne toutes les tailles n>=3.
`(retour au sommaire) <#sommaire>`__
.. _ANALYSE:
ANALYSE
~~~~~~~
| Supposons donc que le carré est magique et que les coefficients des
zones D, w et v sont connus.
| Appelons S la somme des termes de chaque ligne, de chaque colonne et
de chaque diagonale.
| Chaque terme de p est imposé de manière unique par S (puisque les
termes de v et D sont connus)
| Alors la somme des termes des (n-2) colonnes centrales est
``v+ D + p = (n - 2)S`` donc ``p = (n - 2)S - (v + D) (*)``.
| De même, chaque terme de q est imposé de manière unique par S (puisque
les termes de w et D sont connus).
| Alors la somme des termes des (n-2) colonnes centrales est
``w + D + q = (n - 2)S`` donc ``q = (n - 2)S - (w + D) (**)``.
| (On peut déduire ce résultat du précédent, en utilisant la symétrie
par rapport à la diagonale principale).
Chercher le carré magique revient donc à trouver tous les coefficients
(sauf ceux de p et q) et la somme S.
A présent, le carré est magique si et seulement si S est la somme des
éléments des termes de chacun des 4 côtés, ainsi que de chacune des 2
diagonales. Une condition nécessaire et suffisante, pour que le carré
soit magique, se traduit donc par le système linéaire suivant, à 6
équations pour 5 inconnues qui sont a,b,c,d et S.
Diagonale principale
: ``S = a + t + d``
``(1)``
Seconde diagonale
: ``S = b + u + c``
``(2)``
Première ligne
: ``S = a + v + b``
``(3)``
Première colonne
: ``S = a + w + c``
``(4)``
Dernière ligne
: ``S = c + p + d``
ce qui, d'après (*), équivaut à : ``(3 - n)S = c + d - (v +D) (5)``
)
Dernière colonne
: ``S = b + q + d``
ce qui, d'après (**), équivaut à : ``(3 - n)S = b + d - (w + D) (6)``
Dans la suite des calculs, on s'efforce de conserver la symétrie ( en
particulier entre 3 et 4, et entre 5 et 6) par rapport à la diagonale
principale.
+--------------------+-------------------+----------+
| (1) équivaut à : | ``a = S - t - d`` | ``(1')`` |
+--------------------+-------------------+----------+
| donc (3) devient : | ``d = b + v - t`` | ``(3')`` |
+--------------------+-------------------+----------+
| et (4) devient : | ``d = c + w - t`` | ``(4')`` |
+--------------------+-------------------+----------+
| Posons ``(3'') = (3') + (4')`` et ``(4'') = (3') - (4')``.
| Posons ``(5'') = (5') + (6')`` et ``(6'') = (5') - (6')``
En particulier on a : ``(4") 0 = (b-c) + (v-w) (6") 0 = (c-b) + (w-v)``
| Les équations (4") et (6") sont équivalentes : on ne garde que (4")
| On obtient ainsi un système à 5 équations et 5 inconnues,
rigoureusement équivalent au précédent:
````
+-------+---------+---------------------------+
| (1') | a | = S - t - d |
+-------+---------+---------------------------+
| (2) | S | = (b+c) + u |
+-------+---------+---------------------------+
| (3'') | 2d | = (b+c) + (v+w) - 2t |
+-------+---------+---------------------------+
| (4'') | 0 | = (b-c) + (v-w) |
+-------+---------+---------------------------+
| (5'') | 2(3-n)S | = (b+c) + 2d - (v+w) - 2D |
+-------+---------+---------------------------+
| Dans (5"), on remplace 2d par l'expression donnée en (3") et on
obtient :/
| ``2(3-n)S = 2(b+c) - 2(t+D) (5"')``
| Or (2) équivaut à ``(b+c) = S - u``
| On remplace alors, dans (5"'), ``(b+c)`` par ``S-u``, ce qui
donne \ ``2(3-n)S = 2(S-u) - 2(t+D)`` et, en simplifiant par 2, on
obtient :
| **(5"") : S = (D+t+u)/(n-2)** (car n >2). (on peut alors en
déduire tous les coefficients de p et de q)
| ``(2)+(4") : S = 2b + u +(v-w)`` donc ``b = (S - u - (v-w))/2 (2')``
| ``(2)-(4") : S = 2c + u - (v-w)`` donc ``c = (S - u - (w-v))/2 (4"')``
En remplaçant, dans (2') et (4"'), S par son expression dans (5""), les
expressions de b et c deviennent
````
| (2") b = 1/2 \* ((D + t + (3-n)u)/(n-2) - (v-w))
| **(4"") c = 1/2 \* ((D + t + (3-n)u)/(n-2) - (w-v))**
En remplaçant, dans ``(3")``, ``(b+c)`` par l'expression ``S-u`` (donnée
par (2)), et ``S`` par l'expression donnée en ``(5"")``, on obtient :
``(3"') d = 1/2 * ((D + (5-2n)t + (3-n)u) / (n-2) + (v+w))``
| Enfin, en remplaçant, dans (1'), d par l'expression ci-dessus et S par
l'expression donnée en (5""), on obtient :
| **(1") a = (D + t)/ (2(n - 2)) + (u - v - w) / 2**
On a donc, à partir de la donnée des coefficients de D,v et w, trouvé
tous les autres coefficients du carré, et ce de manière unique.
`(retour au sommaire) <#sommaire>`__
.. _SYNTHESE:
SYNTHESE
~~~~~~~~
Comme toutes les transformations faites sont réversibles (il est facile
de repartir des conclusions pour revenir au point de départ), le système
ci-dessous est équivalent au système de départ à 6 équations. Comme ces
conditions sont nécessaires et suffisantes, le carré défini par les
équations suivantes est bien l'unique carré magique correspondant aux
coefficients de D, v et w. CQFD.
+-----------+--------------------------------------------------------+
| ``(1")`` | ``a = (D + t)/ (2(n - 2)) + (u - v - w) / 2`` |
+-----------+--------------------------------------------------------+
| ``(2")`` | ``b = 1/2 * ((D + t + (3-n)u)/(n-2) - (v-w))`` |
+-----------+--------------------------------------------------------+
| ``(3"')`` | ``d = 1/2 * ((D + (5-2n)t + (3-n)u) / (n-2) + (v+w))`` |
+-----------+--------------------------------------------------------+
| ``(4"")`` | ``c = 1/2 * ((D + t + (3-n)u)/(n-2) - (w-v))`` |
+-----------+--------------------------------------------------------+
| ``(5"")`` | **``S = (D+t+u)/(n-2)``** |
+-----------+--------------------------------------------------------+
`(retour au sommaire) <#sommaire>`__
.. _CONCLUSION:
CONCLUSION
----------
Comme les coefficients de D, v et w sont au nombre de ``(n-1)²-1``, et
comme on vient de montrer qu'on peut les choisir comme on veut, la
dimension de l'espace vectoriel des carrés magiques d'ordre n est bien
``N = (n - 1)² - 1``. \ `(retour au sommaire) <#sommaire>`__
.. _Corollaires_exercices:
COROLLAIRES ET EXERCICES
------------------------
| NB : L'expression (5"") est intéressante car elle montre qu'il suffit
de fixer les ``(n-2)²`` coefficients du centre du carré pour que la
somme soit déterminée : elle est alors égale à la somme des termes du
carré intérieur D et des termes de ses deux diagonales, divisée par
son côté. Ceci permet au passage quelques exercices amusants.
| Par exemple, il est impossible d'obtenir un carré magique en
complétant le carré 5*5 ci-dessous avec des entiers :
+---+----+----+----+---+
| | | | | |
+---+----+----+----+---+
| | 5 | 8 | 17 | |
+---+----+----+----+---+
| | 13 | 12 | 3 | |
+---+----+----+----+---+
| | 11 | 7 | 21 | |
+---+----+----+----+---+
| | | | | |
+---+----+----+----+---+
| En effet, supposons que ce soit possible. Alors S est une somme
d'entiers donc c'est un entier.
| D'autre part ``D=5+8+17+13+12+3+11+7+21=97``, ``t =5+12+21=38``,
``u=11+12+17=40`` donc ``D+t+u = 175``. Or d'après ``(5'')`` :
``S = (D+t+u)/(n-2)``. Comme ``(n-2)=3`` et comme ``175`` n'est pas
multiple de ``3``, ``S`` ne peut pas être entière, ce qui contredit
l'intégrité de ``S``. CQFD.
| Variante de cet exercice : le carré ci-dessous ne peut pas être
complété en un carré magique contenant les entiers de 1 à 25.
+---+----+----+----+---+
| | | | | |
+---+----+----+----+---+
| | 15 | 8 | 17 | |
+---+----+----+----+---+
| | 11 | 25 | 22 | |
+---+----+----+----+---+
| | 12 | 14 | 1 | |
+---+----+----+----+---+
| | | | | |
+---+----+----+----+---+
En effet, si c'était possible, alors, comme on aurait
``S = (1+...+25)/5 = 65``. Or ici : ``D=115``, ``t=41``, ``u=54``,
``n=5`` donc d'après ``(5'') S=(115+41+54)/(5-2)=70``, ce qui contredit
``S=65`` CQFD.
`(retour au sommaire) <#sommaire>`__