Discussion :

[Vampyre]

Bonjour à tous !

Une idée me passe par la tête... Vous connaissez certainement les carrés magiques... Et bien les carrés sataniques sont les carrés magiques, qui, une fois chaque nombre mit à son carré reste toujours magique...

On en trouve une belle définition sur wikipedia...

Par contre, ma question, elle, revient sur un problème d'algorithme... A votre avis, quelle serait la méthode à utiliser pour calculer ce genre de carrés ?

D'avance merci pour vos idées, car là, je sèche... Existerait-il une méthode permettant d'évaluer cela, sans trop bouffer en ressources ?

[Aitone]

Ca doit être bien difficile...

Carré satanique

[PRomu@ld]

Tout comme il y avait une méthode pour construire les carrés magiques (méthode des diagonales), il doit y en avoir une pour construire les carrés sataniques.

En partant de la formule donnée ici pour la densité:

http://www.recreomath.qc.ca/dict_bimagique_carre.htm

On devrait pouvoir construire un carré magique à partir de celà. Reste à vérifier si on a un carré magique.

Alors il existe peut-être une méthode plus astucieuse mais il faudrait y réfléchir plus longtemps (moi ça fait 5 mins )

[Nemerle]

tu utilises la méthode pour produire un carré magique avec des carrés de nombres entier, puis tu checkes sans les carrés...

[PRomu@ld]

Non, ça ne marche pas, il faut que les carrés soient des carrés consécutifs pour que ça marche or tu ne sais pas si les carrés consécutifs donneront un carré magique.

[Zavonen]

Ce qui a fait avancer la recherche sur les carrés magiques c'est la remarque selon laquelle ils forment un sous-espace vectoriel de l'espace des matrices lequel est de dimension n^2.
Dès qu'on a des carrés magiques linéairement indépendants on peut donc en obtenir de nouveaux par combinaison linéaire et tout le problème revient alors à trouver la dimension et une base de ce sous-espace.
On n'a rien de tel pour les carrés 'sataniques' d'ordre 2 par exemple, parce que, contrairement à ce que tous les collégiens croient:
(a+b)^2 n'est pas égal (la plupart du temps ) à a^2+b^2 ....
Cependant l'homogénéité se conserve.
Partez d'un carré 'satanique' multipliez tous les coefficients par 2, le carré reste magique et toutes les lignes et les colonnes du carré des carrés sont multipliés par 4.
Si on joint cette évidence au fait que a^p + b^p = (a+b)^p dans tous les corps Z/pZ avec p premier on peut utiliser des techniques d'algébre linéaire pour résoudre le problème dans les corps Z/pZ, de là à pouvoir 'remonter' dans Z ????

[PRomu@ld]

Si on joint cette évidence au fait que a^p + b^p = (a+b)^p dans tous les corps Z/pZ avec p premier

J'était en train de chercher un corps simple dans lequel on pouvait effectuer une résolution au problème, mais je ne connaissait pas cette proprièté (mon niveau en math s'arrête au DEUG ). Néanmoins la remontée dans Z est comme tu le dis pas évidente du tout .

[millie]

J'était en train de chercher un corps simple dans lequel on pouvait effectuer une résolution au problème, mais je ne connaissait pas cette proprièté (mon niveau en math s'arrête au DEUG ).

En fait, après coup, quand on voit le théorème, c'est très simple à démontrer. Il suffit d'utiliser la formule du binôme, et d'utiliser le fait que n est premier pour montrer que pour tout p=2 à n-1, n * (n-1)! / k!(n1-k)! est divisible par n (puisque n premier dans le coefficient binomial). Mais évidemment, c'était facile à voir quand Zavonen nous a gentillement donné le théorème

[Zavonen]

L'idée de 'relever' des solutions dans des corps simples, était séduisante, et nous sommes plusieurs à l'avoir eu.
Mais hélas elle est stérile.
Dans Z/2Z, tous les carrés magiques sont sataniques, on ne peut donc pas essayer de 'relever' par image réciproque de l'homomorphisme canonique de Z sur Z/2Z un sous ensemble restreint des carrés magiques de l'hypercube de dimension n^2.
Par contre la première remarque que j'ai fait sur la stabilité de la notion par multiplication par un scalaire permet de se restreindre aux ensembles de nombres premiers entre eux (globalement et non deux à deux). Je ne suis pas sûr qu'il s'agisse d'une simplification notable, mais cela permet au moins de ne pas trouver des solutions non 'fondamentalement différentes'.
Seule remarque pouvant peut être être exploitable:
Si aij est satanique alors si:
bij= (aij+aji)(aij-aji)
bij est magique de somme 0 avec une diagonale entièrement nulle.
Ce produit terme à terme de A+tA par A-tA ne correspond à mon avis directement à aucune opération algébrique classique, mais peut être à une expression algébrique en termes d'opérations usuelles compte tenu de la spécificité de A (à voir donc...)

[Zavonen]

