Drapeau jaune : Cet article demande quelques connaissances mathématiques et un peu d’abstraction pour être entièrement compris

Avant de rentrer dans le vif du sujet, essayez de résoudre cette énigme. On considère l’expression suivante, qui comporte les nombres entiers de 0 à 10 :

0 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10

Est-il possible de remplacer les . de cette expression par des signes + ou – de sorte que l’opération qui s’affiche alors ait pour résultat 0 ?

Une méthode fonctionnelle serait tout simplement de tester toutes les possibilités.

• 0 + 1 + 2 – 3 + 4 – 5 + 6 – 7 + 8 – 9 + 10 = 7
• 0 + 1 – 2 – 3 + 4 – 5 – 6 + 7 – 8 – 9 + 10 = -5
• …

Dans le pire des cas, celui où il n’y aurait aucune solution, cela ne ferait que 1024 cas à étudier (10 trous, deux possibilités à chaque fois, donc 2¹⁰ possibilités). Et l’on se rendrait compte en effet qu’il n’existe aucune solution à ce problème. Mais alors, est-ce le cas si l’on va jusqu’au nombre 50 aussi ? Sachant que 2⁵⁰ est plus grand qu’un million de milliards, peut-être va-t-on réfléchir autrement.

Revenons au premier problème et séparons les nombres pairs des nombres impairs. D’un part, si on ajoute ou soustrait un nombre pair à un nombre pair, le résultat sera lui aussi un nombre pair (2 + 4 = 6, 8 – 4 = 4 …). Ainsi, quelque soit les opérations que l’on fait avec 0, 2, 4, 6, 8, et 10, nous aurons à la fin un nombre pair.

D’autre part, ajouter ou soustraire deux nombres impairs donne aussi un nombre pair (1 + 3 = 4, 7 – 5 = 2 …). Or, dans notre opération, nous avons cinq nombres impairs : 1, 3, 5, 7 et 9. Il en restera forcément un tout seul.

Or, si l’on ajoute ou soustrait un nombre pair à un nombre impair, l’opération donne un résultat impair. Ainsi, quelque soit les signes que l’on pourra donner dans notre expression, le résultat sera forcément impair, et ne peut donc pas valoir 0.

Du point de vue de la démonstration, nos deux méthodes sont toutes les deux aussi convaincantes l’une que l’autre. Néanmoins, vous admettrez surement que la deuxième méthode présente plus de cachet. N’avez-vous jamais ressenti de la frustration ou de l’émerveillement face à un problème qui vous semblait si compliqué que vous en avez écrit des lignes et des lignes et que, finalement, votre professeur a résolu en une ligne au tableau par un argument rusé ? L’élégance mathématique, c’est ça !

Et l’informatique dans tout ça ?

L’outil informatique est très performant pour exécuter de nombreux calculs en un temps ridicule. Par ailleurs, il a également pour lui l’avantage de ne pas se tromper dans son opération (ou c’est que vous l’avez mal programmé ; souvenez-vous de l’adage, un nombre incalculable de soucis informatiques trouvent leur origine entre la chaise et le clavier.)

Pour notre opération, nous avons de la chance : un raisonnement de quelques lignes nous a permis de trouver une solution immédiate et satisfaisante à notre problème, mais ce n’est pas toujours le cas. L’outil informatique peut alors entrer en scène et tester tous les cas de figures possibles, valider si tous ont passé le test ou infirmer si l’un d’eux y échoue.

La conjecture de Syracuse par exemple, que j’ai abordé dans un autre billet de ce blog, attend toujours une démonstration ou un contre-exemple. Si cette conjecture s’avère fausse, l’ordinateur pourra peut-être lui trouver un contre-exemple, a des valeurs surement inatteignables par le cerveau humain. Mais si cette conjecture se révèle vraie, l’ordinateur n’aura aucun moyen de le prouver, puisqu’il n’est évidemment pas capable de tester tous les nombres jusqu’à l’infini.

C’est d’ailleurs une limite des démonstrations faisant appel à l’informatique pour tester toutes les combinaisons possibles : si celles-ci sont infinies, inutile de vous dire que vous allez potentiellement attendre longtemps, très longtemps

Des théorèmes démontrés informatiquement

Mais il existe des problèmes qui ne possèdent qu’un nombre fini de possibilités, comme ce fut le cas pour notre énigme du début.

Prenons par exemple le cas du rubik’s cube : peu importe l’état initial de votre cube, quel est le nombre maximal de rotations d’un quart de tour à faire pour revenir au cube avec toutes les faces de la même couleur ? La réponse est 26. Autrement dit, si vous résolvez votre cube en plus de 26 coups, je suis navré de vous annoncer que vous avez été inefficace.

Lançons-nous donc dans la démonstration : il existe environ 43 milliards de milliards (43.10¹⁸) d’états initiaux possibles pour un rubik’s cube de taille 3×3. Autrement dit, si en l’état, nous donnions un rubik’s cube différent à chaque habitant de la planète, et qu’il était capable de le résoudre de la manière la plus rapide en une seconde, et que l’on continuait ainsi jusqu’à avoir balayé toutes les possibilités, il faudrait plus de 180 ans pour y arriver !

