I problemi concernenti l'attraversamento di un fiume da parte di mariti gelosi e delle loro mogli sono un classico della matematica ricreativa. Il più famoso e datato tra questi è sicuramente il seguente:
Tre mariti e le rispettive tre mogli devono attraversare un fiume su una barca che può trasportare al massimo due persone alla volta.Poiché i mariti sono molto gelosi, nessuna donna deve trovarsi mai assieme ad altri uomini se non in presenza del proprio marito. Come faranno le tre coppie ad attraversare il fiume?
La prima versione del problema così formulato, la troviamo nel "De viribus quantitatis" 1 di Pacioli. Informazioni dettagliate sulla storia del problema sono presenti nell'appendice del libro "Giochi matematici alla corte di Carlo Magno" 2.
Molto interessante è la generalizzazione del problema:
Un numero n di mariti si trova, assieme alle mogli, a dover passare un fiume e trova un battello senza battelliere. Questo battello non può portare più di (n-1) persone. Come possono attraversare il fiume queste 2n persone in modo tale che nessuna delle mogli rimanga in compagnia di un altro uomo, o di altri uomini, mentre suo marito non è presente?
Quest'ultimo viene trattato in modo quasi completo da Lucas nelle sue "Ricreazioni Matematiche" 3 (1894). Riporto di seguito la soluzione di Lucas, con l'aggiunta da parte mia delle dimostrazioni dei casi non esplicitati, e di quelli che Lucas rimanda al lettore. Seguendo l'approccio di Lucas, possiamo generalizzare il problema mediante elencazione di tutti i casi possibili con relativa dimostrazione.
Indichiamo con $n$ il numero di coppie (marito - moglie) da traghettare, e con $x$ il numero di posti sulla barca.
Ho individuato 10 casi possibili, che ricoprono tutte le casistiche, e sono:
- $2$ coppie - $2$ posti
- $3$ coppie - $2$ posti
- $4$ coppie - $2$ posti
- $n$ coppie - $2$ posti $n \ge 5$
- $4$ coppie - $3$ posti
- $5$ coppie - $3$ posti
- $n$ coppie - $3$ posti $n > 5$
- $n$ coppie - $4$ posti $n \ge 5$
- $n$ coppie - $x$ posti $ n \ge 5$,$\quad x \ge 4$, $x$ pari,$\quad n \ge x$
- $n$ coppie - $x$ posti $ n \ge 5$,$\quad x \ge 4$, $x$ dispari,$\quad n \ge x$
Quelli sottolineati sono stati dimostrati da Lucas; i restanti provo a dimostrarli io di seguito.
La situazione iniziale è la seguente:
| Prima riva | Seconda riva |
|---|---|
| … | … |
| … | … |
Di seguito le dimostrazioni dei singoli casi:
Caso 1. $2$ coppie - $2$ posti
Considerando che, dopo ogni viaggio, la barca approda alla seconda riva, si avrà
-
Le due mogli passano dall'altra parte
Prima riva Seconda riva -
Una delle mogli ritorna, mentre i due mariti passano
Prima riva Seconda riva -
La moglie sulla seconda riva ritorna a prendere l'altra moglie
Prima riva Seconda riva
Caso 2. $3$ coppie - $2$ posti (Lucas)
Considerando che, dopo ogni viaggio, la barca approda alla seconda riva, si avrà
-
Due mogli passano dall'altra parte
-
Una delle mogli torna e porta sull'altra riva la terza
-
Una delle mogli ritorna, resta con suo marito, mentre gli altri due mariti passano
-
Un marito torna assieme alla moglie, che lascia a riva mentre porta dall'altra parte l'altro marito
-
La moglie sulla seconda riva ritorna a prendere una delle altre due
-
Una moglie (o il marito) ritorna a prendere l'ultima
$\fbox{4 coppie - 2 posti}$ (Lucas)
Ecco come si può dimostrare l'impossibilità di questo problema quando non è possibile far passare più di due persone alla volta.
Prima di tutto, va osservato che, tra un passaggio e l'altro, il numero delle persone passate, se aumenta, non può che aumentare di un'unità.
Di conseguenza, possiamo supporre che si facciano passare due, poi tre, poi quattro persone assecondando le condizioni imposte, e vediamo se queste possono essere verificate anche quando sono passate cinque persone.
Queste cinque persone non possono trovarsi che in una delle quattro condizioni seguenti:
| $\text{Prima riva}$ | $\text{Seconda riva}$ |
|---|---|
| $C$ $B$ $A$ | $\bullet$ $\bullet$ $\bullet$ |
| $c$ $b$ $a$ | $\bullet$ $\bullet$ $\bullet$ |
I due primi casi sono impossibili, perchè contraddicono l'enunciazione del problema, dato che sulla seconda riva, le donne sono in maggiornaza e, di conseguenza, almeno una si trova in compagnia di un altro uomo senza il marito;
allo stesso modo è impossibile il terzo caso, perchè questa volta le donne si trovano in maggioranza sulla prima riva.
Quanto all'ultimo caso, può aver luogo solo se nell'ultimo attraversamento sono stati portati due uomini oppure un uomo e una donna.
In realtà, non è possibile che siano stati portati due uomini, poichè sull'altra riva sarebbero rimasti due uomini e tre donne, con una situazione analoga a quella del secondo caso;
nè è possibile che siano stati trasportati un uomo e una donna, perchè sulla prima riva sarebbero rimasti un uomo e quattro donne, situazione quindi analoga al primo caso.
Dunque, seguendo le condizioni poste dall'enunciato del problema, non è possibile far transitare cinque persone.
$\fbox{n coppie - 2 posti}\qquad n \ge 5$
Possiamo utilizzare lo stesso ragionamento utilizzato da Lucas per il caso precedente (4 coppie - 2 posti).
Di conseguenza, possiamo supporre che si facciano passare due, poi tre, fin a $x$ persone assecondando le condizioni imposte, e vediamo se queste possono essere verificate anche quando sono passate $x+1$ persone.
Per la dimostrazione, consideriamo un $x \ge n$, e pari; ossia $x = n + 2k$, con $k = 1,2,3,\ldots,n$.
Dunque, queste $x+1$ persone possono trovarsi in una delle $n$ condizioni seguenti:
| $\text{Prima riva}$ | $\text{Seconda riva}$ |
|---|---|
| $C$ $B$ $A$ | $\bullet$ $\bullet$ $\bullet$ |
| $c$ $b$ $a$ | $\bullet$ $\bullet$ $\bullet$ |
Essendo $x$ pari, si ha che:
i primi $\frac{x}{2}$ casi sono impossibili, perchè contraddicono l'enunciazione del problema, dato che sulla seconda riva, le donne sono in maggiornaza e, di conseguenza, almeno una si trova in compagnia di un altro uomo senza il marito;
allo stesso modo sono impossibili i successivi $\frac{x}{2}-1$ casi, perchè questa volta le donne si trovano in maggioranza sulla prima riva.
Quanto all'ultimo caso, può aver luogo solo se nell'ultimo attraversamento sono stati portati due uomini oppure un uomo e una donna.
In realtà, non è possibile che siano stati portati due uomini, poichè sull'altra riva sarebbero rimasti $2$ uomini e $x-1$ donne, con una situazione analoga a quella del secondo caso;
nè è possibile che siano stati trasportati un uomo e una donna, perchè sulla prima riva sarebbero rimasti $1$ uomo e $x$ donne, situazione quindi analoga al primo caso.
Dunque, seguendo le condizioni poste dall'enunciato del problema, non è possibile far transitare $x+1$ persone, ed il problema è pertanto non risolvibile.
$\fbox{3 coppie - 3 posti}$
Considerando che, dopo ogni viaggio, la barca approda alla seconda riva, si avrà
-
Le tre mogli passano dall'altra parte
-
Una delle mogli ritorna, mentre i tre mariti passano
-
Una delle mogli sulla seconda riva ritorna a prendere l'utima moglie sulla prima riva
$\fbox{4 coppie - 3 posti}$ (Lucas - Labosne)
-
All'inizio passano tre donne
-
Una donna (o due) ritornano per portare sulla seconda riva la quarta
-
Una delle donne ritorna, resta con suo marito, mentre passano gli altri tre uomini
-
Uno dei mariti ritorna assieme alla moglie e porta sulla seconda riva l'ultimo marito
-
Infine, l'ultimo dei mariti torna a prendere sua moglie
$\fbox{5 coppie - 3 posti}$ (Lucas - Delannoy)
Considerando che, dopo ogni viaggio, la barca approda alla seconda riva, si avrà
-
Tre donne passano per prime
-
Una donna (o due) torna indietro e porta la quarta sulla seconda riva
-
Una delle donne ritorna, e tre mariti raggiungono le rispettive mogli
-
Una delle coppie ritorna, mentre passano gli altri tre mariti
-
Una delle mogli ritorna e porta altre due mogli sulla seconda riva
-
Una moglie (o il marito) ritorna a prendere l'ultima
$\fbox{n coppie - 3 posti} \quad n > 5$
Possiamo utilizzare lo stesso ragionamento utilizzato per il caso di ($\text{n coppie - 2 posti}, n \ge 5$).
In questo caso, però, va osservato che, tra un passaggio e l'altro, il numero delle persone passate, se aumenta, può aumentare sia di un'unità, che di due.
Di conseguenza, possiamo supporre che si facciano passare due, poi tre, fino a $n$ persone assecondando le condizioni imposte, e vediamo se queste possono essere verificate anche quando sono passate $n+1$, ed $n+2$ persone.
Supponiamo, per comodità, che $n$ sia pari.
Situazione con $n+1$ persone sulla seconda riva:
queste $n+1$ persone possono trovarsi in una delle $n$ condizioni seguenti:
i primi $\frac{n}{2}$ casi sono impossibili, perchè contraddicono l'enunciazione del problema, dato che sulla seconda riva, le donne sono in maggiornaza e, di conseguenza, almeno una si trova in compagnia di un altro uomo senza il marito;
allo stesso modo sono impossibili i successivi $\frac{n}{2}-1$ casi, perchè questa volta le donne si trovano in maggioranza sulla prima riva.
Quanto all'ultimo caso, può aver luogo solo se nell'ultimo attraversamento sono stati portati tre uomini oppure due uomini e una donna.
In realtà, non è possibile che siano stati portati tre uomini, poichè sull'altra riva sarebbero rimasti $3$ uomini e $n-1$ donne, ossia una o più donne senza il proprio marito;
nè è possibile che siano stati trasportati due uomini e una donna, perchè sulla prima riva sarebbero rimasti $2$ uomini e $n$ donne, situazione analoga alla precedente.
Dunque, seguendo le condizioni poste dall'enunciato del problema, non è possibile far transitare $n+1$ persone.
Tuttavia, sempre assecondando le condizioni imposte, potrebbe essere possibile passare direttamente, da $n$ persone ad $n+2$ persone; pertanto analizziamo anche la situazione con $n+2$ persone sulla seconda riva.
Situazione con $n+2$ persone sulla seconda riva:
queste $n+2$ persone possono trovarsi in una delle $n+1$ condizioni seguenti:
i primi $\frac{n}{2}$ casi sono impossibili, perchè contraddicono l'enunciazione del problema, dato che sulla seconda riva, le donne sono in maggiornaza e, di conseguenza, almeno una si trova in compagnia di un altro uomo senza il marito;
allo stesso modo sono impossibili gli ultimi $\frac{n}{2}-1$ casi, perchè questa volta le donne si trovano in maggioranza sulla prima riva.
L'ultimo caso, analogamente a quanto scritto per l'ultimo caso della situazione con $n+1$ persone sulla seconda riva, è impossibile.
Resta da dimostrare l'impossibilità del caso centrale, ossia il caso in cui si ha lo stesso numero di uomini e donne sulla seconda riva, ossia:
Questo caso, può aver luogo solo se nell'ultimo attraversamento sono stati portati tre uomini, tre donne oppure due uomini e una donna.
In realtà, non è possibile che siano stati portati tre uomini, poichè, in tal caso, sulla seconda riva sarebbero già presenti $\frac{n}{2}-2$ uomini e $\frac{n}{2}+1$ donne, ossia tre donne senza il proprio marito;
altresì non è possibile che siano stati trasportati due uomini e una donna, poichè, in tal caso, sulla seconda riva sarebbero già presenti $\frac{n}{2}-1$ uomini e $\frac{n}{2}$ donne, ossia una donna senza il proprio marito;
Infine non è possibile che siano state portate tre donne, poichè sull'altra riva sarebbero rimasti $\frac{n}{2}-1$ uomini e $\frac{n}{2}+2$ donne, ossia tre donne senza il proprio marito.
Dunque, seguendo le condizioni poste dall'enunciato del problema, non è possibile far transitare né $n+1$ persone, né $n+2$ persone; pertanto il problema non è risolvibile.
$\fbox{n coppie - x posti} \quad n\ge 5, x \ge 4 , x\text{ pari}, n \ge x$
Il ragionamento è il seguente:
si fanno passare $\frac{x}{2}$ coppie alla volta sulla seconda riva, mentre una coppia ritorna indietro per permettere l'attraversamento alle altre coppie. Ripetendo questa manovra, si verifica facilmente che le $n$ coppie possono attraversare il fiume in $\left\lceil\frac{n-1}{\frac{x}{2}-1}\right\rceil$ viaggi.
$\fbox{n coppie - x posti} \quad n \ge 5 , x \ge 4, x \text{ dispari}, n \ge x$
Passano $x$ mogli sulla seconda riva;
una delle mogli torna, resta con il marito, mentre altri $x$ mariti passano sulla seconda riva;
una coppia torna indietro, ed altre $\frac{x-1}{2}$ coppie raggiungono la seconda riva;
ripetendo questa manovra si fanno passare tutte le restanti coppie.
Calcoliamo, adesso, il numero di viaggi che vengono effettuati;
dopo $2$ viaggi abbiamo la seguente situazione
dopo di che una coppia torna indietro e si ottiene la seguente situazione
a questo punto abbiamo $n-x+2$ coppie che passano sulla seconda riva, $\frac{x-1}{2}$ alla volta; stando a quanto calcolato nel caso precedente, il numero di viaggi necessario per far passare $n-x+2$ coppie, $\frac{x-1}{2}$ alla volta, sarà pari a
Quindi le $n$ coppie possono attraversare il fiume in un totale di $2+\left\lceil\frac{n-x+1}{\left(\frac{x-1}{2}\right)-1}\right\rceil\qquad$ viaggi.
Fonti correlate
- http://www.base5forum.it/il-leopardo-la-capra-e-il-kassawi-9-attraversare-un-fiume-una-possibile-generalizzazione-t1434.html
- http://utenti.quipo.it/base5/logica/lupcacav2.htm
-
Il "De Viribus Quantitatis" è un'unica copia manoscritta di Luca Pacioli, realizzata tra il 1496 ed il 1508, contenuta nel codice 250 della Biblioteca Universitaria di Bologna ↩
-
"Giochi matematici alla corte di Carlomagno. Problemi per rendere acuta la mente dei giovani" - Alcuino da York. A cura di Raffaella Franci. Edizioni ETS, Pisa, 2005 ↩
-
Recreations mathematiques - Edouard Lucas. 1 Vol.(XXIV-254 p.). Blanchard, Paris, 1891 ↩