backup del Post

Di pozzi e problemi

«Mio cuggino mio cuggino (cit.) deve andare al pozzo a prendere esattamente cinque litri d’acqua. Purtroppo ha solo a disposizione un secchio da tre litri e uno da sette. Come può riuscire nel suo intento?»

Questo problema, o una sua variante, è uno dei più famosi nel campo della matematica ricreativa. Ho verificato: un problema simile, che consiste nel dividere in due parti uguali otto litri di vino avendo a disposizione altre due botti vuote una di tre e una di cinque litri, era già presente nel manoscritto Vat. Lat. 3129 di Fra’ Luca Pacioli, della fine del XV secolo, e probabilmente è ancora anteriore. Erano i bei tempi in cui le persone erano abbastanza brave da non versare nulla per terra durante i travasi, e almeno nel primo caso non dovevano preoccuparsi delle tariffe dell’acqua, che forse non era un bene comune ma almeno era abbastanza liberamente disponibile senza dover pagare le bollette. Ma torniamo al problema: devo risolvervelo io, o ce la fate da soli?

Immagino che con un po’ di tentativi ci siate riusciti tutti, al limite sprecando un po’ d’acqua: quello che serve è avere un po’ di pazienza e poi si arriva alla soluzione. Ma i matematici spesso non sono tipi pazienti: così c’è stato chi ha pensato di trovare un metodo sicuro (quello che gli informatici chiamano “algoritmo”) per arrivare alla soluzione. Howard Grossman aveva una rubrica intitolata “Fun with Lattice Points” nella rivista Scripta Mathematica, e nel numero di marzo 1948 presentò il seguente metodo aritmo-geometrico per generare una soluzione di problemi di questo tipo. (In realtà, come dice Futility Closet da cui ho brutalmente preso questo problema, Grossman aveva dato una soluzione rigorosamente algebrica già nel 1940: ma come capita spesso la soluzione algebrica è pallosa, e per i nostri scopi è meglio lavorare meno rigorosamente).

Generalizzando il problema, bisogna ottenere l litri d’acqua avendo a disposizione due secchi di h e k litri. Potete immaginare che h e k siano primi tra loro, perché altrimenti o il problema è impossibile (se l non è anche multiplo del massimo comun denominatore degli altri due numeri) oppure si possono dividere tutti e tre i numeri per il suddetto MCD; inoltre h+k deve essere maggiore di l. Senza perdere in generalità, possiamo anche supporre che h sia maggiore di k. Prendete ordunque un bel foglio quadrettato, oppure se siete tipi che amate la manualità piantate un bel po’ di chiodini a costruire una grata a quadratini; scegliete un punto in basso a destra e chiamatelo O come origine, e prendete il punto P a distanza (h,k) dall’origine. Tracciate una riga tra O e P: è facile dimostrare che tale riga non tocca alcun altro punto. Qui arriva il colpo di genio: costruite una spezzata r i cui lati siano orizzontali e verticali, i cui vertici siano i punti della grata, che non tocchi il segmento OP ma arrivi il più vicino possibile, come si vede qui a fianco.

A questo punto immaginate di avere una pseudodistanza di tipo tassistico, in cui ogni passo a destra valga +h e ogni passo in alto −k; è allora possibile dimostrare che gli h+k−1 punti nella spezzata tra O e P esclusi assumeranno in un certo ordine tutti i valori da 1 a h+k−1. (Aiutino per chi volesse dimostrarlo: non si può raggiungere o superare h+k, e se mancasse qualche valore allora per il principio dei cassetti ce ne dovrebbe essere uno doppio, il che non è possibile). Quindi ci deve essere un punto X a distanza esattamente l; quel punto, che in questa figura è casualmente a distanza tassistica 5 dall’origine, corrisponderà alla soluzione del problema, se si seguono i passi dell’algoritmo spiegato qui sotto.

 [1] Se si fa un passo a destra, innanzitutto si versi l’eventuale acqua dal recipiente h a quello k; poi si riempia il recipiente h.
[2] Se si fa un passo verso l’alto, si versi l’acqua dal recipiente h a quello k; poi si svuoti il recipiente k.

Sono sicuro che vi siete accorti come il passo [1] aumenti di h litri il totale di acqua nei secchi, mentre il passo [2] lo faccia diminuire di k litri, in maniera coerente con la distanza da noi definita. La spezzata OP avrà pertanto i seguenti valori per le coppie h,k:

 (0,0), (7,0), (4,0), (1,0), (7,1), (5,0), (2,0), (7,2), (6,0), (3,0), (0,0)

Notate inoltre che esiste sempre una soluzione duale, rappresentata dalla spezzata r’ nel disegno. Purtroppo il metodo ha una falla, nel senso che non è possibile sapere esattamente qual è il punto corrispondente alla soluzione cercata e bisogna comunque fare il percorso: però non bisogna fare troppa fatica a seguire l’algoritmo, il che è sempre utile.