N’imaginez pas cependant que l’ordinateur est également tout puissant : un tel nombre de possibilités est complètement ahurissant, même pour le plus puissant d’entre eux. Il faut réduire ce nombre, et pour cela, utiliser des symétries.

Par exemple, si vous prenez votre cube et l’observez sur une face, puis sur une autre, puis une troisième, sans rien toucher à chaque fois. Techniquement, ce n’est pas tout à fait le même cube, puisque la face devant vous n’est plus la même, mais vous admettrez vite qu’il faut autant de coups au maximum pour résoudre l’un ou l’autre ! Voilà donc deux configurations effacées, et l’on procède ainsi pour réduire petit à petit le nombre.

Ainsi, Tomas Rosicky et Morley Davidson sont passés de 43.10¹⁸ à environ 2.10⁹ ensembles de 5.10⁷ positions différentes, à l’aide de symétries et de rotations, pour finalement les étudier et arriver à la conclusion suivante : il suffit de 26 quarts de tour pour résoudre un rubik’s cube.

Dans la liste des théorèmes utilisant l’informatique, nous pouvons aussi citer

• Le théorème des 4 couleurs – combien de couleur pour colorier une carte sans que deux régions voisines aient la même couleur ?
• Le sudoku – en dessous de combien d’indices peut-on affirmer qu’un sudoku ne possède pas une unique solution ?
• La conjecture de Kepler – quelle est la manière optimale d’empiler des sphères ?

Et ainsi de suite… Toutes ces démonstrations se basent sur les mêmes principes : d’abord, on cherche un système qui regroupe tous les cas possibles, puis on essaye de le réduire, et enfin, on attaque toutes les possibilités restantes de front.

Les limites de l’informatique

« Hé, tu savais que tu pouvais résoudre un rubik’s cube en 26 coups ?
– C’est cool ! Et alors ?
– Ben… rien, c’est tout… »

En mathématiques, on a souvent tendance à dire que le chemin est plus important que la destination, parce qu’il ouvre la voie à d’autres questions, posent de nouveaux problèmes.

L’informatique a ouvert la voie aux méthodes « brute force » qui consistent à foncer dans le tas en espérant que ça fonctionne, moyennant éventuellement un certain exercice de réflexion au préalable, en ce qui concerne la réduction des choix possibles. N’allez pas croire que c’est une chose triviale toutefois, il faut encore être capable de programmer efficacement la résolution d’un rubik’s cube tout de même.

Ces programmes laissent toutefois un goût amer en bouche, puisqu’ils se contentent de répondre « Oui » ou « Non » à la question « Bon alors, est-ce que ça marche ? », et cela ne satisfait pas forcément tout le monde. Certes, lorsque la réponse est « Non », on s’en contentera, mais dans le cas contraire, une démonstration belle, élégante, et qui soulève d’autres points mathématiques aura certainement un intérêt plus grand que le seul programme informatique, et les recherches continuent donc même sur ces théorèmes déjà démontrées.

Il ne faut pas non plus accorder une vision toute puissante à ce nouvel outil, puisqu’il n’est capable d’effectuer que ce que l’homme peut déjà faire lui-même. D’accord, il le fera dix milliards de fois plus rapidement que le plus brillant des mathématiciens de tout temps, mais avec (beaucoup) de persévérance, les résultats que renvoient la machine ne seraient pas différentes de ceux qu’obtiendrait l’humain.

On peut également craindre les bugs informatiques, les problèmes de programmation, les erreurs de la machine – même si la chaise, le clavier, tout ça… Sachez qu’il existe des logiciels spéciaux, comme le logiciel COQ, qui sont capables d’analyser une preuve informatique et de dire si la preuve donnée est correcte ou non. Attention, ils n’établissent pas la preuve eux-mêmes mais vérifient si la démonstration que l’on propose n’est pas entachée d’erreurs de raisonnements qui pourraient compromettre tout le travail des chercheurs.

Les démonstrations informatiques sont des démonstrations : on ne peut réfuter ce qu’elles disent. Il faut vivre avec son temps, mais pour autant, ne pas toujours s’en satisfaire. Peut-être existe-t-il des preuves plus plaisantes que nous découvrirons dans quelques années ?

Ils en parlent également

Sur l’élégance mathématique

• Mickaël Launay (MicMaths) à la Confer’ENS : L’élégance mathématique

Sur le rubik’s cube

• Image des maths : Nao résout le rubik’s cube
• God’s Number is 26 in the Quarter-Turn Metric

Sur les théorèmes démontrés par l’informatique

• Numberphile : 17 and Sudoku Clues
• Science Etonnante : Le théorème des quatre couleurs
• Eljj : Deux (deux ?) minutes pour le théorème des quatre couleurs
• Pour la Science : La conjecture de Képler