"Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Messaggio da **Admin** » mer gen 04, 2012 5:42 pm

Admin ha scritto:Dalla sezione "Il leopardo la capra ed il kassawi"

9. Attraversare un fiume: una possibile generalizzazione

Non poteva mancare un'indagine sul problema generale dell'attraversamento di un fiume. Non si sa mai: un giorno potremmo trovarci in 5000 ed è bene arrivare preparati.
Dunque, abbiamo:
- n coppie;
- una barca a x posti;
Possiamo farcela?
In quanti passaggi?

[Lucas, L'Arithmétique Amusante, 1895]

A suo tempo (circa 8 o 9 anni fa!) inviai a Gianfranco una possibile generalizzazione del problema.
La trovate nell'apposita sezione del portale di Base5, ossia: http://utenti.quipo.it/base5/logica/lupcacav.htm" target="_blank.
Bene, ultimamente mi sono appassionato nuovamente all'argomento, grazie all'appendice sul tema, presente nel libro "Giochi matematici alla corte di Carlomagno" a cura di Raffaella Franci.
Da quest'ultima ho appreso che Lucas aveva trattato in modo completo il problema, nelle sue "Ricreazioni Matematiche" (1894).
Consultando il libro di Lucas mi sono accorto che la mia dimostrazione è sbagliata.
Il problema sono le situazioni in cui, per un breve lasso di tempo (ad esempio avvicendamento tra barca e sponda), una moglie viene a trovarsi lontana dal proprio marito e in compagnia di altri uomini.
Io avevo a suo tempo considerato ambigue e comunque trascurabili queste situazioni;
in realtà esse non sono affatto ambigue e, semplicemente, non soddisfano la condizione iniziale della "gelosia".

Pertanto, riporto nel post seguente la corretta generalizzazione di Lucas, con l'aggiunta da parte mia delle dimostrazioni dei casi non esplicitati, e di quelli che Lucas rimanda al lettore. In blu le mie dimostrazioni.

Messaggio da **Admin** » mer gen 04, 2012 6:14 pm

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 $\qquad n\/\ge\/5$
$4$ coppie - $3$ posti
$5$ coppie - $3$ posti
$n$ coppie - $3$ posti $\qquad n\/>\/5$
$n$ coppie - $4$ posti $\qquad n\/\ge\/5$
$n$ coppie - $x$ posti $\qquad n\/\ge\/5$ , $\qquad x\/\ge\/4$ , $x$ pari, $\qquad n\/\ge\/x$
$n$ coppie - $x$ posti $\qquad n\/\ge\/5$ , $\qquad x\/\ge\/4$ , $x$ dispari, $\qquad n\/\ge\/x$

Quelli in nero sono stati dimostrati da Lucas; quelli in blu proverò a dimostrarli io.

Indichiamo con $A,\/B,\/C,\/\dots$ gli $n$ mariti, e con $a,\/b,\/c,\/\dots$ le $n$ mogli.
La situazione iniziale è la seguente:

$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/C & \qquad B & \qquad A & \hspace{45}\bullet & \qquad\bullet & \qquad\bullet \\ \/c & \qquad b & \qquad a & \hspace{45}\bullet & \qquad\bullet & \qquad\bullet \\ \end{array}$

Di seguito le dimostrazioni dei singoli casi:

Messaggio da **Admin** » gio gen 05, 2012 11:57 am

$\fbox{\text{2 coppie - 2 posti}}$

Considerando che, dopo ogni viaggio, la barca approda alla seconda riva, si avrà

Le due mogli passano dall'altra parte
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/\qquad B & \qquad A & \hspace{75}\Large{\bullet} & \qquad\Large{\bullet} \\ \/\qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{75} b & \qquad a \\ \end{array}$
Una delle mogli ritorna, mentre i due mariti passano
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/\qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{75} B & \qquad A \\ \/\qquad b & \qquad\Large{\bullet} & \hspace{75}\Large{\bullet} & \qquad a \\ \end{array}$
La moglie sulla seconda riva ritorna a prendere l'altra moglie
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/\qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{75} B & \qquad A \\ \/\qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{75} b & \qquad a \\ \end{array}$

Messaggio da **Admin** » gio gen 05, 2012 12:03 pm

$\fbox{\text{3 coppie - 2 posti}}$ (Lucas)

Considerando che, dopo ogni viaggio, la barca approda alla seconda riva, si avrà

Due mogli passano dall'altra parte
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\ \/c & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad b & \qquad a \\ \end{array}$
Una delle mogli torna e porta sull'altra riva la terza
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\ \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} c & \qquad b & \qquad a \\ \end{array}$
Una delle mogli ritorna, resta con suo marito, mentre gli altri due mariti passano
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/ C & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad B & \qquad A \\ \/ c & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} \Large{\bullet} & \qquad b & \qquad a \\ \end{array}$
Un marito torna assieme alla moglie, che lascia a riva mentre porta dall'altra parte l'altro marito
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} C & \qquad B & \qquad A \\ \/ c & \qquad b & \qquad\Large{\bullet} & \hspace{45} \Large{\bullet} & \qquad\Large{\bullet} & \qquad a \\ \end{array}$
La moglie sullas seconda riva ritorna a prendere una delle altre due
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} C & \qquad B & \qquad A \\ \/ c & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} \Large{\bullet} & \qquad b & \qquad a \\ \end{array}$
Una moglie (o il marito) ritorna a prendere l'ultima
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/ \Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} C & \qquad B & \qquad A \\ \/ \Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} c & \qquad b & \qquad a \\ \end{array}$

