Le plus petit carré magique additif-multiplicatif possible


Quel est le plus petit carré magique additif-multiplicatif (ou addition-multiplication) possible ? 5x5, 6x6, ou 7x7 : aujourd'hui personne ne sait !

Rappel : un carré magique additif-multiplicatif doit être magique quand on additionne les cellules de n'importe quel alignement (même somme S), et doit aussi être magique quand on multiplie les cellules de n'importe quel alignement (même produit P). Tous les entiers utilisés doivent être distincts. Le plus petit carré magique additif-multiplicatif est un carré 7x7 construit par Sébastien Miquel en 2016. Auparavant, les plus petits carrés connus étaient des carrés 8x8 et 9x9, construits pour la première fois par Walter Horner dans les années 50. En 2005, je construisais d'autres carrés 8x8 et 9x9 mais avec de plus petits produits magiques et de plus petites sommes magiques que les carrés de Horner.


Carrés magiques add-mult 3x3 ?

Les carrés semi-magiques et magiques sont impossibles. Voici la démonstration donnée par Lee Morgenstern.

Duplication Lemma
Given
     a + b = c + d
and
     ab = cd,
then
     c = a or c = b.

Proof
Use the 2nd equation and set d = ab/c. Substitute this into the 1st equation to get
     a + b = c + ab/c
or
     c(a + b) = c^2 + ab
or
     (c - a)(c - b) = 0.

 Thus c = a or c = b.

Theorem
A 3x3 add-mult semi-magic square of distinct entries is impossible.

Proof
Suppose the following is a 3x3 add-mult semi-magic square.
     a b M
     N P c
     Q R d

 Because the square is additive semi-magic, we have
         a + b + M = M + c + d
or
     (1) a + b = c + d.

 Because the square is multiplicative semi-magic, we have
         abM = Mcd
or
     (2) ab = cd.

From (1) and (2) and the Duplication Lemma, all 3x3 add-mult semi-magic squares must have duplicate entries.

Corollary
A 3x3 add-mult magic square of distinct entries is impossible.


Carrés magiques add-mult 4x4 ?

Les carrés semi-magiques add-mult 4x4 sont possibles. Lee Morgenstern a trouvé 54 exemples semi-magiques avec un Nb max < 256, les meilleurs possibles étant :

Mais les carrés magiques add-mult 4x4 sont impossibles, comme prouvé ci-dessous par Lee.

Theorem
A 4x4 add-mult magic square of distinct entries is impossible.

Proof
Suppose the following is a 4x4 add-mult magic square.
     a M N b
     P Q R S
     T U V W
     X c d Y

 Because the square is additive magic, we have
     (1)  a + M + N + b = X + c + d + Y,
     (2)  a + Q + V + Y = M + Q + U + c,
     (3)  b + R + U + X = N + R + V + d.

 Add (1), (2), and (3), cancel common terms, and divide by 2,
     (4)  a + b = c + d.

 Because the square is multiplicative magic, we have
     (5)  aMNb = XcdY
     (6)  aQVY = MQUc
     (7)  bRUX = NRVd

 Multiply (5), (6), and (7),
          MNQRUVXY(ab)^2 = MNQRUVXY(cd)^2
or
     (8)  ab = cd.

 From (4) and (8) and the Duplication Lemma, all 4x4 add-mult magic squares must have duplicate entries.


Carrés magiques add-mult 5x5 ?

On ne sait pas si les carrés magiques add-mult 5x5 sont possibles. Mais les carrés semi-magiques add-mult 5x5 sont possibles. Lee Morgenstern a trouvé 20 exemples semi-magiques avec un Nb max < 276. Voici le carré ayant le plus petit Nb max possible :

Cet autre carré a une très intéressante propriété supplémentaire : c'est aussi un carré additif panmagique, les sommes de toutes les diagonales brisées donnant encore le même S.

Voici le carré ayant le plus petit S :

