Due brocche, un’equazione: dal problema 3–5 a Bézout

Due brocche senza tacche, una sorgente d’acqua e un obiettivo preciso: misurare una quantità che nessuna delle due capacità indica direttamente. Il rompicapo è concreto, ma conduce con naturalezza agli interi, al massimo comune divisore, all’identità di Bézout e agli algoritmi sui grafi.

Il criterio aritmetico dice se l’obiettivo supera il filtro della divisibilità; i limiti di capacità e gli stati delle brocche stabiliscono se e come realizzarlo fisicamente. Sono risposte diverse e complementari.

1. Regole e obiettivo

Nel modello classico aperto disponiamo di acqua senza limiti, di uno scarico e di due brocche di capacità intera, prive di graduazioni. Una mossa legale è soltanto una delle seguenti:

• riempire completamente una brocca dalla sorgente;
• svuotare completamente una brocca nello scarico;
• travasare da una brocca all’altra finché la prima è vuota oppure la seconda è piena.

Non si può interrompere un travaso “a occhio”. Nel problema principale le capacità sono 3 e 5 litri e l’obiettivo rigoroso è arrivare a (1,0): un litro nella brocca da 3 e la brocca da 5 vuota. Scriveremo sempre uno stato come (u,v), dove u è il contenuto della brocca da 3 litri e v quello della brocca da 5.

2. Il caso 3–5, stato per stato

Dalle brocche vuote a un litro isolato

Passo	Mossa	Stato	Esito della mossa
0	Partenza	(0,0)	Entrambe vuote
1	Riempi la brocca da 3	(3,0)	La brocca è piena
2	Versa dalla 3 nella 5	(0,3)	La brocca da 3 si svuota
3	Riempi di nuovo la 3	(3,3)	La brocca è piena
4	Versa dalla 3 nella 5	(1,5)	Nella brocca da 5 entrano soltanto 2 litri
5	Svuota la brocca da 5	(1,0)	Resta isolato il litro cercato

(0,0) → (3,0) → (0,3) → (3,3) → (1,5) → (1,0)

Ogni freccia rispetta le regole e ogni coordinata resta compresa tra zero e la capacità corrispondente. Questi due controlli semplici impediscono molte false soluzioni.

3. Stato, bilancio e invariante

Conviene tenere due registri. Lo stato fisico dice dove si trova l’acqua; il bilancio dice quanta acqua è presente in tutto e come è entrata o uscita. Nel percorso precedente:

Stato fisico e bilancio esterno

Stato	Totale presente	Bilancio esterno
(0,0)	0	0
(3,0)	3	3
(0,3)	3	3
(3,3)	6	2 · 3
(1,5)	6	2 · 3
(1,0)	1	2 · 3 − 5

Durante un travaso il totale u + v non cambia: cambia soltanto la sua distribuzione. Riempimenti e svuotamenti, invece, scambiano acqua con l’esterno. In questa sequenza entrano due brocche complete da 3 litri ed esce una brocca completa da 5, perciò:

1 = 2 · 3 − 5

C’è anche un invariante aritmetico più generale: ogni volume raggiungibile è una combinazione intera delle capacità. All’inizio compare solo zero; riempire introduce una capacità, svuotare introduce zero e un travaso produce somme o differenze con una capacità quando una brocca si svuota o l’altra si riempie. Le combinazioni intere restano quindi chiuse sotto tutte le mosse legali.

La coppia di coefficienti non è lo stato e non è unica. È un’etichetta algebrica utile per certificare il volume; lo stato (u,v) rimane la descrizione fisica indispensabile.

4. Il significato dei coefficienti negativi

Dalla sequenza otteniamo un’equazione diofantea, cioè un’equazione nella quale le soluzioni cercate devono essere numeri interi:

3x + 5y = 1,
x = 2, y = −1.

Il coefficiente −1 non rappresenta una quantità d’acqua negativa. Nel bilancio indica che una brocca completa da 5 litri è stata restituita allo scarico. I coefficienti contano contributi con segno; i contenuti reali delle brocche restano sempre tra zero e la loro capacità.

