La rubrique Récréations informatiques propose une petite énigme algorithmique ou sur un thème de mathématiques discrètes susceptible d’intéresser un lecteur de 1024. La solution est donnée dans le numéro suivant.
Rappel du problème précédent — Les pentaminos amis
Les pentaminos sont les formes d’un seul tenant composées de cinq carrés collés par leurs côtés. Il existe 12 pentaminos dont la liste est donnée ci-dessous.
Deux pentaminos sont « amis » si, par définition, il existe une même forme F qu’ils pavent chacun de leur côté.
Le dessin (a) montre que le pentamino N est ami avec le X. Le dessin (b) montre que le I et le Z sont amis, et le dessin (c) montre que le L et le X le sont aussi. Cette notion a été introduite en 1996 par Rodolfo Kurchan dans son livre Puzzle fun où il traite quelques cas. Chacune de 66 paires possibles de pentaminos crée un problème ludique et parfois difficile. Un bon programme est sans doute nécessaire pour les résoudre.
À vous de les étudier en tentant de remplir le tableau ci-dessous. Dans chaque case du tableau il faut écrire une croix s’il n’y a pas d’amitié possible entre les deux pentaminos (et que vous arrivez à le démontrer), ou un entier donnant le plus petit nombre de pièces prouvant l’amitié. Personne aujourd’hui n’a pu remplir toutes les cases. C’est donc un problème ouvert.
Les dessins suivants justifient que l’on place quelques « 2 » dans le tableau.
Solution
Ce type de problèmes est aussi appelé « problèmes de compatibilité ». Il est la spécialité de Georges Sicherman qui les a étudié avec passion et qui s’est aussi intéressé à un grand nombre de variantes utilisant d’autres polyominos de base que les pentaminos, et même d’autres formes que les polyominos. Il propose un merveilleux site Internet1 où on trouve divers tableaux et une multitude de dessins résumant ses recherches et celles des amateurs s’intéressant à ce type de problèmes.
Le tableau demandé correspondant à l’état de l’art (en avril 2022) pour la partie concernant la compatibilité des paires de pentaminos est :
La justification des nombres écrits dans le tableau se trouve à cette URL2. Il est à noter que, pour ce puzzle, aucun lecteur ne m’a fourni une paire de pentaminos amis, justifiant ainsi l’un des nombres du tableau prédédent.
Nouveau problème — Matrices de somme positive
On se donne une matrice remplie d’entiers relatifs. Par exemple :
On a le droit de changer tous les signes des nombres d’une même ligne ou d’une même colonne. Par exemple :
(les coefficients des lignes ou colonnes modifiées sont surlignés.) Montrer que pour toute matrice initiale, en opérant de cette façon plusieurs fois, on peut obtenir une matrice dont la somme totale des nombres de chaque colonne et de chaque ligne sera positive ou nulle.