Transvasements - Solution

2 récipients

On peut obtenir la solution par tâtonnement, mais donnons une méthode systématique.

graphe1résolution graphique

L'état du système est décrit en fonction des contenus actuels de chaque récipient dans un repère (x,y).
Les seuls états déterminés sont ceux sur le périmètre du rectangle, et les seuls déplacements possibles sont :

Revenir à un état d'où on est parti est inutile et on voit qu'il y a deux possibilités et deux seulement à partir du point (0,0), les deux récipients vides :

C'est toujours le même récipient que l'on remplit à la fontaine et toujours le même que l'on vide quand il est plein, et on transfère chaque fois. On répète ces opérations jusqu'à obtenir la quantité souhaitée. On choisit alors celle des deux solutions qui est la plus économique.

Résolution algébrique

Appelons alors X le nombre de fois où on a "algébriquement" rempli le récipient de 11 litres. C'est à dire X > 0 si on a effectivement rempli et X < 0 si on l'a en fait vidé. De même pour Y et le récipient de 9 litres. La quantité totale de liquide dans les deux récipients est 11X + 9Y. Obtenir la quantité q, c'est résoudre l'équation :

 11X + 9Y = q 

Avec notre exemple numérique, 11X + 9Y = 5 soit X = -2 + 9k, Y = 3 - 11k et les deux solutions :
X = -2, Y = 3 et X = 7, Y = -8.
La plus économique est bien sûr de vider 2 fois le récipient de 11 litres et remplir 3 fois celui de 9, c'est à dire :
Remplir le récipient de 9 litres, transvaser
Remplir le récipient de 9 litres, transvaser, reste 7 litre
Vider le récipient de 11 litres, transvaser
Remplir le récipient de 9 litres, transvaser, reste 5
(vider le récipient de 11 litres. Cette dernière étape est inutile pour l'énoncé, on les a, nos 5 litres !)

De façon générale, avec deux récipients a et b, on peut obtenir la quantité q en résolvant :

 aX + bY = q 

Cette équation de Diophante a toujours des solutions si le PGCD de a et b divise q, et est insoluble sinon.
Conclusion, on peut obtenir toutes les quantités q multiples du PGCD de a et b.
Par exemple avec des récipients de 12 et 30 litres on peut obtenir toutes les quantités multiples de 6 litres, mais il est impossible d'obtenir 10 litres par exemple.

Le nombre d'opérations est |X| + |Y| remplissages/vidages et |X| + |Y| - 1 transvasements soit

 N = 2|X| + 2|Y| - 1 

Si q < a,b le dernier vidage est inutile car on a q dans l'autre récipient.

Application

Obtenir deux fois plus dans un récipient que dans l'autre. Comme au moins un récipient est plein ou vide, on ne peut obtenir que (8,4) c'est à dire 4.
Il faut résoudre 8X + 11Y = 4 soit X = 6 - 11k, Y = -4 + 8k.
X = 6 Y = -4 N = 19
X = -5 Y = 4 N = 17
et donc la solution optimale est X = -5, Y = 4, on vide le récipient de 8 litres et on remplit celui de 11.
(0,0) (0,11) (8,3) (0,3) (3,0) (3,11) (8,6) (0,6) (6,0) (6,11) (8,9) (0,9) (8,1) (0,1) (1,0) (1,11) (8,4)
Bien sûr la 17ème opération (0,4) n'est pas effectuée !

3 récipients

Avec plus de deux récipients, le principe est le même mais dans un espace à n dimensions.
Ceci conduit à l'équation aX + bY + cZ + ... = q.
Dans l'énoncé proposé, 19X + 13Y + 7Z = 20 a une solution évidente X = 0, Y = 1, Z = 1, qui ne jette rien.

Vient alors une deuxième partie du problème, la répartition de ces 20 litres en deux fois 10, sans utiliser la fontaine ni jeter d'eau. Ceci se fait en considérant un des récipients comme réservoir, on y puise pour remplir et ou y jette pour vider, les deux autres récipients servant à obtenir 10 litres. Il y a trois stratégies à examiner :

  1. Le récipent de 19 litres sert de réservoir, vide au départ, et les deux autres font tout le travail.
  2. Le récipient de 13 litres sert de réservoir, plein au départ.
  3. Le récipent de 7 litres sert de réservoir, plein au départ.
En fait ces trois stratégies sont équivalentes : chaque opération peut être décrite selon l'un ou l'autre point de vue.
Par exemple transvaser le contenu du récipient de 13 litres dans celui de 7 peut être vu comme un transvasement sans toucher au "réservoir" de 19 litres, ou bien comme le remplissage du récipient de 7 litres à partir du "réservoir" de 13 litres, ou bien comme le vidage du récipient de 13 litres dans le "réservoir" de 7 litres,
Il suffit donc d'étudier un seul cas, par exemple en considérant le récipient de 13 litres comme réservoir.

La quantité totale de liquide dans les deux récipients servant aux transvasements ne peut pas devenir inférieure à 7 litres sans faire déborder le réservoir, elle ne peut pas dépasser 20 litres puisqu'on n'a que cette quantité disponible. Ceci interdit l'accès aux zones grisées et les seuls points définis sont sur le pourtour du polygone limité par les droites x + y = 7 et x + y = 20.
Le contenu z du réservoir peut être indiqué par une échelle à 45° repérant les droites x + y = q - z = 20 - z.

graphe2 On part du point (0,7), réservoir plein.
Il faut atteindre le point (10,0).
Suivons le chemin en rouge.
On transvase le récipient de 7 dans celui de 19 (7,0), on remplit celui de 7 (7,7), on transvase dans celui de 19 (14,0), on remplit celui de 7 mais là le réservoir est vide et il n'y a que 6 litres (14,6).
Transvaser dans le récipient de 19 nous amènerait au point (19,1) dont nous discuterons plus tard. Il faut vider le récipient de 19 dans celui de 13, reste 1 litre et le point (1,6), on complète le récipient de 7 (1,7), etc... pour aboutir finalement au point (10,0) solution.

Partons dans l'autre sens (trajet en vert). On démarre de (0,7) puis (13,7). En ce point il faut choisir si on transvase ou si on vide. Si on vide, on arrive en (13,0) puis (6,7) (6,1) (19,1) (19,0) (12,7) etc... alors que si on transvase, on arrive directement au point (19,1) et les points intermédiaires ne peuvent être visités que dans l'ordre (6,1) (6,7) (13,0) qui nous ramène sur (13,7).
Le même court-circuit se produit si on choisit sur le trajet rouge depuis le point (14,6) de transvaser au lieu de vider. On arrive directement au point (19,1) qui est normalement vers la fin de la chaîne rouge.

Les brisures de remplissages/vidages interdisent un calcul simple, par exemple du point (15,0) sur le trajet rouge, on remplit le récipient de 7 litres en deux fois : (15,5), il faut d'abord vider le récipient de 19 (2,5) avant de poursuivre le remplissage du récipient 7 (2,7). De plus l'existence du raccourci complique encore les choses.

graphe3 Il n'est pas même simple de déterminer si le problème a une solution.

Par exemple avec un réservoir de 9 litres plein et deux récipients vides de 5 et 7 litres. Les seuls points accessibles sont ceux marqués.
Une répartition 6 litres 3 litres est ainsi impossible.

graphe4Coordonées Trilinéaires

Une autre façon de voir les choses est d'utiliser un système de "coordonnéres trilinéaires". Dans le dernier example, la quantité totale disponible est de 9 litres.
On peut donc représenter tous les états possibles comme des points dans un triangle équilatéral de côté 9 litres. Les distances aux côtés représentant les quantités dans chaque récipient. Un transvasement consiste en un déplacement sur une ligne parallèle à un côté (quantité dans un récipient = constante). Comme la quantité dans le récipient de 5 litres ne peut pas dépasser 5 litres, la zone autorisée est limitée par la ligne à distance 5 du côté correspondant. Et de même pour le récipient de 7 litres. Comme précédement, les points accessibles sont uniquement ceux sur le pourtour du polygone.
La ligne verte forme une boucle, et aucun point de cette boucle ne peut être atteint depuis l'extérieur de la boucle.

L'état initial (0,0,9) n'est pas sur la boucle et donc seuls les points violets sont accessibles depuis cet état initial (chemin bleu clair). Noter que depuis un point de la boucle verte, on peut aussi atteindre la boucle bleue. Et donc depuis un point sur la boucle verte, par exemple (1,0,8), tous les points sont accessibles.
L'avantage de cette méthode est le rôle symétrique joué par les trois récipients. Mais sinon elle est identique, simplement les axes sont inclinés à 60° au lieu d'être perpendiculaires.

Partages

2 voleurs

Partager un tonneau de 16 litres en utilisant des récipients de 11 et 7 litres.
La méthode ci-dessus donne la solution. En commençant par remplir le récipient de 7 litres :
(9,0,7) (9,7,0) (2,7,7) (2,11,3)...(7,9,0) (0,9,7) (0,11,5) (11,0,5) (11,5,0) ... (en vert).
en fait le raccourci (5,11,0) (0,11,5) (11,0,5) (11,5,0) (4,5,7) (4,11,1) (15,0,1) (15,1,0) (8,1,7) (8,8,0) donne 10 opérations seulement.

Mais en commençant dans l'autre sens :
(5,11,0) (5,4,7) (12,4,0) (12,0,4) (1,11,4) (1,8,7) (8,8,0) est encore plus rapide (en bleu).

3 voleurs

Partager un tonneau de 24 litres en utilisant des récipients de 5, 11 et 13 litres. En fait on veut obtenir 8 + 8 + 8 donc dans un premier temps 8 + 16. On remarque deux coïncidences qui simplifient le problème : 8 = 13 - 5 et 16 = 11 + 5 qui conduisent à deux méthodes différentes.
  1. Remplir le récipient de 13 litres, le vider dans celui de 5, il y reste 8 litres. Partager les 16 litres restant en deux en n'utilisant plus le récipient de 13 litres mais seulement ceux de 24, 11 et 5.
    Variante : transvaser les 8 litres dans le récipient de 11 litres pour effectuer le partage avec les récipients de 24, 13 et 5 litres.

  2. Remplir les récipients de 5 et 11 litres. Il reste 8 litres dans le tonneau. Partager les 16 litres en n'utilisant que les récipients de 5, 11 et 13
On est alors ramené à trois problèmes de partage en deux, et il restera à choisir la meilleure solution sur les trois.
  1. partager 16 litres en utilisant 24, 11 et 5 soit 11X + 5Y = 8, X0 = 3, Y0 = -5 et X1 = -2, Y1 = 6
  2. partager 16 litres en utilisant 24, 13 et 5 soit 13X + 5Y = 8, X0 = 1, Y0 = -1 et X1 = -4, Y1 = 12
  3. partager 16 litres en utilisant 13, 11 et 5 soit idem 1.
    sauf qu'il y a un raccourci car la réserve est limitée à 13 et que 13 - 5 = 8
Le X0 = 1 Y0 = -1 du 2) semble bien parti pour remporter la palme de la solution la plus courte :
(24,0,0,0) (11,13,0,0) (11,8,0,5) (11,0,8,5) (11,5,8,0) (3,13,8,0) (3,8,8,5) (8,8,8,0)
Mais le raccourci du 3) n'a pas dit son dernier mot :
(24,0,0,0) (13,0,11,0) (8,0,11,5) (8,5,11,0) (8,13,3,0) (8,8,3,5) (8,8,8,0)
Et c'est finalement là la solution optimale.

