Pierre Hennequin [1]

J’ai souvent donné des recherches sur les carrés magiques et étoiles magiques. Suivant les niveaux de classe, en dehors du carré 3 × 3 que l’on peut faire créer par des élèves dès la sixième, il s’agissait le plus souvent de compléter des carrés ou étoiles partiellement remplis.

Le solveur d’Excel est un outil d’optimisation très puissant mais délicat à utiliser et a priori on ne saurait l’utiliser au collège. Pourtant, il m’a paru intéressant de mettre cet outil au service d’une activité de recherche de solutions multiples de carrés ou d’étoiles magiques. Ce thème intéresse les élèves. Il est simple à comprendre, assez aisé à programmer, nécessite une réflexion mathématique et … l’élève sait immédiatement si la réponse fournie par la machine convient ou non contrairement à la plupart des problèmes d’optimisation.

Mes objectifs

• Utiliser un outil d’optimisation.
• Analyser un problème et l’adapter à l’outil en n’utilisant que des fonctions de base.
• S’intéresser aux limites et au temps de calcul d’une machine.
• Réfléchir à la notion de condition nécessaire, condition suffisante.
• Avoir recours au calcul littéral pour confirmer une conjecture.

Quelques indications sur le fonctionnement du solveur

Remarque préalable pour les utilisateurs d’Open Office.
Il existe un solveur pour le tableur Calc de la suite Open Office mais il n’a pas pour l’instant les performances de celui d’Excel. La version 3 qui paraîtra bientôt devrait disposer d’un solveur performant.

En général, le solveur n’est pas installé par défaut. Pour le charger, dérouler le menu Outils – macros complémentaires et cocher solveur. Pour l’utiliser, dérouler de nouveau le menu outils et sélectionner solveur.

Pour « programmer » le solveur, renseigner les différents champs :

Cellule cible  : doit contenir une formule. La cellule peut être maximisée, minimisée ou atteindre une valeur précise qu’il faut alors saisir.

Cellules variables : le plus simple c’est de les sélectionner. On peut aussi saisir les adresses ou laisser faire le solveur.

Contraintes : pour écrire une contrainte cliquer d’abord sur ajouter. On peut écrire des inégalités larges, demander des nombres entiers (pour les cellules variables seulement). La contrainte « binaire » est à utiliser pour des cellules ne pouvant prendre que les valeurs vrai/faux.

Avec le bouton options, on peut agir sur un certain nombre de paramètres supplémentaires comme le temps de calcul, le nombre d’itérations, la précision, le pourcentage de tolérance (pour les entiers), le modèle supposé linéaire, supposé non négatif, l’échelle, l’algorithme de calcul, …

Une option importante et même indispensable pour construire un carré magique d’ordre 4 : échelle automatique.
Selon l’aide du logiciel, il faut activer cette option lorsque, je cite, « les valeurs des cellules variables et des cellules à contrainte ou cible diffèrent les unes des autres de plusieurs ordres de grandeur. »
Ne pas l’activer peut bloquer le solveur (CM4) ou rendre le calcul extrêmement long (étoile).
Sur mon PC doté d’un P4 1400MHz, la construction de l’étoile a pris plus de 25 min avec l’option échelle automatique désactivée contre 45 secondes en l’activant !
Curieusement les deux étoiles sont différentes.
À noter également qu’activer l’option « modèle supposé non négatif » peut accélérer le temps de réponse.

Déroulement de l’activité

Séance 1 : Classe entière, vidéoprojecteur, professeur aux commandes

Il s’agit de montrer comment on peut construire un carré magique 3 × 3 avec le solveur.Dans un premier temps, j’explique avec l’aide du tableur ce qu’est un carré magique.

Au départ la feuille de calcul est vierge. Les élèves ayant une certaine pratique du tableur, on construit rapidement le carré ci-contre.
Il est très facile de déplacer les nombres dans la grille et d’en voir l’effet sur les sommes.

Le but du problème est de placer les 9 nombres entiers dans la grille de telle façon que toutes les sommes, en ligne, colonne et diagonale soient égales.

Cette présentation dynamique permet aux élèves de bien saisir la situation.
Se pose alors le problème du calcul de la constante magique.
Certains répondent 15 parce que « c’est le résultat qui apparaît le plus souvent ».