Messaggio da **Admin** » gio gen 05, 2012 4:47 pm

$\fbox{\text{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:

$\begin{array}{cccc} \text{4 donne} & \hspace{45}\text{3 donne} & \hspace{45}\text{2 donne} & \hspace{45}\text{1 donna}\\ \text{1 uomo} & \hspace{45}\text{2 uomini} & \hspace{45}\text{3 uomini} & \hspace{45}\text{4 uomini} \end{array}$

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.

Messaggio da **Admin** » gio gen 05, 2012 4:55 pm

$\fbox{n\text{ coppie - 2 posti}\qquad\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,...,n$ .

Dunque, queste $x+1$ persone possono trovarsi in una delle $n$ condizioni seguenti:

$\begin{array}{cccc}<br />\text{x donne} & \hspace{45}\text{x-1 donne} & \hspace{45}\text{x-2 donne} & \hspace{45}\cdots & \hspace{45}\text{3 donna}& \hspace{45}\text{2 donna}& \hspace{45}\text{1 donna}\\<br />\text{1 uomo} & \hspace{45}\text{2 uomini} & \hspace{45}\text{3 uomini} & \hspace{45}\cdots & \hspace{45}\text{x-2 uomini} & \hspace{45}\text{x-1 uomini} & \hspace{45}\text{x uomini}\end{array}$

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.

Messaggio da **Admin** » gio gen 05, 2012 4:57 pm

$\fbox{\text{4 coppie - 3 posti}}$ (Lucas - Labosne)

All'inizio passano tre donne
$\text{Prima\/riva \hspace{70}Seconda\/riva}\\ \begin{array}{cccc} \/ D & \qquad C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\ \/ d & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} \Large{\bullet} & \qquad c & \qquad b & \qquad a \\ \end{array}$
Una donna (o due) ritornano per portare sulla seconda riva la quarta
$\text{Prima\/riva \hspace{70}Seconda\/riva}\\ \begin{array}{cccc} \/ D & \qquad C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\ \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} d & \qquad c & \qquad b & \qquad a \\ \end{array}$
Una delle donne ritorna, resta con suo marito, mentre passano gli altri tre uomini
$\text{Prima\/riva \hspace{70}Seconda\/riva}\\ \begin{array}{cccc} \/ D & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad C & \qquad B & \qquad A \\ \/ d & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad c & \qquad b & \qquad a \\ \end{array}$
Uno dei mariti ritorna assieme alla moglie e porta sulla seconda riva l'ultimo marito
$\text{Prima\/riva \hspace{70}Seconda\/riva}\\ \begin{array}{cccc} \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} D & \qquad C & \qquad B & \qquad A \\ \/ d & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad c & \qquad b & \qquad a \\ \end{array}$
Infine, l'ultimo dei mariti torna a prendere sua moglie
$\text{Prima\/riva \hspace{70}Seconda\/riva}\\ \begin{array}{cccc} \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} D & \qquad C & \qquad B & \qquad A \\ \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} d & \qquad c & \qquad b & \qquad a \\ \end{array}$