mesures

Deux récipients de 1 litre pleins et deux mesures de 40 et 70 cl vides Mesurer 30 cl dans chacune des deux mesures.
Obtenir 30cl est simple : remplir la mesure de 70cl. Il reste 30 cl dans le récipient de 1 litre.
Une autre façon d'obtenir 30cl est de vider la mesure de 70cl pleine dans la mesure de 40cl Il reste 30cl dans la mesure de 70.

La difficulté est de transvaser les deux fois 30 cl obtenus dans les bons récipients ! Et pour cela utiliser l'autre récipient de 1 litre. Malheureusement il est plein ! Il faut donc trouver d'autres façons d'obtenir 30 cl.
Comme on veut terminer avec les 2x 30cl dans les mesures, la dernière opération est :

 1. soit de vider 40 cl de la mesure pleine de 70 dans un litre contenant 60cl
 2. soit de vider 10 cl de la mesure de 40 pleine dans un litre contenant 90cl
Dans chaque cas, l'autre mesure contenant déjà ses 30 cl souhaités.

  1. Le litre contenant 60cl est facile à obtenir : remplir la mesure de 40 Il reste alors à obtenir 30cl dans la mesure de 40 avec les mesures de 1 litre pleine, de 70cl vide et de 40 pleine soit 140cl en tout.
    graphe5C'est encore un problème avec contraintes. En appelant x la quantité dans la mesure de 70 et y celle dans la mesure de 40 la contrainte est x + y ≥ 40.
    Le problème s'avère impossible car les points cherchés ne sont pas des sommets sur la trajectoire.

     

  2. Le litre avec 90cl s'obtient un peu plus difficilement mais a l'avantage qu'il y a moins de liquide dans les autres récipients ce qui allège la contrainte.
    (100,100,0,0) (100,60,40,0) (100,0,40,60) (90,0,40,70)
    Il reste à obtenir 30cl dans la mesure de 70 ce qui est assez facile :
    (90,40,0,70) (90,40,40,30)
    Et c'est fini : (100,40,30,30)

     

Accueil Arithmétiques Géométrique Divers Thèmes Scripts Jeux Exercices Précédent Suivant Parent