Géométriser

Piste bleue 8 novembre 2014  - Ecrit par  Patrick Popescu-Pampu Voir les commentaires (1)

J’illustre par un exemple élémentaire le fait que « géométriser » un problème consiste à le ramener à une question portant sur un « espace ».

Cet article est un pendant de mon article « Algébriser ». Dans celui-là, j’y expliquais par un exemple élémentaire une manière générale d’aborder les problèmes mathématiques : leur « algébrisation ». Ici je désire illustrer par un autre exemple élémentaire une deuxième manière générale d’aborder ces problèmes : leur « géométrisation ».

De nombreux livres de récréations mathématiques contiennent des problèmes de passage de rivière : un certain nombre de personnages doivent traverser à l’aide d’une barque, en respectant certaines contraintes. Ce type de problèmes a un âge vénérable, puisque les plus anciens exemples connus datent du temps de Charlemagne. En effet, on trouve les trois problèmes suivants dans « Propositiones ad acuendos juvenes » [1], écrit par
Alcuin :

Proposition 17. De trois hommes et de leurs sœurs

Trois hommes, ayant chacun une sœur, doivent traverser une rivière, tout en évitant qu’un homme soit en présence d’une femme autre que sa sœur [2]. Ils n’ont qu’une chaloupe qui ne peut transporter que deux personnes.

Qui peut dire comment ils peuvent traverser la rivière pour qu’une femme ne soit jamais laissée en compagnie d’un autre homme si son frère n’est pas présent ?

Proposition 18. D’un homme, d’une chèvre et d’un loup

Un homme devait traverser une rivière avec un loup, une chèvre et un panier de choux. Il y avait là un bateau, mais si petit que seul pouvait passer avec lui le loup, la chèvre ou le panier de choux. Il ne voulait pas laisser la chèvre avec le loup ou avec les choux.

Dis-moi, qui le peut, comment l’homme s’y prendra pour transporter sans problèmes le loup, la chèvre et les choux.

Proposition 19. D’un mari et de son épouse

Un homme et son épouse pesaient chacun autant qu’une charrette chargée. Leurs deux enfants pesaient ensemble autant que la charrette vide. Les quatre devaient traverser une rivière. Ils trouvèrent un bateau qui pouvait porter au plus le poids d’une charrette.

Comment purent-ils traverser la rivière sans faire naufrage ?

De ces trois problèmes, le plus connu est probablement le deuxième, et le plus compliqué le premier. Mais avec un peu de patience on arrive à le résoudre sans aucun bagage mathématique, par essais successifs, afin de se frayer un chemin à travers les diverses pistes qui s’ouvrent à chaque étape.

Dans la phrase antérieure, se frayer un chemin semble une expression métaphorique, utilisée pour désigner la démarche d’essais et d’erreurs menant à une solution. Je voudrais présenter ici une autre méthode, qui passe par la traduction du problème en celui de se frayer un chemin allant d’un point à un autre dans un certain espace.

J’ai lu cette méthode dans le très agréable livre « Aventuras matemáticas » [3] de Miguel de Guzmán.

Guzman l’illustre d’abord sur le deuxième problème de la liste précédente, puis sur une variante plus simple du premier, dans laquelle il n’y a que deux couples de frères et sœurs. C’est ce cas que je reprends ici.

Le graphe des possibles

Le point de départ de la méthode est de construire un espace sous-jacent au problème, que j’appellerai le graphe des possibles.

En général, un graphe est un diagramme formé de sommets et d’arêtes qui les relient. Dans notre cas, chaque sommet correspond à une configuration possible des personnages, c’est-à-dire une configuration qui respecte les contraintes du problème. Deux sommets sont reliés par une arête si on peut passer d’une configuration à l’autre en une seule traversée qui respecte les contraintes données.

Par exemple, la configuration initiale est celle où les quatre personnes ainsi que la barque (qui est un personnage du problème !) se trouvent sur la rive de départ. Une
autre configuration possible est celle où les dames se trouvent sur l’autre rive avec la barque, et les messieurs sur la rive de départ. On peut passer
de la configuration de départ à cette dernière en une seule traversée, donc il y a une arête qui relie les sommets associés.

