Problemes de garrafes

És possible que recordis la pel·lícula La jungla de cristall 3 on els protagonistes, a més de la força bruta, han de fer funcionar el magí per resoldre alguns petits problemes matemàtics. En aquest fragment s'enfronten a un clàssic problema de transvasament de líquids.

Però aquest és un tipus de problema amb història i algorismes propis.

Un dels primers llocs on es van proposar aquesta mena de problemes va ser la llibre Problèmes plaisans et délectables, qui se font par les nombres, partie recueillis de divers autheurs, et inventez de nouveau, avec leur démonstration de Claude Gaspard Bachet de Méziriac i publicat fa quatre-cents anys, al 1612.

Anem ara al cas concret que ens planteja la pel·lícula. Hem d'aconseguir mesurar exactament 4 galons disposant d'un recipient de 5 i un de 3. A la seqüència hauràs vist que ens han escamotejat un tros de la solució, així que no ens queda una altra opció que practicar nosaltres mateixos. Aquí tens enllaçat un applet (flash) que et permetrà fer-ho.

Enllaç a l'applet interactiu (flash)

Ara et proposem que tornis a fer el problema començant per l'altra garrafa. Segons per quina ho facis necessitaràs més operacions o menys, però sempre es pot resoldre. I, si penses bé cada pas, veuràs que només hi ha un de bo. Pots descartar les opcions que et porten a situacions repetides anteriors o inútils.

El fet de que l'opció útil sigui gairebé única cada vegada ens fa pensar en la possibilitat de que existeixi un algorisme per resoldre aquesta mena de situacions. Efectivament és així i és curiós perquè la seva resolució és gràfica.
Es basa en dibuixar un itinerari sobre un rectangle "graduat" de 5x3 i traduir sobre una taula cada situació de la gràfica. L'itinerari surt d'un punt inicial. En el nostre cas omplir el recipient de 3 galons i que anotarem (0,3). Després cada línia que surti de cada costat del rectangle, de cada "paret", pren una direcció concreta. Quan s'arriba a un altre costat anotem la posició i dibuixem una nova línia segons la direcció que correspon a aquell costat. Així fins arribar a la solució buscada (4,0).

Algoritme transvasaments from calaix2ie

Com es pot veure cada direcció correspon a una acció:

• la fletxa horitzontal representa omplir el recipient de 3
• la vertical buidar el de 5
• la fletxa en diagonal representa el transvasament de 3 a 5

Modificant convenientment el tipus de rebot podem trobar la solució que comença omplint el recipient de 5 galons.

Bé. Ja ho tenim tot: història del problema i mètode per resoldre'l. Només toca proposar algunes variants, totes del llibre de Bachet:

• Mesurar 6 litres amb garrafes de 5 i 7.
• Mesurar 8 litres amb garrafes de 9 i 7.
• Mesurar 8 litres amb garrafes de 11 i 6.
• Mesurar 21 amb garrafes de 27 i 12.