L'incubo dei due recipienti

Creato il 21 febbraio 2014 da Tanks @tanks
Se

 non vi è mai capitato di cimentarvi nel giochino dei due recipienti, allora delle due l'una: o non siete ancora emersi dalla primissima infanzia, oppure siete refrattari agli interrogativi logico-matematici.
Il testo è più o meno sempre lo stesso, cambiano solo le quantità:
«Ho due recipienti non graduati, uno da 11 litri, l'altro da 7. Come posso ottenere 6 litri d'acqua in uno dei due contenitori, avendo a disposizione una quantità infinita d'acqua, ma senza bilance o altri strumenti di peso o misura?»
I refrattari si limitano a sollevare un sopracciglio e a commentare: «Procurati un contenitore da 6 e non sprecare tutta quell'acqua».
Noi altri, invece, in genere ci buttiamo a capofitto su sequenze più o meno casuali di riempi-travasa-svuota, arrivando, prima o poi, alla soluzione.
Una piccola riflessione logica aiuta però a risolvere una volta per tutte questo tipo di problema.
Prima considerazione: poiché non si possono misurare in alcun modo le quantità d'acqua, se non riempendo un contenitore vuoto o svuotando un contenitore pieno, le soluzioni potranno essere solo del tipo:

  • riempio x volte il recipiente da 11 e svuoto y volte quello da 7, rimanendo esattamente con 6 litri: 11x - 7y = 6 
  • riempio x volte il recipiente da 7 e svuoto y volte quello da 11, rimanendo esattamente con 6 litri: 7x - 11y = 6 

Questo tipo di equazione (con più variabili, coefficienti interi e di cui interessano le soluzioni intere o, in generale, razionali) fu studiato per la prima volta nel III secolo dal matematico greco Diofanto, da cui il nome di Equazione diofantea.
Chi volesse seguire la strada del rigore può a questo punto esplorare l'argomento con Google. Per gli altri esiste un'altra strada, un po' più divertente: un modello di simulazione al calcolatore. Vediamone uno in excel (file scaricabile dal mio sito Digiland).
La struttura del simulatore è semplice:

  • un'intestazione con i dati del problema (che quindi possono essere modificati: celle C2, C3 e C4) 
  • due simulazioni, una per "riempi primo contenitore - svuota secondo" e l'altra per "riempi secondo contenitore - svuota primo"; a colpo d'occhio si vede poi quale delle due strade conviene 
  • in ciascuna delle due simulazioni, si determina la prossima azione da effettuare (colonne B e F), sulla base del contenuto dei due recipienti (colonne C-D e G-H) e poi la si esegue (es.: decisione nella cella B8, esecuzione nelle celle C8 e D8) 
  • una volta raggiunta la quantità voluta, la simulazione si ferma 

Come funziona la decisione? Vediamo il contenuto della cella B8: 

=SE(O(B7="stop";B7="");"";SE(C7=C$4;"stop";SE(D7=C$3;"svuota B";SE(O(D7=0;C7=C$2);"travasa da A in B";"riempi A"))))

che tradotto in parole semplici vuol dire:

  • se la simulazione è finita, rimani fermo 
  • in caso contrario, se nel recipiente A ho i miei 6 litri, fermati 
  • altrimenti se il recipiente B è pieno, svuotalo 
  • in caso contrario, se B è vuoto o A è pieno, travasa quello che puoi da A a B
  • altrimenti riempi A

Nella cella C8 c'è invece l'esecuzione per il recipiente A:

=SE(O(B8="stop";B8="");"";SE(B8="travasa da A in B";C7-MIN(C7;C$3-D7);SE(B8="riempi A";C$2;C7))), cioè:

  • se la simulazione è finita, rimani fermo 
  • se devi travasare, travasa 
  • se devi riempirti, riempiti

Cosa analoga vale per D8 e il recipiente B.
Il nostro caso si risolve quindi con: 5 riempimenti del contenitore più grosso e 6 svuotamenti di quello piccolo (più uno svuotamento finale se vogliamo ritrovarci con la soluzione x = 5 e y = 7 della prima equazione), oppure 4 riempimenti del piccolo e 1 svuotamento (più svuotamento finale) del grande, che è la soluzione più rapida.
La convenienza si ribalterebbe se ci fosse richiesto di isolare non 6 litri ma 5 (inserire 5 nella cella C4). In questo caso la procedura più veloce diventa riempire il contenitore grosso 3 volte e svuotare l'altro 3 (+1) volte: 3 * 11 - 4 * 7 = 33 - 28 = 5.
Mai più rompicapo di questo tipo, quindi.

Buon venerdì.

[Tutti i post su numeri e giochi.]