Questa lettura come conteggio netto è diretta nei percorsi canonici, nei quali si riempie una brocca soltanto quando è vuota e la si scarica soltanto quando è piena. Se si riempie o si svuota una brocca parzialmente piena, i coefficienti restano un certificato algebrico, ma non coincidono più semplicemente con il numero delle operazioni.

Questo chiarimento evita un equivoco: una soluzione intera dell’equazione è un certificato aritmetico, non ancora una successione automatica di riempimenti e travasi. Per ottenere le mosse occorre costruire un percorso fra stati legali.

5. Euclide esteso e identità di Bézout

Il massimo comune divisore di due interi positivi è il maggiore intero positivo che li divide entrambi. L’algoritmo di Euclide lo trova; risalendo le divisioni produce anche i coefficienti di Bézout:

5 = 1 · 3 + 2
3 = 1 · 2 + 1

1 = 3 − 2
  = 3 − (5 − 3)
  = 2 · 3 − 5

Abbiamo così ritrovato esattamente il bilancio del percorso. L’identità di Bézout afferma che, per interi positivi a e b, esistono interi r e s tali che:

a r + b s = MCD(a,b)

Moltiplicando l’identità per un intero si ottengono tutti gli obiettivi multipli del MCD. Per 3x + 5y = 1, partendo dalla soluzione (2,−1), tutte le soluzioni intere sono:

x = 2 + 5t
y = −1 − 3t,  con t intero.

Questa infinità algebrica non implica un’infinità di stati fisici: le brocche hanno capacità finite e molte coppie di coefficienti descrivono lo stesso volume senza suggerire un percorso conveniente.

6. Regola generale e limiti

Con capacità a e b e obiettivo d, l’equazione associata è:

a x + b y = d

Posto g = MCD(a,b), l’equazione ha soluzioni intere se e solo se g divide d. Nel modello aperto classico, per lasciare esattamente d litri in una sola brocca con l’altra vuota servono inoltre:

0 ≤ d ≤ max(a,b).

Le due condizioni sono anche sufficienti con le mosse standard. La divisibilità elimina gli obiettivi aritmeticamente impossibili; il limite di capacità elimina obiettivi che nessuna brocca può contenere. L’equazione ax + by = d riguarda il totale presente: per porlo uguale a d, al termine dobbiamo davvero avere l’altra brocca vuota. Se ci fermassimo, per esempio, con d in una brocca e altra acqua nell’altra, il totale non sarebbe d.

7. Il confronto 4–6: un litro no, due sì

Per brocche da 4 e 6 litri, MCD(4,6) = 2. Ogni combinazione 4x + 6y è pari, quindi un litro è impossibile. Non serve tentare mosse a caso: la parità è un invariante.

Due litri sono invece possibili perché 2 = 6 − 4:

(0,0) → (0,6) → (4,2) → (0,2)

Gli stati sono ordinati come (brocca da 4, brocca da 6): riempiamo la 6, versiamo nella 4 fino a riempirla e infine svuotiamo la 4. Restano 2 litri nella 6 e l’altra brocca è vuota.

8. Altri casi verificati

Brocche 3–5, obiettivo 4

Il certificato è 4 = 2 · 5 − 2 · 3. Ordinando gli stati come (3,5):

(0,0) → (0,5) → (3,2) → (0,2)
      → (2,0) → (2,5) → (3,4) → (0,4)

Ogni volta si versa fino a svuotare la sorgente o riempire la destinazione; lo stato finale contiene 4 litri nella brocca da 5.

Brocche 2–7, obiettivo 1

Qui 1 = 7 − 3 · 2. Ordinando gli stati come (2,7):

(0,0) → (0,7) → (2,5) → (0,5)
      → (2,3) → (0,3) → (2,1) → (0,1)

Si sottraggono ripetutamente porzioni da 2 litri dalla brocca da 7.

Brocche 6–10, obiettivo 8

MCD(6,10)=2 divide 8. Un certificato è 8 = 3 · 6 − 10; il percorso seguente realizza lo stesso volume con un altro bilancio, 8 = 2 · 10 − 2 · 6. Stati ordinati come (6,10):

(0,0) → (0,10) → (6,4) → (0,4)
      → (4,0) → (4,10) → (6,8) → (0,8)

Brocche 6–9, obiettivo 4

È impossibile: MCD(6,9)=3 non divide 4. Tutti i volumi raggiungibili sono multipli di 3.

9. La variante chiusa 8–5–3

Un altro classico usa tre recipienti da 8, 5 e 3 litri. Questa volta le ipotesi cambiano: il recipiente da 8 parte pieno, non esistono né sorgente né scarico, e sono consentiti soltanto travasi completi fino a svuotare la sorgente o riempire la destinazione. Bisogna dividere gli 8 litri in due parti da 4.

Scrivendo gli stati nell’ordine (8,5,3), una soluzione è:

(8,0,0) → (3,5,0) → (3,2,3) → (6,2,0)
        → (6,0,2) → (1,5,2) → (1,4,3) → (4,4,0)

Il totale è sempre 8: qui la conservazione dell’acqua è l’invariante dominante. Non possiamo applicare senza modifiche il criterio delle due brocche con sorgente e scarico; abbiamo tre capacità, un sistema chiuso e un obiettivo di ripartizione. Occorre dichiarare le ipotesi prima di usare un teorema.

10. Ricerca del percorso minimo e controllo finale

Il certificato di Bézout verifica la compatibilità aritmetica, ma non sostituisce il controllo della capacità e non garantisce che i coefficienti si traducano direttamente nel percorso più breve. Per cercarlo possiamo costruire il grafo orientato degli stati: ogni stato è un vertice e ogni mossa legale è un arco. Con due brocche esistono al massimo (a+1)(b+1) coppie, quindi una visita in ampiezza, o BFS, termina sempre.

coda ← [(0,0)]
visitati ← {(0,0)}

finché la coda non è vuota:
    stato ← estrai il primo
    se stato è (d,0) oppure (0,d): ricostruisci il percorso
    genera: riempi A, riempi B, svuota A, svuota B,
            travasa A→B, travasa B→A
    per ogni stato generato non presente in visitati:
        aggiungilo a visitati
        inseriscilo nella coda e salva il suo predecessore

La BFS visita prima i percorsi con meno archi: il primo percorso che raggiunge l’obiettivo usa il numero minimo di mosse rispetto alle regole dichiarate. Per il sistema chiuso 8–5–3 cambiano lo stato iniziale, il numero di coordinate, il test dell’obiettivo e il generatore: si parte da (8,0,0), si cerca (4,4,0) e si generano soltanto i travasi tra ogni coppia di recipienti.

Checklist di verifica

1. Indica l’ordine delle coordinate e controlla i limiti di capacità in ogni stato.
2. Verifica che ogni travaso termini con la sorgente vuota o la destinazione piena.
3. Calcola il MCD e controlla che divida l’obiettivo.
4. Controlla che d ≤ max(a,b) nel modello aperto con obiettivo in una brocca.
5. Non confondere coefficienti negativi con acqua negativa.
6. Non confondere un certificato di Bézout con la sequenza delle mosse.
7. Se usi ax+by=d come bilancio finale, verifica che l’altra brocca sia vuota.
8. Se cambiano sorgente, scarico o numero di recipienti, riformula lo spazio degli stati.

Tre controlli rapidi

• Con 6 e 10 litri, ottenere 5 è impossibile perché 2 non divide 5.
• Con 3 e 5 litri, il numero 7 è una combinazione intera, ma non può stare in una sola brocca: fallisce il limite di capacità.
• Con 4 e 6 litri, ottenere 2 è possibile e il percorso mostrato termina davvero con l’altra brocca vuota.

Il problema delle brocche mostra bene i diversi ruoli della matematica: l’invariante impedisce ricerche inutili, Bézout certifica la compatibilità aritmetica e il grafo degli stati, insieme ai vincoli fisici, trasforma quel certificato in una procedura concreta, verificabile e ottimizzabile.

---

A cura di Salvatore Mosaico.