Kinesys atterra con un tonfo accanto alla Fontana della Giusta Misura, il pozzo pubblico di Staterion, dove gli abitanti fanno la fila con taniche di ogni capacità. Qui l’acqua si distribuisce al litro esatto: su Staterion “più o meno quattro litri” è un’espressione vietata per legge.
Liz deve procurarsi esattamente 4 litri d’acqua per il sistema di raffreddamento della nave. Il custode della fontana le presta due taniche vuote: una da 3 litri e una da 5. Nessuna tacca, nessuna misura intermedia, e la grande bilancia della fontana, da regolamento, serve solo per il controllo finale.
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?
Suggerimento
Riempire e svuotare non basta: il segreto sono i travasi. Provate a ottenere e a conservare quantità intermedie, per esempio quello che resta nella tanica da 5 dopo averla usata per riempire quella da 3.
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.
Al controllo finale la bilancia della fontana segna 4 litri esatti, e il custode lascia passare Liz con un cenno di approvazione.