L'indovinello dei travasi
by Pasquale
Nel film Die Hard - Duri a morire, la coppia del poliziotto McClane (Bruce Willis) e del negoziante Zeus Carver (Samule L. Jackson) si trova a risolvere un enigma logico-matematico per disinnescare una bomba che sta per esplodere.
Devono isolare una quantità di 4 galloni d'acqua, avendo a disposizione due recipienti non graduati da 3 e 5 galloni, rispettivamente. Ci riescono, ovviamente pochi attimi prima dell'esplosione, mediante una serie di: riempi, svuota e travasa tra i due recipienti.
Come si affronta un problema del genere? Quando è possibile trovare una soluzione, e quando no? Vediamo come risolvere, a cavallo tra matematica e Python.
Le mosse del gioco
Per dare un minimo di generalità al problema, denotiamo con A e B i due recipienti e con Q la quantità di acqua da isolare.
Si può procedere attraverso questo approccio:
- riempire il recipiente A;
- versare il contenuto di A in B, tutto o per quanto è possibile senza far traboccare B;
- quando B si riempie completamente, svuotarlo;
- ripetere i punti 2. e 3., fino a che:
- in uno dei due contenitori rimane la quantità Q (gioco risolto! fine della procedura),
- oppure A si svuota;
- ripartire dal punto 1.
È ovviamente possibile anche eseguire la procedura scambiando i ruoli tra A e B.
Che una delle due sequenze (o entrambe) risolvano il problema è ancora da dimostrare, è però evidente (o almeno così mi pare) che non vi siano altri metodi percorribili.
Un'equazione diofantea e la matematica dell'orologio
Cerchiamo di tradurre in termini matematici la prima delle due procedure. Per l'altra si potrà procedere in modo analogo.
Alla fine del gioco, avremo riempito x volte il contenitore A e svuotato y volte il contenitore B, arrivando alla situazione in cui in A o in B si trova una quantità Q di acqua. In altri termini:
xA = yB + Q
Un'equazione di questo tipo, si dice diofantea, dal matematico greco Diofanto di Alessandria, quando i coefficienti A, B e Q, e le soluzioni x, y sono numeri interi.
Un altro modo di scrivere questa equazione è quello di utilizzare l'aritmetica modulare, inventata da Carl Friedrich Gauss, e anche detta aritmetica dell'orologio:
xA ≡ Q mod B
Ebbene, si dimostra che questa congruenza:
- se A e B sono primi tra loro, ha esattamente una soluzione;
- se A e B hanno un MCD d ≠1, ha d soluzioni se d divide Q;
- in tutti gli altri casi, ha zero soluzioni.
L'aritmetica modulare spiegata semplice
Beh, quantomeno spero di riuscire a raccontarla in modo semplice.
Partiamo dall'orologio: se aggiungo 7 ore alle 10 (di mattina o di sera) ottengo le 5 (rispettivamente di sera o di mattina). Sto eseguendo infatti una somma in modulo 12, e il risultato di un'operazione tra interi potrà solo dare un risultato intero tra 0 e 11.
Nella notazione modulare, l'operazione si scrive così:
7 + 10 ≡ 5 mod 12
e si legge: 7 più 10 è congruente a 5, modulo 12.
La divisione tra interi fornisce un altro modo per spiegare la congruenza:
7 + 10 fa 17, che diviso per 12 dà un resto di 5
Nell'aritmetica modulare le congruenze prendono il posto delle equazioni. Ci si può chiedere, ad esempio, quali valori interi di x soddisfino la congruenza:
11x ≡ 4 mod 7
Per risolverla, occorre trovare un multiplo di 11 che sia contiguo a un multiplo di 7. Un po' di calcolo mentale e si nota che 22 e 21 sono contigui.
Bene, moltiplichiamo entrambi i membri della congruenza per 2, e sviluppiamo:
22x ≡ 8 mod 7
21x + x ≡ 7 + 1 mod 7
x ≡ 1 mod 7
La risoluzione dell'indovinello di Die Hard
Le due congruenze in gioco in questo caso sono:
3x ≡ 4 mod 5 [1]
5y ≡ 4 mod 3 [2]
Che conducono a due diverse strategie di soluzione. Risolviamo prima la [1].
Moltiplichiamo per 3 entrambi i membri:
9x ≡ 12 mod 5
10x - x ≡ 10 + 2 mod 5
-x ≡ 2 mod 5
x ≡ 3 - 5 mod 5
x ≡ 3 mod 5
Quindi occorrerà riempire 3 volte il recipiente A (capacità: 3 galloni, per un totale di 9 galloni), svuotare 1 volta il recipiente B (5 galloni). In B rimangono 4 galloni, come richiesto.
Cosa accade risolvendo la [2]? Riscriviamola come:
6y - y ≡ 3 + 1 mod 3
-y ≡ 1 mod 3
y ≡ 2 - 3 mod 3
y ≡ 2 mod 3
Quindi, in questo caso, occorre riempire due volte il contenitore B (10 galloni), svuotandolo 2 volte nel recipiente A (6 galloni), lasciando 4 galloni in B.
Un semplice programma Python per risolvere l'indovinello
Il codice del programma, con i valori dei due contenitori richiesti dalla [1]:
A,B = 3,5
Q = 4
#
a,b = 0,0
n_op, n_op_max = 0, B + 1
#
while a != Q and b != Q and n_op < n_op_max:
if a == 0:
a = A
n_op += 1
print (n_op, '- riempio A [{}/{}, {}/{}]'.format(a, A, b, B))
elif b == B:
b = 0
print (n_op, '- svuoto B [{}/{}, {}/{}]'.format(a, A, b, B))
elif a <= B - b:
b = b + a
a = 0
print (n_op, '- travaso A in B [{}/{}, {}/{}]'.format(a, A, b, B))
else:
t = B - b
a -= t
b = B
print (n_op,'- travaso {} da A in B, fino a riempire B [{}/{}, {}/{}]'.format(t, a, A, b, B))
#
if a == Q:
print ('in A è rimasta una quantità',a)
elif b == Q:
print ('in B è rimasta una quantità',b)
else:
print ('non ho trovato una soluzione')
Ed ecco il risultato:
1 - riempio A [3/3, 0/5]
1 - travaso A in B [0/3, 3/5]
2 - riempio A [3/3, 3/5]
2 - travaso 2 da A in B, fino a riempire B [1/3, 5/5]
2 - svuoto B [1/3, 0/5]
2 - travaso A in B [0/3, 1/5]
3 - riempio A [3/3, 1/5]
3 - travaso A in B [0/3, 4/5]
in B è rimasta una quantità 4
In ogni riga viene riportato:
- il numero di riempimenti di A, fina a quel punto;
- l'azione compiuta;
- lo stato in cui vengono lasciati A e B.
Scambiando i valori di A e B si ottiene la soluzione per l'equazione [2]:
A,B = 5,3
Il risultato diviene:
1 - riempio A [5/5, 0/3]
1 - travaso 3 da A in B, fino a riempire B [2/5, 3/3]
1 - svuoto B [2/5, 0/3]
1 - travaso A in B [0/5, 2/3]
2 - riempio A [5/5, 2/3]
2 - travaso 1 da A in B, fino a riempire B [4/5, 3/3]
in A è rimasta una quantità 4
E ora, basta travasi!
Nota: questo post riprende un mio vecchio post su Wix.com.