Mais son tout meilleur carré est cet autre. Meilleur qu'un carré semi-magique add-mult, puisqu'il a en plus une diagonale magique additive-multiplicative (et toujours 5 lignes magiques add-mult, et 5 colonnes magiques add-mult). Très proche d'un carré magique add-mult 5x5 !

Résultats de la recherche faite par Lee Morgenstern en 2007 : il n'y a pas d'exemple magique avec un Nb max < 276.
Et résultats de ma propre recherche de février 2009 : il n'y a pas d'exemple magique avec un Nb max < 1000 et P < 10^9 * cellule centrale.

En avril 2010, Jérôme Crétaux, célèbre pour avoir craqué en 2005 la puce de la carte française d'assurance-maladie (la carte "Vitale", voir par exemple http://ec.europa.eu/idabc/servlets/Doc?id=22448 en anglais ou www.internetactu.net/2005/09/09/yaura-t-il-un-scandale-sesam-vitale en français), nominé pour les Big Brother Awards France 2005 (http://bigbrotherawards.eu.org/article550.html), a trouvé un carré semi-magique add-mult avec (Nb max, S, P) = (253, 674, 26854027200). Ce même carré avait été trouvé précédemment par Lee Morgenstern, parmi ses 20 exemples avec Nb max < 276, non complètement donnés ici. Est-ce que Jérôme craquera aussi l'énigme #6?

En janvier 2010, Javier Cilleruelo, Universidad Autonoma de Madrid, et Florian Luca, Universidad Nacional Autonoma de Mexico, ont publié un article intitulé "On multiplicative magic squares" dans The Electronics Journal of Combinatorics (www.combinatorics.org) dans lequels ils donnent une borne inférieure de la différence entre l'élément maximal et l'élément minimal dans un carré magique multiplicatif de dimension r composé d'entiers positifs distincts. Après leur preuve qu'un carré magique add-mult 4x4 ne peut pas exister, ils proposent : "Problem 2. Are there additive-multiplicative magic squares of order r = 5 with distinct entries?" C'est donc le même problème que le nôtre ici ! Voir leur intéressant article : www.combinatorics.org/Volume_17/PDF/v17i1n8.pdf

En décembre 2016, Keith F. Lynch, USA, a trouvé plus d'un millier de carrés semi-magiques add-mult 5x5 avec P < 2x10^12 (et quelques autres contraintes), mais aucun d'eux n'a deux diagonales magiques add-mult. Décevant, il n'a pas non plus trouvé de nouvel exemple ayant une diagonale magique add-mult. Avant ce travail de Lynch, le carré de Morgenstern donné plus haut avec P = 926640000 était considéré comme le carré ayant le plus petit produit magique possible. Mais parce que Lee avait seulement cherché des carrés avec Nb max < 276, il n'avait pas trouvé le carré ci-dessous de Keith. Voici le carré semi-magique ayant le plus petit P :

Parmi son millier de carrés semi-magiques, Keith a trouvé un seul carré utilisant 1, et un seul carré utilisant seulement des entiers impairs. Voici ces rares carrés :

En analysant les deux carrés semi-magiques add-mult (donnés plus haut, de Lee et Keith) qui sont aussi des carrés panmagiques additifs, j'observe que ce sont des carrés gréco-latins. On peut les obtenir avec :

Parmi le millier de carrés semi-magiques add-mult de Keith, j'ai réussi à bouger les cellules de 63 d'entre eux afin d'y ajouter la propriété panmagique additive. TOUS ces 63 carrés ont une structure gréco-latine additive. Mais aucun n'a de diagonale multiplicativement magique.

Puisque de tels carrés gréco-latins ont toujours dix (et pas seulement deux) diagonales additivement magiques, on a dix possibilités (et pas seulement deux) que quelques-unes de leurs diagonales soient aussi magiques multiplicativement. Bien sûr, pas facile que les lignes et colonnes soient aussi magiques multiplicativement... Mais c'est peut-être une méthode permettant un carré magique add-mult 5x5 avec de bons (A, B, C, D, E) et (a, b, c, d, e) ?