Messaggio da **Admin** » gio gen 05, 2012 4:57 pm

$\fbox{\text{5 coppie - 3 posti}}$ (Lucas - Delannoy)

Considerando che, dopo ogni viaggio, la barca approda alla seconda riva, si avrà

Tre donne passano per prime
$\text{Prima\/riva \hspace{100}Seconda\/riva}\\ \begin{array}{cccc} \/E & \qquad D & \qquad C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\ \/e & \qquad d & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad c & \qquad b & \qquad a \\ \end{array}$
Una donna (o due) torna indietro e porta la quarta sulla seconda riva
$\text{Prima\/riva \hspace{100}Seconda\/riva}\\ \begin{array}{cccc} \/E & \qquad D & \qquad C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\ \/e & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad d & \qquad c & \qquad b & \qquad a \\ \end{array}$
Una delle donne ritorna, e tre mariti raggiungono le rispettive mogli
$\text{Prima\/riva \hspace{100}Seconda\/riva}\\ \begin{array}{cccc} \/E & \qquad D & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad C & \qquad B & \qquad A \\ \/e & \qquad d & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad c & \qquad b & \qquad a \\ \end{array}$
Una delle coppie ritorna, mentre passano gli altri tre mariti
$\text{Prima\/riva \hspace{100}Seconda\/riva}\\ \begin{array}{cccc} \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} E & \qquad D & \qquad C & \qquad B & \qquad A \\ \/e & \qquad d & \qquad c & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad b & \qquad a \\ \end{array}$
Una delle mogli ritorna e porta altre due mogli sulla seconda riva
$\text{Prima\/riva \hspace{100}Seconda\/riva}\\ \begin{array}{cccc} \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} E & \qquad D & \qquad C & \qquad B & \qquad A \\ \/e & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad d & \qquad c & \qquad b & \qquad a \\ \end{array}$
Una moglie (o il marito) ritorna a prendere l'ultima
$\text{Prima\/riva \hspace{100}Seconda\/riva}\\ \begin{array}{cccc} \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} E & \qquad D & \qquad C & \qquad B & \qquad A \\ \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} e & \qquad d & \qquad c & \qquad b & \qquad a \\ \end{array}$

Messaggio da **Admin** » gio gen 05, 2012 4:58 pm

$\fbox{n\text{ coppie - 3 posti}\qquad\qquad n\/>\/5}$