Notons par $D_1, D_2$ les deux dames et par $M_1, M_2$ les messieurs ($M_i$ étant bien sûr le frère de $D_i$). Notons aussi par $B$ la barque. Guzmán représente chaque configuration par un cercle partagé en deux à l’aide d’un diamètre, les deux moitiés représentant les deux rives et chaque moitié contenant les noms des personnages se trouvant sur cette rive. Ainsi, les deux configurations du paragraphe précédent sont représentées par :

Avec un peu de travail, on peut dessiner alors le graphe de notre problème.
Pour cela, il est commode de disposer les disques de manière circulaire,
puis de tracer tous les segments qui partent d’une configuration donnée
vers celles qui lui sont associées en une traversée. On fait cela pour chaque
configuration. La disposition initiale des disques est arbitraire, mais il est bon de trouver une manière systématique de le faire, pour être sûrs que l’on n’a oublié
aucune configuration.

Voici le diagramme obtenu par Guzmán :

Comprenez-vous de quelle manière il a disposé les disques et comment cela assure qu’aucune configuration n’a été oubliée ? Vous les avez peut-être disposés autrement, mais cela n’est pas grave, car si vous avez tracé les arêtes correctement, le graphe obtenu est le même, ce que les mathématiciens formulent en disant qu’il lui est isomorphe. Plus précisément, le graphe des possibles doit être pensé en tant qu’objet abstrait, vivant en lui-même, non pas dans un quelconque espace ambiant plus familier. Le dessin dans le plan n’en est qu’une ombre. Sur cette ombre on voit des croisements entre arêtes qui ne sont pas présentes dans le graphe des possibles abstraits, et desquels nous n’avons pas à tenir compte dans la résolution de notre problème.

Il est maintenant facile de trouver visuellement un chemin qui mène de la configuration où tous les personnages se trouvent sur une rive à celle où ils se trouvent tous sur l’autre rive. Par exemple :

Retour sur le sens de la « géométrisation »

La solution précédente procède par « géométrisation » du problème. Mais que signifie cela en général ? Dans le Trésor de la langue française, on trouve les définitions suivantes :

Définition  : Géométriser : rendre géométrique.

Ah, il faut chercher aussi « géométrique » :

Définition  : Géométrique : A. Qui relève de la géométrie. B. Qui est caractérisé par des formes relevant de la géométrie.

Bon, il faut encore chercher le sens de « géométrie » :

Définition  : Géométrie : Partie des mathématiques ayant pour objet l’étude de l’espace et des figures qui peuvent l’occuper.

Je suis d’accord. Mais qu’est-ce que l’« espace » ? Eh bien, c’est une notion qui a évolué incroyablement pendant les deux derniers siècles. Si autour de 1800 on pouvait souvent dire qu’il s’agissait de l’espace de la géométrie d’Euclide, de nos jours il y a pléthore d’objets que les mathématiciens ont été amenés à appeler de ce nom.

Qu’est-ce qui fait que l’on décide à un moment donné qu’un objet de notre pensée peut bien être appelé « espace » ?

Une réponse possible est :

Principe  : On peut dire qu’un objet est un « espace » si on reconnaît des analogies suffisamment importantes entre cet objet et l’espace euclidien.

Par exemple, si on y détecte des figures spéciales, analogues des points, des droites, des plans ou des sphères dans l’espace euclidien. Ou bien si l’on peut s’y déplacer de proche en proche.

Ces deux critères sont vérifiés par les graphes : ils ont des « points » (leurs sommets) et des « droites » (leurs arêtes). On peut s’y déplacer de proche en proche, en circulant le long des arêtes. C’est suffisant pour décréter qu’un graphe est un « espace » !

D’une certaine manière les graphes sont les espaces les plus simples qui soient : même s’ils sont constitués de segments, qui sont de dimension un, on peut penser qu’ils n’ont qu’un ensemble fini de points, car les arêtes matérialisent juste les transitions permises d’un point à un autre [4]. Pourtant, comme pour le plan euclidien, et comme pour tout espace, les contempler fait surgir les questions les unes après les autres.