Il suffira de modifier l’ordre des nombres dans la grille pour les convaincre de leur erreur.
J’interviens alors : quand on change l’ordre des nombres dans la grille, les différentes sommes sont modifiées mais qu’est ce qui ne change pas ?
La réponse finit par arriver : « le total ».

D’où le calcul ${{1+2+3+4+5+6+7+8+9}\over{3}}=15$
On peut alors programmer le solveur.

Réponse quasi immédiate. Remarquer la différence entre la case D4 et la barre de formule.

On remarque évidemment que la solution proposée ne convient pas. On recommence en partant d’une grille vide. On n’obtient que des 5.

Il faut trouver un moyen de différencier les neuf nombres. Je suggère d’utiliser leur produit. (Une justification sera donnée a posteriori.)

La grille de départ contient les entiers de 1 à 9, ce qui permet de connaître immédiatement la valeur cible à atteindre, la cellule G3 contenant la formule « = produit (B2 : D4) ».

Les options du solveur ne sont pas modifiées, à savoir 100s, 100 itérations, tolérance 5 …
Le solveur atteint les 100 itérations ; on continue et on obtient très vite une solution.

Suivant la grille de départ on obtient des solutions apparemment différentes. Quelques élèves considèrent néanmoins et à juste titre qu’il s’agit de la même solution.

Les élèves observent également que, dans tous les essais réalisés, le 5 occupe une place privilégiée : la case centrale du carré. Je propose d’ajouter comme contrainte : B2 = 5. On pourra aussi tenter C2 = 5.

À ce stade, les élèves semblent persuadés que dans un carré magique d’ordre 3 de constante magique 15, la case centrale vaut 5. Un calcul littéral permet de le démontrer.

Démonstration de cette conjecture

Retour sur l’effet de la contrainte factorielle 9

1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 = 362 880
Ce produit impose un 5 et un 7 uniques. Comme le 5 est au centre, il suffit de regarder les grilles possibles, de les compléter et d’éliminer les grilles présentant une contradiction. Il n’y a que deux configurations possibles : le 7 est dans un coin ou sur un bord. La seconde aboutit, pas la première. C’est assez rapide et le recours au calcul littéral n’est pas nécessaire. L’ordinateur est éteint. On travaille au tableau, les élèves venant à tour de rôle compléter les différentes grilles en s’arrêtant à la première anomalie.

Premier cas

À la place du point d’interrogation on peut mettre 1, 2, 3, 4, 6, 8, 9
Pas le 5, pourquoi ?
Pas le 7, pourquoi ?

Deuxième cas :

Les élèves conviennent sans difficulté que les deux solutions obtenues n’en font qu’une. Il n’existe donc qu’un seul carré magique d’ordre 3, même si en apparence on peut en compter 8.

Séances 2 et 3 : Salle multimédia, élèves en binôme.

Objectifs : reconstruire un carré magique d’ordre 3, et voir si ce modèle de construction peut être étendu au carré d’ordre 4 et à l’étoile.

Tous les groupes réussiront le CM3 ; plusieurs le CM4 ; un groupe commencera l’étoile. Il faut préciser que le temps effectif de travail sur ordinateur est environ 45 min (s’installer, allumer les machines, se connecter, charger le logiciel, et inversement en fin de séance, tout cela prend du temps). Une autre séance sera donc nécessaire mais certains ne réussiront pas l’étoile, d’autres resteront bloqués sur un CM4 erroné. En effet, le modèle du CM3 ne se généralise pas, l’ensemble des conditions peut se révéler insuffisant. Cela dépend des grilles de départ mais aussi des options choisies.

Construction du carré magique 4 × 4

Première difficulté : interpréter le contenu de la cellule H2. Cela dépend des
connaissances des élèves. Il suffira de changer le format et de faire afficher
20 922 789 888 000. C’est aussi l’occasion de parler de l’écriture scientifique d’un nombre. À noter que les calculatrices
de collège ne fournissent pas le résultat exact. Les machines ont bien des limites.
Afin de faire prendre conscience aux élèves du gigantisme de ce nombre, je leur dis qu’en comptant de 1 en 1, à raison d’un nombre par seconde, 24h/24, il leur faudrait plus de 600 000 ans pour l’atteindre !
Le calcul de la constante magique n’a posé aucun problème.