Ce serait une bonne idée que d'offrir un nouveau carré 'satanique' à la RPC de Chine pour le nouvel an chinois. Ils en sont friands de ce genre d'amusement depuis la plus haute antiquité (traités I-king Lo-shu).
Pour ce qui concerne les carrés magiques simples on connaît à peu près tout:
La bonne structure pour les étudier est celle de Q-espace vectoriel (Z et encore moins N ne sont des corps). Comme les ensembles cherchés sont toujours des sous espaces de l'espace de dimension n^2 des matrices carrées d'ordre n à coeffs dans Q, on peut toujours se ramener à des coefficients entiers en multipliant par un entier assez 'fort' (par exemple le ppcm des dénominateurs de tous les coeffs). Par ailleurs les sous-espaces considérés contiennent toujours la 'droite' engendrée par la matrice dont tous les coefficients sont 1 et qui est évidemment magique, donc par ajout d'un assez grand nombre entier de cette matrice on peut éliminer les négatifs et dégager les solutions entières positives.
On s'aperçoit en fait que le sous espace cherché est somme directe de la droite décrite plus haut et du sous-espace des carrés magiques pour laquelle la somme des lignes des colonnes et des diagonales vaut 0. c'est ce sous-espace qui concentre toutes les difficultés.
Or ce sous-espace peut être défini comme une intersection d'hyperplans.
En effet les applications qui à toute matrice associent la somme des éléments d'une ligne, d'une colonne, d'une diagonale, sont des formes linéaires, car ce sont des sommes de formes coordonnées dans la base canonique.
Donc l'ensemble cherché se présente comme une intersection de noyaux de formes linéaires qui sont des hyperplans donc chacun de dimension n^2-1
Les hyperplans ne sont jamais parallèles c'est assez simple à voir car les n^2 formes linéaires coordonnées sont indépendantes dans le dual.
Il faut donc couper 2n+2 hyperplans et ajouter une droite.
la dimension du sous espace des carrés magiques est donc( n-1)^2-1
La démo se trouve, par exemple, dans:
http://bayledes.free.fr/carres_magiq...agiques_2.html
Cela fait pour construire TOUS les carrés magiques par exemple d'ordre 5. Il suffit d'en construire
14 indépendantes dont la somme est nulle, les autres s'en déduiront par combinaison linéaire de ceux là auquelles on ajoutera éventuellement une matrice :
p p p p p p
p p p p p p
………….
p p p p p p
Il existe des méthodes de constructions de ces solutions. On trouve tout cela sur le web. Les méthodes employées consistent généralement à distinguer le cas pair du cas impair et à utiliser pour compléter,des isométries du carré (rotations-symétries).
L'IDEE EST MAINTENANT LA SUIVANTE:
Les carrés sataniques ont des carrés magiques particuliers. Ils appartiennent donc au même sous espace. Par ailleurs, un carré satanique de somme S (nombre qui est lui-même une somme de carrés) peut être obtenu en partant d'un carré magique de somme 0 avec la matrice
où tous les éléments sont égaux à un même nombre.
Je suggère donc la méthode suivante
Soit V1,V2,…..Vk une base du sous-espace des matrices magiques de somme nulle
Soit V0 la matrice dont tous les coefficients sont égaux à 1.
Ici k est égal à (n-1)^2-2 dans le cas de l'ordre n
On complète cette base avec des vecteurs
Vk+1, …….,Vn^2-1
en une base de Q puissance n au carré. Les procédés de complétion ne manquent pas (Schmidt par exemple)
On désigne par W0, W1, ……,Wn^2-1 la base canonique de l'espace de toutes les matrices d'ordre n à coeffs dans Q.
n désigne par P la matrice de passage de V à W son inverse par P'.
Comment caractériser les carrés magiques qui sont en fait sataniques ?
On prend un carré magique décomposé sur la base W, on transforme ses coordonnées par P, on les élève au carré, puis on transforme les résultats par P'.
A noter qu'on peut s'arranger, par dilatation, pour que P ou P' soit à coefficients entiers, mais qu'on ne peut certainement pas avoir à la fois P et P' à coefficients entiers.
Les sataniques seront exactement ceux dont les composantes ainsi obtenues sont nulles sur
Vk+1, …….,Vn^2-1
Or quelle est la forme de ces composantes:
Ce sont forcément des polynômes homogènes de degré 2 à n^2 variable, car toutes les transfos sont linéaires à l'exception d'une élévation au carré:
On se retrouve donc avec un système de
n^2-(n-1)^2 +1 =2n équations homogène de degré 2 en n*n inconnues.
Plus n grandit et plus on gagne en degré de liberté le nombre d'équation devenant négligeable devant le nombre d'inconnues.
En définitive on peut considérer le système en une seule inconnue du second degré, les coefficients constants et les autres inconnues jouant le rôle de paramètres.
Il faut donc trouver toutes les façons de choisir n^2-1 paramètres entiers de façon à obtenir
2n discriminants formés à partir d'eux qui soient tous des carrés parfaits pour extraire à répétition des racines rationnelles.
Cela me paraît jouable, mais c'est pas gagné!
La solution passe peut être par la réduction des formes quadratiques à une somme de carrés, la loi d'inertie, etc…