Qui sera le premier à construire un carré magique add-mult 5x5 ? Ou à prouver que c'est impossible ?


Carrés magiques add-mult 6x6 ?

En 2005, j'ai construit un carré magique multiplicatif 6x6 avec des propriétés add-mult partielles : ses 6 lignes sont additives-multiplicatives. En 2007, Lee Morgenstern a construit les premier carrés semi-magiques add-mult 6x6 connus. Voici ses meilleurs exemples semi-magiques. Le premier carré a en plus une diagonale magique additive. Et le second carré a une diagonale magique additive et une diagonale magic multiplicative.



Intéressante observation sur le précédent carré : il utilise les premiers entiers consécutifs 1, 2, 3, 4, 5, 6, 7. Pas complètement sûr que ce carré a le plus petit P possible, mais il a le plus petit P connu.

On ne sait pas si des carrés magiques add-mult 6x6 sont possibles. Le second carré ci-dessus (Plus petit S = 289) a 13 sommes correctes sur 14, et 13 produits corrects sur 14 : total 26 sur 28, pas carré magique additif, et pas carré magique multiplicatif. Voici un carré avec 14 sommes correctes sur 14, et 12 produits corrects sur 14 : toujours 26 sur 28, toujours pas carré magique multiplicatif, mais ce coup-ci carré magique additif !

Résultats de la recherche faite par Lee Morgenstern en 2007 : il n'y a pas d'exemple magique avec un Nb max < 136.

Qui sera le premier à construire un carré magique add-mult 6x6 ? Ou à prouver que c'est impossible ?


Carrés magiques add-mult 7x7 ?

En 2005, j'ai construit un carré magique multiplicatif 7x7 avec des propriétés add-mult partielles : ses 7 lignes sont additives-multiplicatives.

Résultats de la recherche faite par Lee Morgenstern en 2007 : il n'y a pas d'exemple semi-magique avec un Nb max < 91.

Qui sera le premier à construire un carré semi-magique add-mult 7x7 ?

En avril-mai 2010, Toshihiro Shirakawa a construit les premiers carrés semi-magiques add-mult 7x7 connus, ses deux meilleurs carrés étant :

Les diagonales sont magiques additives, mais pas magiques multiplicatives. Quelques mois plus tard, il a trouvé ce meilleur carré, cette fois une diagonale est add-mult magique, l'autre est mult magique (toutefois l'autre diagonale peut être add magique, en réarrangeant les cellules avec 108 + 78 + 39 + 20 + 54 + 63 + 18, mais alors elle n'est plus mult magique):

Qui sera le premier à construire un carré magique add-mult 7x7 ? Ou à prouver que c'est impossible ?

15 août 2016 : Sébastien Miquel, France, est le premier à résoudre mon énigme #6b. Il avait précédemment résolu l'énigme #4c aussi sur carrés 7x7. Sébastien est maintenant en doctorat à l'Université Paris-Sud, travaillant en mathématiques sur les groupes de Lie. Il a utilisé sa propre application écrite en Rust, tournant sur son ordinateur personnel basé sur un processeur i7-920. Il a choisi quelques produits magiques heuristiquements "bons" (ici 150885504000 = 2^10 * 3^7 * 5^3 * 7^2 * 11), avant de chercher des carrés avec sommes magiques sélectionnées. Pour ce produit, sa recherche d'un carré magique avec somme 465 a pris ~600h de calcul. D'autres solutions peuvent exister avec des plus petits produits et/ou des plus petites sommes.

Ce 7x7 est le PLUS PETIT carré magique add-mult connu : 5x5 et 6x6 encore inconnus! (énigmes #6, #6a)


Carrés magiques add-mult 8x8 et 9x9 ?

Des exemples sont connus. Voir cette autre page.


Retour à la page d'accueil http://www.multimagie.com