Selon les grilles de départ, les options du solveur et même les ordinateurs, le temps de réponse peut être plus ou moins long et les réponses très différentes.

Quelques résultats justes obtenus par les élèves

Solutions avec doublons refusées bien que satisfaisant aux contraintes.

Carrés multi-magiques obtenus en ajoutant quelques contraintes (la somme de quatre cellules adjacentes égale 34).

Étoile magique

Le problème

Réorganiser l’étoile afin que la somme des quatre nombres de chacune des six lignes soit toujours la même.

Il s’agit d’un problème analogue aux précédents.
Cette fois l’étoile est fournie. Il faut programmer le solveur comme on l’a fait pour le carré 4×4.
Penser à activer les options « Modèle supposé non négatif » et « Echelle automatique ».
La cible c’est factorielle 12.
Les contraintes doivent être saisies une par une alors que pour un carré magique, on peut le faire
par plages. C’est donc un peu plus long.
La seule difficulté réside dans le calcul de la constante magique.

Voici une excellente méthode proposée par un élève de Quatrième. Je la résume en une phrase :
Calculer la moyenne des douze nombres et multiplier par 4 .
On remarquera que cette méthode vaut aussi pour les CM.

Ci-dessous deux solutions (il y en a bien d’autres)
Les solutions diffèrent suivant la grille de départ (qui ne doit pas être vide sinon le solveur bloque).

La deuxième est une étoile multi magique obtenue avec la contrainte supplémentaire :

B8+E2+H8=26
B4+H4+E10=26

Il y a aussi des solutions erronées, ce qui montre que là encore les conditions imposées ne sont pas suffisantes.

Propriétés d’une étoile magique

Pour prolonger cette activité on étudie en classe quelques propriétés d’une étoile magique, propriétés que l’on peut préalablement découvrir sur les exemples construits par le solveur. C’est l’occasion d’un calcul littéral.

J’ai représenté au tableau quatre étoiles obtenues par le solveur dont une multi magique (voir l’exemple 2) et j’ai demandé aux élèves de chercher ce qu’elles présentaient de commun en dehors bien sûr de la constante magique. Je dois dire qu’ils ont trouvé assez rapidement ce que j’espérais à savoir la propriété des triangles et la propriété des losanges. Il restait à le démontrer.

Remarque : Ces propriétés ne sont pas nécessaires au solveur pour fournir des étoiles.
Toutefois celle des triangles permet de construire l’étoile multi magique.

Complément : À propos du carré magique 5 × 5

Je n’ai pas abordé le sujet avec les élèves. La méthode précédente ne peut pas s’appliquer ici, le calcul de factorielle 25 dépassant les capacités d’Excel. L’idée m’est cependant venue de « calquer » le carré d’ordre 3.

En opérant une translation de (−5), on obtient un carré magique présentant une symétrie
autour de la case centrale.
Pour le CM5 j’applique une translation de (−13).
La cible c’est la valeur absolue du produit des douze cases bleues. La valeur à atteindre est 12 !
Comme contrainte supplémentaire, j’ai ajouté la somme de leur valeur absolue.

Sur cette copie d’écran les contraintes de symétrie n’apparaissent pas. Il y a douze sommes comme : « =B1 + F5 »
Chaque somme est contrainte à valoir 0. Le carré de droite se déduit du carré de gauche par translation de (+13).
La grille gauche est vide au départ. Le solveur trouve une solution en quelques minutes, après une relance.
À noter que là encore le résultat dépend des valeurs de départ. On peut obtenir différentes solutions.

Pour terminer j’ai voulu aller plus loin en construisant un carré magique d’ordre 5 souvent qualifié de diabolique.
À partir du premier carré, je coupe la première colonne que je reporte à droite.
J’obtiens ainsi un nouveau carré toujours magique. On peut procéder de la même façon pour les lignes. En partant d’un carré de ce type je peux en construire 24 autres.
En voici dix.

Pour créer le premier carré avec le solveur, il a fallu ajouter quelques contraintes décrivant les translations de lignes et de colonnes. Seules les diagonales sont modifiées.

<redacteur|auteur=500>