Avete a disposizione due taniche inizialmente vuote la cui capacità è rispettivamente di 3 e 5 litri. Avendo a disposizione tutta l’acqua che desiderate, e potendo riempire e vuotare le taniche, oltre che potere trasferire acqua da una all’altra, dovete mettere esattamente 4 litri di acqua dentro la tanica da 5. Come bisogna procedere?
Soluzione
Per ottenere il risultato voluto, bisogna innanzitutto riempire la tanica da 5 e quindi trasferirne 3 litri nell’altra. In questo modo saranno rimasti 2 litri in quella da 5. Successivamente si svuota quella da 3 e si trasferiscono i 2 litri precedenti dalla tanica da 5 a quella da 3. A questo punto riempiamo di nuovo quella da 5 e trasferiamo 1 litro in quella da 3 in modo da riempire quest’ultima. Il risultato ottenuto sarà quello di avere 4 litri di acqua nella tanica più grande.
Per la risoluzione generale di problemi come questo risulta utile rappresentare ogni configurazione del contenuto delle due taniche con una coppia di numeri (n1, n2) che rappresentano i litri d’acqua contenuti rispettivamente nei due recipienti. A questo punto bisogna costruire un grafo, i cui nodi sono appunto costituiti dalle coppie descritte in precedenza. A partire da ogni nodo bisogna poi costruire i nuovi nodi che si possono ottenere applicando una delle regole seguenti:
- Riempimento tanica 1
- Riempimento tanica 2
- Svuotamento tanica 1
- Svuotamento tanica 2
- Trasferimento da 1 a 2
- Trasferimento da 2 a 1
In questo modo, avremo che nel nostro grafo, da ogni nodo partiranno alcune frecce dirette verso altri nodi, ed il numero di tali frecce è uguale a quello delle diverse regole che si possono applicare a quella particolare configurazione. Una volta completata la costruzione di tale grafo, avendo attenzione di non introdurre nuovi nodi se questi esistono già, ci resterà soltanto da individuare il percorso che ci porta dalla configurazione iniziale a quella finale desiderata. Come molti avranno già potuto notare, non abbiamo fatto altro che costruire il diagramma degli stati di quello che comunemente viene chiamato un automa a stati finiti. Questo automa è dotato di due variabili di stato che coincidono con il contenuto delle due taniche, e di sei ingressi, che non sono altro le regole applicative. In questo caso l’uscita dell’automa non è molto significativa, infatti coincide praticamente con lo stato.
Nel nostro caso il percorso da seguire per raggiungere il risultato voluto è il seguente:
(0,0) – (0,5) – (3,2) – (0,2) – (2,0) – (2,5) – (1,4)
che è il risultato dell’applicazione delle regole: 2 – 6 – 3 – 6 – 2 – 6.