Kinesys atterra su Abakos accanto a una fontana pubblica, dove gli abitanti fanno la fila con taniche di ogni capacità. Su questo pianeta l’acqua si baratta al litro esatto, e chi si presenta al mercato con una quantità sbagliata viene rimandato indietro con un rimprovero numerato.
Liz deve procurarsi esattamente 4 litri d’acqua per il sistema di raffreddamento della nave. Il negoziante le presta due taniche vuote: una da 3 litri e una da 5. Nessuna tacca, nessuna misura intermedia.
Dord trova la cosa inaccettabile: “Chi fabbrica taniche senza tacche?” Liz, per non perdere la pazienza, accenna un passo di tip tap sul selciato. M00N saluta la fila con entusiasmo.
Quesito
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 svuotare le taniche, oltre che trasferire acqua dall’una all’altra, dovete mettere esattamente 4 litri d’acqua dentro la tanica da 5. Come bisogna procedere?
Soluzione
Innanzitutto si riempie la tanica da 5 e se ne trasferiscono 3 litri in quella da 3: nella tanica da 5 restano 2 litri. Poi si svuota la tanica da 3 e vi si trasferiscono i 2 litri rimasti nella tanica da 5. A questo punto si riempie di nuovo la tanica da 5 e si trasferisce 1 litro nella tanica da 3, che così è piena. Nella tanica più grande restano esattamente 4 litri.
Per risolvere in generale problemi come questo è utile rappresentare ogni configurazione con una coppia di numeri (n1, n2), che indicano i litri d’acqua contenuti rispettivamente nella tanica da 3 e in quella da 5. Si costruisce poi un grafo i cui nodi sono queste coppie: da ogni nodo partono frecce verso i nodi che si ottengono applicando una delle regole seguenti:
- riempimento della tanica 1
- riempimento della tanica 2
- svuotamento della tanica 1
- svuotamento della tanica 2
- trasferimento dalla tanica 1 alla tanica 2
- trasferimento dalla tanica 2 alla tanica 1
Il numero di frecce che partono da ogni nodo è uguale al numero di regole applicabili a quella configurazione. Una volta completato il grafo (facendo attenzione a non introdurre nodi già esistenti), resta solo da individuare il percorso che porta dalla configurazione iniziale a quella finale desiderata. In pratica si è costruito il diagramma degli stati di un automa a stati finiti, con due variabili di stato (il contenuto delle due taniche) e sei ingressi (le regole); l’uscita dell’automa coincide praticamente con lo stato.
Nel nostro caso il percorso da seguire è:
(0, 0) → (0, 5) → (3, 2) → (0, 2) → (2, 0) → (2, 5) → (3, 4)
ottenuto applicando le regole 2 – 6 – 3 – 6 – 2 – 6.