Possiamo utilizzare lo stesso ragionamento utilizzato per il caso di ( $n\text{ coppie - 2 posti}\qquad\qquad 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:

$\begin{array}{cccc}\text{n donne} & \hspace{45}\text{n-1 donne} & \hspace{45}\text{n-2 donne} & \hspace{45}\cdots & \hspace{45}\text{3 donna}& \hspace{45}\text{2 donna}& \hspace{45}\text{1 donna}\\\text{1 uomo} & \hspace{45}\text{2 uomini} & \hspace{45}\text{3 uomini} & \hspace{45}\cdots & \hspace{45}\text{n-2 uomini} & \hspace{45}\text{n-1 uomini} & \hspace{45}\text{n uomini}\end{array}$

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:

$\begin{array}{cccc}\text{n+1 donne} & \hspace{45}\text{n donne} & \hspace{45}\text{n-1 donne} & \hspace{45}\cdots & \hspace{45}\text{3 donna}& \hspace{45}\text{2 donna}& \hspace{45}\text{1 donna}\\\text{1 uomo} & \hspace{45}\text{2 uomini} & \hspace{45}\text{3 uomini} & \hspace{45}\cdots & \hspace{45}\text{n-1 uomini} & \hspace{45}\text{n uomini} & \hspace{45}\text{n+1 uomini}\end{array}$

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:

$\begin{array}{cccc}\large{\text{\frac{n}{2}+1 donne} \\ \text{\frac{n}{2}+1 uomini}} \end{array}$

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.

Messaggio da **Admin** » gio gen 05, 2012 4:59 pm

$\fbox{n\text{ coppie - }x\text{ posti}\qquad\qquad n\/\ge\/5\/,\/x\/\ge\/4\/,\/x\text{ pari}\/,\/n\/\ge\/x}$

Il ragionamento è il seguente:

si fanno passare $\large\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 $\large n$ coppie possono attraversare il fiume in $\Large{\left\lceil\frac{n-1}{\frac{x}{2}-1}\right\rceil}$ viaggi.

Messaggio da **Admin** » gio gen 05, 2012 5:01 pm

$\fbox{n\text{ coppie - }x\text{ posti}\qquad\qquad n\/\ge\/5\/,\/x\/\ge\/4\/,\/x\text{ dispari}\/,\/n\/\ge\/x}$

Passano $\large x$ mogli sulla seconda riva;
una delle mogli torna, resta con il marito, mentre altri $\large x$ mariti passano sulla seconda riva;
una coppia torna indietro, ed altre $\large\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

$\text{Prima\/riva \hspace{100}Seconda\/riva}\\ n-x+1\;\text{coppie}\hspace{100} x-1\;\text{coppie}$

dopo di che una coppia torna indietro e si ottiene la seguente situazione

$\text{Prima\/riva \hspace{100}Seconda\/riva}\\ n-x+2\;\text{coppie}\hspace{100} x-2\;\text{coppie}$

a questo punto abbiamo $\large n-x+2$ coppie che passano sulla seconda riva, $\large\frac{x-1}{2}$ alla volta;
stando a quanto calcolato nel caso precedente, il numero di viaggi necessario per far passare $\large n-x+2$ coppie, $\large\frac{x-1}{2}$ alla volta, sarà pari a

$\large\left\lceil \frac{n-x+2-1}{\left(\frac{x-1}{2}\right)-1}\right\rceil \qquad\Rightarrow\qquad \left\lceil \frac{n-x+1}{\left(\frac{x-1}{2}\right)-1}\right\rceil$

Quindi le $n$ coppie possono attraversare il fiume in un totale di $\qquad\large 2+\left\lceil\frac{n-x+1}{\left(\frac{x-1}{2}\right)-1}\right\rceil\qquad$ viaggi.

Messaggio da **Admin** » dom apr 01, 2012 7:28 pm

$\fbox{\text{3 coppie - 3 posti}}$

Considerando che, dopo ogni viaggio, la barca approda alla seconda riva, si avrà

Le tre mogli passano dall'altra parte
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\ \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}c & \qquad b & \qquad a \\ \end{array}$
Una delle mogli ritorna, mentre i tre mariti passano
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{50} C & B & A \\ \/c & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad b & \qquad a \\ \end{array}$
Una delle mogli sulla seconda riva ritorna a prendere l'utima moglie sulla prima riva
$\text{Prima\/riva \hspace{20}Seconda\/riva}\\ \begin{array}{cccc} \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} C & B & A \\ \/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} c & \qquad b & \qquad a \\ \end{array}$

"Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

"Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Re: "Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Re: "Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Re: "Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Re: "Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Re: "Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Re: "Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Re: "Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Re: "Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Re: "Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Re: "Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione

Re: "Il leopardo, la capra e il kassawi" - 9. Attraversare un fiume: una possibile generalizzazione