Voici quelques unes auxquelles on peut répondre en jouant avec le graphe précédent :

  • Quel est le nombre minimum de traversées nécessaires pour que tout le monde passe d’une rive à l’autre ? En d’autres termes, quelle est la distance entre les deux sommets correspondants ?
  • De combien de manières peut-on faire une telle traversée minimale ?
  • Quel est le diamètre du graphe, c’est-à-dire la plus grande distance entre deux sommets ?
  • Peut-on trouver une représentation dans le plan de ce graphe dans laquelle n’apparaissent pas de croisements supplémentaires ?
  • (Pour lecteurs plus savants) Quel est le groupe de symétrie du graphe ?

La notion de distance introduite dans la première question met en évidence une autre analogie des graphes avec l’espace de la géométrie euclidienne : dans les deux cas on peut définir la longueur des chemins allant d’un point à un autre. En ce qui concerne les graphes, il est possible de le faire en attribuant à chaque arête une longueur, puis en additionnant les longueurs des arêtes parcourues par le chemin.

Dans le graphe des possibles précédent, on attribue à chaque arête la longueur $1$.
Cette convention revient à supposer que chaque fois la rivière est traversée en des intervalles de temps de même durée. Mais on peut aussi varier le problème en prenant en compte le fait que ces durées dépendent de la personne qui rame. Dans ce dernier cas, il faut considérer un autre graphe, dans lequel il y a parfois deux arêtes entre deux sommets, chacune correspondant à un autre rameur. De plus, à chaque arête est associée une longueur qui représente la durée de la traversée faite avec le rameur associé. Par exemple, si cette personne ne sait pas ramer, on attribue à l’arête correspondante une longueur infinie ... ce qui revient à éliminer tout bonnement l’arête du graphe.

Mais revenons au cas le plus simple, où on ne tient pas compte de ces subtilités
liées à la diversité des rameurs. Si on dessine les graphes correspondant aux trois problèmes de passage de rivière posés par Alcuin, on comprend visuellement pourquoi on pouvait avoir le sentiment que le premier problème est le plus difficile : il s’agit du graphe ayant le plus grand nombre d’arêtes.

Les difficultés des problèmes peuvent donc être comparées grâce à leur géométrisation, en comparant divers caractères des espaces associés.

Retour aux problèmes d’Alcuin

Les trois problèmes de traversée de rivières posés par Alcuin peuvent être rendus à souhait plus compliqués, en augmentant le nombre de personnages présents ou les règles de compatibilité entre eux, et en introduisant éventuellement quelques îles sur lesquelles certains personnages peuvent être déposés temporairement. On pourra trouver de tels exemples dans le chapitre « Le jeu des traversées en bateau » du premier volume de « Récréations mathématiques » de Lucas [5]. Chacun de ces problèmes peut se géométriser de la même manière que dans l’exemple de Guzmán, en le traduisant en la recherche d’un chemin reliant deux sommets donnés dans un graphe. Mais les graphes associés deviennent rapidement très compliqués, et il est alors impossible de se débrouiller en dessinant.

Il devient nécessaire de programmer un ordinateur pour chercher un tel chemin à notre place. Cela nécessite d’algébriser à son tour le problème géométrique, afin de le rendre calculable par une machine. [6]

J’arrive ainsi à un aspect essentiel de mon propos : les processus
d’algébrisation et de géométrisation ne suffisent pas en général tout seuls
à résoudre un problème. Il faut les combiner judicieusement, en faisant
plusieurs algébrisations et géométrisations successives du problème de départ, ou bien de ses sous-problèmes. Cela est valable même si on s’occupe de problèmes étiquetés différemment, par exemple de “théorie des nombres”, de “probabilités” ou d’“équations aux dérivées partielles”. Les géométriser revient à y percevoir des espaces sous-jacents, les algébriser revient à y percevoir les aspects calculables.

Ce qui est curieux est que la plupart des mathématiciens préfèrent nettement l’une des deux méthodes : soit ils ont un goût prononcé pour les structures algébriques et les algorithmes mais ne « voient » pas géométriquement, soit ils ne se sentent heureux que lorsqu’ils savent penser un problème et sa solution à l’aide d’un certain type d’espace. Devinez de quel côté se situait Hermann Weyl, qui écrivit :

« En ce temps l’ange de la topologie [7] et le diable de
l’algèbre abstraite luttent pour l’âme de chaque discipline mathématique. » [8]

