Des problèmes connus des Carolingiens pour la plupart d’entre eux, se prêtent remarquablement bien à une analyse algorithmique, par les graphes ou en Python. Le niveau visé est NSI en Terminale.
France Gall le chantait, c’est de l’époque de Charlemagne que date l’école. Mais si l’idée de fonder l’école peut être attribuée à l’empereur, celui qui a animé cette école est Alcuin. Pour lancer l’enseignement des mathématiques, il aurait rédigé le manuscrit propositiones ad acuendos juvenes, un ensemble de propositions (de problèmes) pour aiguiser l’esprit des écoliers. On y trouve beaucoup de problèmes de passage de rivière faisant allusion à la nécessité, fréquente au moyen-âge, d’utiliser un bac (bateau) pour traverser une rivière.
En fait, en appelant « état » une configuration d’un de ces problèmes (par exemple la liste des personnages présents sur la rive droite), on est ramené à l’étude d’un automate fini, et ces problèmes sont très étudiés en informatique, et très utilisés dans l’enseignement de celle-ci.
Aucune licorne, aucune chèvre, aucun chameau, aucun chou ni aucune pomme n’ont été maltraités durant l’élaboration de cet article, aux contributeurs multiples, nombreux et variés.
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International.
Calculer et autres compétences
Le parcours d’un graphe, si ce graphe représente un automate, est la suite des états (ou des changements d’état) de l’automate, et il est d’usage d’utiliser le mot calcul pour désigner ce parcours. Selon la théorie des automates finis, les problèmes de traversée de rivière reviennent à chercher un calcul. Pour autant, ce n’est pas la compétence calculer qui est évaluée ici.
En fait l’intérêt essentiel de ces problèmes est que la compétence calculer est pratiquement la seule qui ne soit pas mobilisée pour les résoudre ! Il reste
- La compétence raisonner, mobilisée pour trouver « de tête » une solution (et espérer qu’elle soit optimale).
- La compétence communiquer, utilisée pour verbaliser la solution qu’on croit avoir trouvée.
- La compétence représenter, mobilisée par ceux qui veulent utiliser un graphe pour résoudre le problème.
- Et surtout la compétence modéliser, surtout utilisée par ceux qui réussissent à programmer en Python le parcours du graphe : des questions comme « qu’est-ce que c’est qu’un état dans ce problème ? » viennent très rapidement à l’esprit du programmeur Python !
Le fait de ne pas mobiliser la compétence calculer libère en quelque sorte les autres compétences, de celle-ci, et permet de mieux les repérer. Par ailleurs, ce genre de problème peut intéresser plus les élèves ayant choisi NSI sans maths, certains d’entre eux ayant tendance à être déçus lorsqu’ils voient le niveau de maths requis en informatique...
Sous contraintes
Voici un problème bien plus moderne (XXe siècle) :
Il est intéressant parce que l’algorithme glouton ne s’y applique pas. Cet algorithme inciterait à faire passer d’abord les deux personnages les plus lents, ce qui prendrait du temps pour le retour de l’un d’eux avec la torche. Cependant le problème revêt un caractère nettement plus numérique que ceux décrits ci-dessous alors on ne va pas le traiter ici.
Régiment
Édouard Lucas, proche du milieu militaire, a généralisé ce problème (numéro 19) d’Alcuin :
XIX. PROPOSITIO DE VIRO ET MVLIERE PONDERANTIBVS [PLAVSTRI PONDVS ONVSTI].
De uiro et muliere, quorum uterque pondus habebat plaustri onusti, duos habentes infantes inter utrosque plaustrali pondere pensantes fluuium transire debuerunt. Nauem inuenerunt, quae non poterat ferre plus, nisi unum pondus plaustri. Transfretari faciat, qui se putat posse, ne nauis mergatur.
Dans ce problème, il s’agit de faire traverser la rivière à toute une famille, le bac ne permettant pas à plus d’un adulte (ou deux enfants) de traverser. On considère que chacun des deux enfants (des jumeaux comme on peut le voir ci-dessous) pèse exactement la moitié de l’un des parents (lesquels ont donc tous les deux la même masse corporelle).
~~ rive gauche ~~ | ~~ rive droite ~~ | |||||
---|---|---|---|---|---|---|
👨👩👦👦 |
|
Loup, chèvre et chou
C’est le célébrissime problème 18 d’Alcuin :
XVIII. PROPOSITIO DE HOMINE ET CAPRA ET LVPO.
Homo quidam debebat ultra fluuium transferre lupum, capram, et fasciculum cauli. Et non potuit aliam nauem inuenire, nisi quae duos tantum ex ipsis ferre ualebat. Praeceptum itaque ei fuerat, ut omnia haec ultra illaesa omnino transferret. Dicat, qui potest, quomodo eis illaesis transire potuit ?
Pour homogénéiser les dessins ci-dessous, le chou (cauli) a été remplacé par une pomme, qui présente de plus l’avantage de ne pas avoir la même initiale que la chèvre.
~~ rive gauche ~~ | ~~ rive droite ~~ | |||||
---|---|---|---|---|---|---|
🐺🐐🍏🚣 |
|
L'état actuel du jeu est (0,0,0,0).
Le graphe, étiqueté par les personnages qui traversent, est celui des états d’un automate fini. On peut effectuer des parcours de ce graphe en Python.
Voici, au format pdf, une version plus détaillée, avec affichage des valeurs des variables à chacun des états :
Maris jaloux
C’est le problème 17 d’Alcuin :
XVII. PROPOSITIO DE TRIBVS FRATRIBVS SINGVLAS HABENTIBVS SORORES.
Tres fratres erant, qui singulas sorores habebant, et fluuium transire debebant. (Erat enim unicuique illorum concupiscientia in sorore proximi sui) qui uenientes ad fluuium non inuenerunt, nisi paruam nauiculam, in qua non potuerunt amplius nisi duo ex illis transire. Dicat, qui potest, qualiter fluuium transierunt, ne una quidem earum ex ipsis maculata sit ?
En 1612, Claude-Gaspard Bachet de Méziriac a traduit en français ce problème, dans ses problèmes plaisans et délectables :
Trois maris jaloux se trouvent de nuit avec leurs femmes au passage d’une rivière où ils ne rencontrent qu’un petit bateau sans batelier, si étroit qu’il n’est capable que de deux personnes, on demande comment ces six personnes passeront deux à deux, tellement que jamais aucune femme ne demeure en compagnie d’un ou de deux hommes si son mari n’est pas là.
C’est la version de Bachet qui est citée par Édouard Lucas qui devine une analogie entre ce problème, et le jeu du baguenaudier à 3 anneaux :
Dans ce texte, Édouard Lucas évoque une intéressante généralisation [2] : que se passe-t-il s’il y a plus de 3 couples à faire traverser ? Et si le bateau permettait de transporter plus de 2 personnes à la fois ? Lucas propose ce problème d’allure plus numérique que les précédents :
Des maris en nombre quelconque n se trouvent avec leurs femmes au passage d’une rivière ; quel doit être le plus petit nombre x de personnes qu’un bateau peut au plus contenir, pour effectuer la traversée, avec un batelier, avec la condition qu’aucune femme ne demeure dans le bateau ou sur l’une des rives en compagnie d’un ou plusieurs hommes, si son mari n’est présent.
Cette généralisation en a inspiré d’autres durant le XXe siècle. On va en voir une dans l’onglet suivant.
Cannibales et missionnaires
Ce problème, qui n’est pas d’Alcuin, peut être considéré comme une simplification du précédent, ou plutôt une généralisation : si, à un moment, il y a plus de femmes que d’hommes sur une rive, l’une des femmes serait en compagnie d’autres hommes que son mari et la solution proposée par Bachet au problème ci-dessus est donc a fortiori aussi solution du problème suivant (où on met des dragons à la place des femmes et des licornes à la place des hommes, l’allégorie des cannibales et des missionnaires étant inutilement violente de nos jours). Trois 🐉 et trois 🦄 doivent traverser la rivière avec un bac ne permettant au maximum que le passage de deux d’entre eux à la fois, avec la contrainte que sur aucune rive, à aucun moment, les licornes soient moins nombreuses que les dragons ce qui les mettrait en danger :
~~ rive gauche ~~ | ~~ rive droite ~~ | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
L'état actuel du jeu est (3,3,1).
Jeep
Les jeeps n’existant pas à l’époque d’Alcuin, c’est un chameau qui, ignorant que des siècles après lui, des véhicules allaient le remplacer en consommant le pétrole qui est sous ses pieds, transporte des graines en dévorant au passage une partie de sa cargaison :
LII. PROPOSITIO DE HOMINE PATERFAMILIAS.
Quidam paterfamilias iussit XC modia frumenti de una domo sua ad alteram deportari ; quae distabat leucas XXX : ea uero ratione, ut uno camelo totum illud frumentum deportaretur in tribus subuectionibus, et in unaquaque subuectione XXX modia portarentur : camelus quoque in unaquaque leuca comedat modium unum. Dicat, qui uelit, quot modii residui fuissent ?
Le chameau ne traverse donc pas une rivière, mais un désert. Cela change beaucoup de choses : il est possible de déposer une partie des 90 sacs de couscous au milieu du désert pour revenir les récupérer après.
📦📦📦🐪______________________________
Une première idée est de faire transporter par le chameau les 90 sacs de couscous d’un coup, avec un aller simple. Il en mange 30 (il consomme un sac de couscous par lieue parcourue) et on arrive 30 lieues plus loin avec 60 sacs de couscous, de quoi nourrir pas mal de monde (sauf le chameau, vu qu’il s’est déjà bien gavé pendant la traversée du désert).
Mais Alcuin signale que la capacité de transport du chameau est limitée à 30 sacs. On ne peut donc appliquer la solution précédente. Si on lui fait porter 30 sacs (sa capacité maximale) à 30 lieues, il ne reste plus de couscous à l’arrivée. En plus pas de carburant pour aller chercher les deux chargements de 30 sacs restés au départ...
📦📦______________________________🐪
Si on lui fait transporter moins de 30 sacs, il n’arrive pas à destination, faute de carburant pour lui. La constitution de dépots au milieu du désert est donc nécessaire.
On peut alors chercher à constituer un dépot à mi-chemin : on part avec 30 sacs de couscous faire un aller-retour à mi-chemin, soit à 15 lieues,
📦📦______________📦🐪_______________
mais ce faisant on arrive à cette étape avec seulement 15 sacs restants et on en a besoin pour le trajet retour. L’idée était mauvaise après tout.
📦📦🐪______________________________
Le problème a-t-il seulement une solution ? Si on constitue un dépot à 10 lieues, on peut y amener d’abord 10 sacs (en en consommant 20 pour l’aller-retour)
📦📦🐪_________📦____________________
puis encore 10 (avec consommation de 20 sacs supplémentaires)
📦🐪_________📦____________________
et enfin 20 puisqu’on n’a besoin que d’un aller simple cette fois-ci. On est alors ramené au problème de transporter 40 sacs de couscous à 20 lieues (qui restent à parcourir).
_________📦📦🐪____________________
En laissant 10 sacs sur place on peut partir avec 30 sacs et arriver avec 10 sacs.
_________📦____________________📦🐪
Le problème a donc bel et bien une solution. Mais elle n’est pas optimale puisqu’on a laissé 10 sacs abandonnés dans le désert.
L’histoire n’est pas finie : dans ce jeu de Don Knuth, les cartes ne traversent pas une rivière mais une FIFO, le but étant qu’une fois arrivées sur la « rive droite » elles soient rangées dans l’ordre croissant. Ce jeu fait l’objet d’un chapitre entier du livre promenade d’Étienne Ghys et mène à une classification intéressante des permutations sur n éléments.