[ version PDF à télécharger : ]

Le jeu est la forme la plus élevée de la recherche. [Albert Einstein]

On peut en savoir plus sur quelqu’un en une heure de jeu qu’en une année de conversation. [Inconnu] ¹

 

Albinus Alcuin (né dans le Yorkshire vers 730, et mort à Tours en 804) fut un des hommes les plus savants de son temps. L’un des principaux amis et conseillers de Charlemagne, il fut engagé à titre de précepteur pour réformer les programmes d’enseignement, en réorganisant également la structure scolaire et en rédigeant des manuels dans chaque discipline.

Alcuin fut nommé par Charlemagne abbé de Saint-Martin de Tours en 796 où il rétablit l’observance régulière. Sous son égide, cette abbaye deviendra l’un des grands foyers de la renaissance carolingienne.

Théologien et pédagogue, il établira en 800 une version de la Bible qui s’imposera comme modèle.

Parmi ses ouvrages, on retrouve un recueil écrit en latin Propositiones ad acuendos juvenes qu’on pourrait traduire par Propositions pour aiguiser la perspicacité des jeunes.

Ce recueil contient 53 problèmes récréatifs et figure comme l’un des exemples les plus anciens de récréations mathématiques.
* Selon des historiens, certains de ces problèmes sont dus à des mathématiciens qui ont vécu avant Alcuin.
Par la suite, plusieurs auteurs dont Bachet de Méziriac s’inspireront de certaines de ces propositions.

En voici quelques propositions.

 

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, comment l’homme s’y prendra pour transporter sans problèmes le loup, la chèvre et les choux ?

Il n’est pas très difficile de trouver une solution à ce problème, mais comment savoir facilement combien de solutions a ce problème ? A-t-on trouvé la plus courte ?

Voyons plusieurs façons de répondre à ces questions.

Cette situation peut être modélisée à l’aide d’un graphe.

Désignons par P le passeur, par C la chèvre, par X le chou et par L le loup.

Les sommets du graphe sont des couples précisant qui est sur chaque rive (initiale / destination).

Le couple (PCX ; L) signifie que le passeur est sur la rive initiale avec la chèvre et le chou (qui sont donc sous surveillance), alors que le loup est sur l’autre rive.

Les sommets dont l’une des composantes est CX ou LC sont des situations interdites.

On dit que le graphe ainsi obtenu est un graphe biparti : les sommets pour lesquels le passeur est sur la rive initiale ne sont reliés qu’aux sommets pour lesquels le passeur est sur l’autre rive.

Il suffit alors de trouver un chemin (le plus court de préférence) entre la situation initiale (PCXL ; -) et la situation finale souhaitée (- ; PCXL).

Sur le graphe ci-dessous, on observe bien qu’il n’y a que deux plus courts chemins qui répondent au problème (l’un d’entre eux est en vert).

Ce que l’on peut alors synthétiser sous la forme d’un tableau :

 

On peut aussi transformer cette énigme en problème géométrique en traçant un schéma dans l’espace « loup-chèvre-chou » :

0 = sur la rive initiale      1 = sur l’autre rive

Par exemple, (1,1,0) signifie que le chou est sur la rive initiale, alors que la chèvre et le loup sont sur l’autre rive.

Passer de (0,1,0) à (1,1,0) signifie que le passeur a transporté le loup vers l’autre rive (sur laquelle il y a la chèvre), en laissant le chou sur la rive initiale. Etc.

On ne peut pas passer de (0,0,0) à (0,0,1) car cela signifierait que le passeur transporte le chou vers l’autre rive, et donc que la chèvre et le loup sont seuls…

Il est alors facile de constater qu’un des chemins le plus court est :

(0,0,0) \(\to\) (0,1,0) \(\to\) (1,1,0) \(\to\) (1,0,0) \(\to\) (1,0,1) \(\to\) (1,1,1)

et qu’il y n’a qu’un seul autre chemin solution.

 

L’avantage de cette méthode est que les solutions sautent aux yeux ! Par contre, cela ne permet pas de visualiser facilement les trajets (le passeur est-il seul ? transporte-t-il quelque chose ? etc.).

 

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.

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 ?

Ici, construire une solution géométrique (comme pour la proposition 18) nécessiterait de dessiner un hyper-cube à 6 dimensions dans un espace « frère 1 – frère 2 – frère 3 – sœur 1 – sœur 2 – sœur 3 ».

Par contre, la théorie des graphes peut nous être utile.

Nous n’allons pas faire comme à la proposition 18, car notre graphe comporterait alors 60 sommets !

Une façon efficace de voir le problème est de considérer les trajets possibles en fonction du nombre de femmes et du nombre d’hommes sur la rive initiale (sans distinction de « couples » frère/sœur).

L’objectif est alors de trouver un trajet reliant le point (3 ;3) au point (0 ;0) en alternant les allers et les retours…

On constate alors que l’on doit passer par le point (3 ;2) et qu’il y a deux variantes pour cela (en rouge). Puis l’on doit nécessairement suivre le trajet bleu pour atteindre le point (0 ;1). Il y a alors à nouveau deux variantes pour rejoindre (0 ;1).

Il y a donc 4 variantes possibles, sans compter les permutations des « couples », et il faut au minimum 11 étapes pour résoudre le problème.

Une possibilité, en notant en minuscules (a ;b ;c) les femmes et en majuscules (A ;B ;C) les hommes :

 

 

Terminons par une énigme célèbre, inspirée d’une de celles d’Alcuin :

à partir d’un bidon de 5 L et d’un bidon de 7 L, peut-on obtenir 4 L ?

(on peut remplir un bidon à volonté)

L’axe des abscisses représente la contenance du bidon de 5 L, tandis que l’axe des ordonnées représente celle du bidon de 7 L.

L’objectif est de partir de (0 ;0) pour atteindre un couple qui contient 4 :

(4 ;0) ou (4 ;7) ou (0 ;4) ou (5 ;4).

 Le chemin le plus court nécessite alors 6 étapes :

(0 ;7) Remplir le bidon de 7 L

(5 ;2) Verser dans celui de 5 L

(0 ;2) Vider le bidon de 5 L

(2 ;0) Verser l’eau (2 L) du bidon de 7 L dans celui de 5 L

(2 ;7) Remplir le bidon de 7 L

(5 ;4) Remplir le bidon de 5 L avec les 3 L (sur 7 L) du bidon de 7 L...

 En choisissant de remplir le bidon de 5 L en premier, il faudra 14 étapes pour atteindre 4 L…

 

A vous de jouer : à partir d’un bidon de 7 L et d’un bidon de 11 L, obtenir 2 L le plus rapidement possible.