Heureusement que les goûts sont variés ! Ce n’est qu’ainsi, après avoir subi
de multiples algébrisations et géométrisations fines, permettant chacune de décomposer un problème donné en sous-problèmes, ou de le relier à d’autres problèmes qui semblaient totalement différents au départ, que les problèmes les
plus profonds se retrouvent finalement résolus par les efforts combinés de générations de mathématiciens plutôt inclinés à l’algébrisation, ou bien à la géométrisation. Ces efforts laissent derrière eux de vastes perspectives de nouveaux espaces, de nouvelles structures algébriques ou de nouveaux algorithmes, qui engendrent de nouvelles questions, qui demanderont à être géométrisées, puis algébrisées, puis ...

Mais peut-être que ces deux méthodes générales de transformation des problèmes ne suffisent pas, et qu’il faut parfois les arithmétiser ou les probabiliser ? Sûrement, et peut-être qu’un volontaire nous expliquera autour d’un café en quoi cela consiste ...

Post-scriptum :

Merci beaucoup à Simon Billouet, Maxime Bourrigan, Damien Gayet, Lison Jacoboni, Marcus Mildner, François Sauvageot, Massy Soedirman, Claire Wenandy et Flandre pour leurs remarques et suggestions !

Article édité par Patrick Popescu-Pampu

Notes

[1Ce qui peut se traduire par « Propositions pour aiguiser la perspicacité des jeunes ». J’ai repris cette traduction, ainsi que celle des trois problèmes présentés ici, à Charles-E. Jean,
telle qu’il l’a publiée sur le site
Récréomath.

[2La suite de l’énigme montre que la contrainte « en évitant qu’un homme soit en présence d’une femme autre que sa sœur » concerne uniquement les personnes se trouvant dans la chaloupe. En effet, sur un rivage un homme peut être en présence d’une femme qui n’est pas sa sœur, pourvu que le frère de celle-ci soit aussi présent. Mais comme dans la chaloupe ne peuvent entrer que deux personnes, la contrainte principale du problème « qu’une femme ne soit jamais laissée en compagnie d’un autre homme si son frère n’est pas présent » a en fait comme conséquence cette première contrainte énoncée dans l’énigme.

[3Il s’agit d’un ouvrage de récréations mathématiques du niveau du lycée, publié par les éditions Pirámide de Madrid. Une traduction française, sous le titre « Aventures mathématiques », est parue en 1990 aux Presses Polytechniques et Universitaires romandes de Lausanne. La méthode dont je parle ici y est expliquée au chapitre 1.

[4On pourra voir aussi à ce sujet l’exemple des chaînes de Markov.

[5J’ai déjà parlé ici d’un problème tiré de cet ouvrage.

[6Une telle méthode d’algébrisation est expliquée
dans l’article Alcuin’s transportation problems and integer programming
de Borndörfer, Grötschel et Löbel, paru dans le volume 2 de « Charlemagne and his heritage. 1200 years of civilization and science in Europe » (Aachen, 1995), Brepols, Turnhout, 1998, 379–409.

[7La topologie est la branche de la géométrie qui étudie les « espaces topologiques ». On pourra consulter à ce sujet plusieurs articles sur IDM : ici, , là-bas ou encore .

[8« In these days the angel of topology and the devil of abstract algebra fight for the soul of every individual discipline of mathematics. » Cette phrase se trouve à la page 500 de l’article « Invariants », paru dans Duke Mathematical Journal No. 5 (1939), 489—502.

Partager cet article

Pour citer cet article :

Patrick Popescu-Pampu — «Géométriser» — Images des Mathématiques, CNRS, 2014

Crédits image :

Image à la une - Le logo est une photo de la peinture « Les coteaux de Belbeuf » (1909) de Robert Antoine Pinchon, provenant de Wikimedia

Commentaire sur l'article

  • Géométriser

    le 8 novembre 2014 à 11:28, par Nils Berglund

    Mais peut-être que ces deux méthodes générales de transformation des problèmes ne suffisent pas, et qu’il faut parfois les arithmétiser ou les probabiliser ?

    Je suis d’accord ! Pour quelques jolis exemples d’applications de la « méthode probabiliste » dans des domaines inattendus (théorie des nombres, géométrie, théorie des graphes), voir par exemple le chapitre 12 de ces notes de cours d’Yvan Velenik.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM