Testo nascosto, fai click qui per vederlo
Siano $A, B, C$ i tre secchi e $0<a<=b<=c$ il loro contenuto in un numero interi di litri.
Sia $b=qa+r$ dove $0<=r<a$ e $q>=1$ sono interi.
Scrivo $q$ in binario così $q=q_0+2q_1+...+2^nq_n$ dove ogni $q_i$ vale $0$ o $1$ e $q_n=1$.
La procedura consiste in $n+1$ "mosse", numerate da $0$ a $n$, eseguite come segue:
Alla mossa $i$-esima verso da $B$ in $A$ se $q_i=1$ altrimenti verso da $C$ in $A$ se $q_i=0$.
Compiute le $n+1$ mosse, avrò versato una quantità $qa$ da $B$ in $A$ ed in $B$ saranno rimasti $b-qa=r<a$ litri ovvero ho ottenuto un secchio che contiene meno acqua di ciascuno dei secchi originari.
Ripetendo questa procedura un numero finito di volte finirò con l'ottenere un secchio vuoto.
Si può notare che da $C$ al massimo avrò versato $sum_(i=0)^(n-1) 2^ia<2^na<=qa<=b<=c$, quindi in $C$ c'è sempre acqua a sufficienza.
Conosco un'altra soluzione che va al contrario ma non l'ho capita bene …
Sia $b=qa+r$ dove $0<=r<a$ e $q>=1$ sono interi.
Scrivo $q$ in binario così $q=q_0+2q_1+...+2^nq_n$ dove ogni $q_i$ vale $0$ o $1$ e $q_n=1$.
La procedura consiste in $n+1$ "mosse", numerate da $0$ a $n$, eseguite come segue:
Alla mossa $i$-esima verso da $B$ in $A$ se $q_i=1$ altrimenti verso da $C$ in $A$ se $q_i=0$.
Compiute le $n+1$ mosse, avrò versato una quantità $qa$ da $B$ in $A$ ed in $B$ saranno rimasti $b-qa=r<a$ litri ovvero ho ottenuto un secchio che contiene meno acqua di ciascuno dei secchi originari.
Ripetendo questa procedura un numero finito di volte finirò con l'ottenere un secchio vuoto.
Si può notare che da $C$ al massimo avrò versato $sum_(i=0)^(n-1) 2^ia<2^na<=qa<=b<=c$, quindi in $C$ c'è sempre acqua a sufficienza.
Conosco un'altra soluzione che va al contrario ma non l'ho capita bene …
Cordialmente, Alex
