Défis mathématiques dans Le journal Le Monde

Depuis quelques semaines, le journal Le Monde met les mathématiques à l'honneur! D'abord en publiant une série de livres de vulgarisation ( je viens de lire le premier consacré au nombre d'or que j'ai trouvé bien écrit) mais aussi en proposant sur son site web des défis mathématiques auxquels les lecteurs peuvent proposer leur solution. Chaque défi est présenté par une petite vidéo de quelques minutes, les deux premiers sont même présentées par Cédric Villani lui-même :

• combien y a-t-il de palindromes à 351 chiffres?
• peut-on trancher un cube et obtenir comme figure de coupe un pentagone?
• Quelle est la valeur maximale de remplissage d'un tableau à 3 lignes et 3 colonnes où l'on commence par placer deux "1" et où on remplit les cases autres avec la somme des valeurs des cases voisines (déjà remplies) ?

Ce dernier problème m'a particulièrement amusé et voici ma solution en image :-)

Quelques explications s'imposent : pour essayer de résoudre le défi il faut le décomposer en deux questions :

• d'abord trouver comment placer les deux "1" de départ
• ensuite choisir un ordre de remplissage optimal des cases restantes

1 Position des "1" au départ 
pour le premier point, en utilisant les symétriques du carré (par rapport à la 2ième ligne, ou la 2ième colonne ou l'une des diagonales) on peut facilement se rendre compte qu'il existe un nombre très limité de choix possibles. En plus de la configuration donnée en exemple, équivalente à la matrice de départ suivante :
$$C_0={\begin{pmatrix}1&0&0\cr 1&0&0\cr 0&0&0\cr \end{pmatrix}}$$
  il n'y a que 6 autres configurations possibles:

$$C_1={\begin{pmatrix}1&0&0\cr 0&0&0\cr 1&0&0\cr \end{pmatrix}}
~C_2={\begin{pmatrix}1&0&0\cr 0&1&0\cr 0&0&0\cr \end{pmatrix}}
~C_3={\begin{pmatrix}1&0&0\cr 0&0&0\cr 0&1&0\cr \end{pmatrix}}$$
$$~C_4={\begin{pmatrix}1&0&0\cr 0&0&0\cr 0&0&1\cr \end{pmatrix}}
~C_5={\begin{pmatrix}0&1&0\cr 1&0&0\cr 0&0&0\cr \end{pmatrix}}
~C_6={\begin{pmatrix}0&0&0\cr 1&1&0\cr 0&0&0\cr \end{pmatrix}}$$

parmi elles  la meilleure configuration est celle où le remplissage des autres cases se fait en ajoutant des nombres les plus gros possibles donc en limitant les fois où le "1" interviennent dans la somme. Il faut donc que

• les deux "1" touchent le moins de cases possibles, 
• limiter les cas où les deux  "1" interviennent  dans la même somme.

La meilleur manière de répondre à ces deux contraintes est donc de placer les "1"  dans les coins  comme dans la deuxième configuration $C_1$!


2 Choix de l'ordre de remplissage 
Une fois les deux 1 placés il reste alors 7!=5040 manières de remplir la grille (et encore certaines sont équivalentes en utilisant des symétries dans le placement des "1"). On peut  alors par essais successifs  trouver des ordres de remplissage de plus en plus efficaces ... j'ai pu ainsi trouver la solution suivante :
$${\begin{pmatrix}1&7&11\cr 2&4&22\cr 1&55&26\cr \end{pmatrix}}~~~~~~
\textrm{ordre de remplissage :}
{\begin{pmatrix}1&5&6\cr 3&4&7\cr 2&9&8\cr \end{pmatrix}}~~(1)$$
 Hélas cette solution n'est pas optimale :-( Mais le nombre de combinaisons étant limité il est alors tentant de toutes les calculer à l'aide d'un petit programme pour trouver la meilleure :-) Pour écrire un tel programme  je vais représenter une solution par un simple vecteur à 9 cases représentant l'ordre de remplissage des cases pour une certaine numérotation des cases. Pour la "solution" de l'équation (1)  sera représentée par :
 $$ordre=[1,3,2,5,4,7,8,9,6] ~~\textrm{numérotation des cases : }N={\begin{pmatrix}1&4&7\cr 2&5&8\cr 3&6&9\cr \end{pmatrix}}$$
Avec Scilab il est facile d'écrire une petite fonction effectuant le remplissage de la grille suivant cet ordre :

function A=essai_grille(ordre)
    //initialisations
    n=9,u=3,
    A=zeros(u,u)    // la grille 3x3
    N=A;N(:)=[1:n]; //pour numéros de cases 
    //deux premières cases = place des "1"
    k1=ordre(1),k2=ordre(2)
    A(k1)=1;A(k2)=1;
    ordre([1,2])=[]
    for k=ordre  // remplissage de la kième case
        [i,j]=find(N==k);// position (i,j) de la case k
        A(i,j)=sum(A(max(1,i-1):min(u,i+1),max(1,j-1):min(u,j+1)))
    end
endfunction

Ensuite, bien qu'il soit possible d'écrire un programme explorant toutes les possibilités, j'ai préféré utiliser  un algorithme génétique !  L'intérêt est que l'heuristique génétique évite d'avoir à comprendre la manière d'organiser les calculs, le hasard se charge lui même d'expérimenter et de corriger les essais jusqu'à obtenir une solution optimale. C'est d'autant plus justifié ici que la formulation du problème est très proche de celle du PVC que j'ai présenté sur ce blog dans un billet précédent.   En reprenant les fonctions proposées pour le PVC il faudra juste modifier :

•  la fonction qui génère la population de départ function P=Populat(n,m)   les vecteurs d' ordre générés vont avoir leurs deux premières composantes fixées (ordre=[1, 3, ....] pour la configuration $C_1$)  au lieu d'une seule dans le cas du PVC. On peut la coder facilement en utilisant la fonction grand(2*m,'prm',vect) de scilab avec l'option 'prm' pour générer 2m permutations d'un vecteur de initial vect
• le calcul de la valeur à optimiser par function D=CalculAdapt(P) est ici la valeur maximale de remplissage de la grille  cela s'écrit donc simplement :
  

  function D=CalculAdapt(P)
      ordre=P'// pour avoir un vecetru ligne
      A=essai_grille(ordre)
      D=max(A)
  endfunction

  
  
•  il faut aussi modifier la fonction de sélection  function E=SelectElit(P)  pour choisir les solutions de D maximum et pas minimum  comme dans le cas du PVC
• il peut y avoir des petits ajustement à faire dans function M=Mutation(I)  et  function [P1,P2]=Croisement(I1,I2)  pour que l'algorithme ne modifie pas les deux premières valeurs des matrices ordre (qui doivent rester 1 et 3 pour la configuration $C_1$)
• la fonction  principale ne dépend plus alors que de la taille de la population m, le taux de mutation t et le nombre d'étapes N,son entête  pourra être simplifié en :
  

  function S=Genetiq(m, t,N)
     n=9// n=nombre de cases 

   

Reste à faire tourner l'algorithme génétique avec suffisamment de données ... par exemple Genetiq(100,0.02,3) suffit pour trouver la solution optimale (c'est beaucoup moins de qu'une simulation exhaustive des  7!=5040 possibilités de remplissage) et c'est comme cela que j'ai trouvé la solution avec la valeur de remplissage de 57 donnée au début de ce billet. On pourra remarquer qu'il existe plusieurs solutions arrivant au total de 57 :
$$ordre=[1,3,2,6,5,9,8,4,7]\Rightarrow {\begin{pmatrix}1&30&57\cr 2&7&20\cr 1&3&10\cr \end{pmatrix}}$$

Pour aller plus loin, avec le même programme,  on peut aussi analyser les valeurs de remplissage pour chaque configuration de base :

• pour $C_0$ valeur de remplissage 44 $ {\begin{pmatrix}1&2&2\cr 1&6&24\cr 7&14&44\cr \end{pmatrix}}$
• pour $C_2$ valeur de remplissage 33 ${\begin{pmatrix}1&18&33\cr 2&1&14\cr 3&6&7\cr \end{pmatrix}}$
• pour $C_3$ valeur de remplissage 49 ${\begin{pmatrix}1&49&23\cr 2&7&16\cr 3&1&8\cr \end{pmatrix}}$
• pour $C_4$ valeur de remplissage 40 ${\begin{pmatrix}1&11&40\cr 2&8&21\cr 3&1&1\cr \end{pmatrix}}$
• pour $C_5$ valeur de remplissage 36 ${\begin{pmatrix}1&11&40\cr 2&8&21\cr 3&1&1\cr \end{pmatrix}}$
• pour $C_6$ valeur de remplissage  25 ${\begin{pmatrix}2&4&5\cr 1&1&10\cr 2&14&25\cr \end{pmatrix}}$

Ces résultats confirment bien que la configuration $C_1$ est meilleure que les autres.

3. Et avec une grille 4x4 ?

Je me suis alors amusé à regarder ce qui se passerait si on cherchait les valeurs de remplissage maximales pour une grille de taille 4x4. Il faut faire quelques modifications dans les fonctions Populat et essai_grille pour qu'elles s'adapte automatique à une grille carrée à u lignes et u colonnes de telle sorte que le nombre de cases est $n=u^2$  et considérer la numérotation des cases colonne par colonne :

 $${\begin{pmatrix}1&5&9&13\cr 2&6&10&14\cr 3&7&11&15\cr 4&8&12&16\cr \end{pmatrix}}$ $
 Dans ce cas le nombre méthodes de remplissage possibles explose et l'algorithme génétique trouve ses limites :

• Il faut tester avec une population bien plus grande et beaucoup plus d'étapes  que dans le cas d'une grille 3x3, typiquement j'ai fait mes essais avec m=2000 et N=20 ce qui prend déjà plus de 20 secondes de calculs.
• Pour des "1" placés dans deux coins d'un même coté il semble que le résultat optimal soit 1881, par exemple avec ordre=[1,4,5,2,6,3,7,8,12,11,16,15,10,14,13,9]  :
  $${\begin{pmatrix}1&1&1881&938\cr 2&4&319&619\cr 7&14&76&224\cr 1&22&36&112\cr \end{pmatrix}}$$
  Ce résultat est retrouvé quasiment à chaque essai de l'algorithme génétique pour cette configuration de départ. Par contre si les "1" sont dans des coins opposés on arrive pas à de telles valeurs ...
• Pour des "1" adjacents le résultat dépasse les 2000 , par exemple avec ordre=[1,2,5,6,9,10,13,14,15,16,11,12,8,7,3,4] :  $${\begin{pmatrix}1&2&6&18\cr 1&4&12&36\cr 1198&801&148&48\cr 2391&392&244 &48\cr \end{pmatrix}}$$

si vous trouvez mieux que 2391 n'hésitez pas à m'en faire part ...