[BASE Cinque - Appunti di Matematica ricreativa]

Mariti gelosi che devono attraversare un fiume con le loro mogli

Soluzione completa di un problema di attraversamento

Introduzione

Ringrazio innanzitutto Pietro Vitelli per questa soluzione dettagliata di un problema generale di attraversamento di un fiume.

Nella pagina Il leopardo, la capra e il kassawi trovate alcuni casi particolari che vi permetteranno di entrare nell'argomento.

Qui di seguito riporto un semplice esempio.

I tre mariti gelosi
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?

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 marito-moglie;
- una barca a x posti;
Possiamo farcela?
In quanti passaggi?
[Lucas, L'Arithmétique Amusante, 1895]

La soluzione generale

di Pietro Vitelli

Ultimamente mi sono appassionato 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).
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 grassetto le mie dimostrazioni.

Seguendo l'approccio di Lucas, possiamo generalizzare il problema mediante elencazione di tutti i casi possibili con relativa dimostrazione.

Indichiamo con Descrizione: Descrizione: Descrizione: n il numero di coppie (marito - moglie) da traghettare, e con Descrizione: Descrizione: Descrizione: x il numero di posti sulla barca.

Ho individuato 10 casi possibili, che ricoprono tutte le casistiche, e sono:

Descrizione: Descrizione: Descrizione: 2 coppie - Descrizione: Descrizione: Descrizione: 2 posti

Descrizione: Descrizione: Descrizione: 3 coppie - Descrizione: Descrizione: Descrizione: 2 posti

Descrizione: Descrizione: Descrizione: 4 coppie - Descrizione: Descrizione: Descrizione: 2 posti

Descrizione: Descrizione: Descrizione: n coppie - Descrizione: Descrizione: Descrizione: 2 posti Descrizione: Descrizione: Descrizione: \qquad n\/\ge\/5

Descrizione: Descrizione: Descrizione: 4 coppie - Descrizione: Descrizione: Descrizione: 3 posti

Descrizione: Descrizione: Descrizione: 5 coppie - Descrizione: Descrizione: Descrizione: 3 posti

Descrizione: Descrizione: Descrizione: n coppie - Descrizione: Descrizione: Descrizione: 3 posti Descrizione: Descrizione: Descrizione: \qquad n\/>\/5

Descrizione: Descrizione: Descrizione: n coppie - Descrizione: Descrizione: Descrizione: 4 posti Descrizione: Descrizione: Descrizione: \qquad n\/\ge\/5

Descrizione: Descrizione: Descrizione: n coppie - Descrizione: Descrizione: Descrizione: x posti Descrizione: Descrizione: Descrizione: \qquad n\/\ge\/5,Descrizione: Descrizione: Descrizione: \qquad x\/\ge\/4, Descrizione: Descrizione: Descrizione: x pari,Descrizione: Descrizione: Descrizione: \qquad n\/\ge\/x

Descrizione: Descrizione: Descrizione: n coppie - Descrizione: Descrizione: Descrizione: x posti Descrizione: Descrizione: Descrizione: \qquad n\/\ge\/5,Descrizione: Descrizione: Descrizione: \qquad x\/\ge\/4, Descrizione: Descrizione: Descrizione: x dispari,Descrizione: Descrizione: Descrizione: \qquad n\/\ge\/x


Quelli in testo normale sono stati dimostrati da Lucas; quelli in grassetto proverò a dimostrarli io.

Indichiamo con Descrizione: Descrizione: Descrizione: A,\/B,\/C,\/\dotsgli Descrizione: Descrizione: Descrizione: n mariti, e con Descrizione: Descrizione: Descrizione: a,\/b,\/c,\/\dotsle Descrizione: Descrizione: Descrizione: n mogli.
La situazione iniziale è la seguente:

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

Di seguito le dimostrazioni dei singoli casi.


2 coppie - 2 posti

Descrizione: Descrizione: Descrizione: \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
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\qquad B & \qquad A & \hspace{75}\Large{\bullet} & \qquad\Large{\bullet} \\<br />\/\qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{75} b & \qquad a \\<br />\end{array}

Una delle mogli ritorna, mentre i due mariti passano
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{75} B & \qquad A \\<br />\/\qquad b & \qquad\Large{\bullet} & \hspace{75}\Large{\bullet} & \qquad a \\<br />\end{array}

La moglie sulla seconda riva ritorna a prendere l'altra moglie
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{75} B & \qquad A \\<br />\/\qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{75} b & \qquad a \\<br />\end{array}


3 coppie - 2 posti

Descrizione: Descrizione: Descrizione: \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
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\<br />\/c & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad b & \qquad a \\<br />\end{array}

Una delle mogli torna e porta sull'altra riva la terza
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\<br />\/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} c & \qquad b & \qquad a \\<br />\end{array}

Una delle mogli ritorna, resta con suo marito, mentre gli altri due mariti passano
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/ C & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad B & \qquad A \\<br />\/ c & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} \Large{\bullet} & \qquad b & \qquad a \\<br />\end{array}

Un marito torna assieme alla moglie, che lascia a riva mentre porta dall'altra parte l'altro marito
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad B & \qquad A \\<br />\/ c & \qquad b & \qquad\Large{\bullet} & \hspace{45} \Large{\bullet} & \qquad\Large{\bullet} & \qquad a \\<br />\end{array}

La moglie che ha appena attraversato il fiume ritorna a prendere una delle altre due
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad B & \qquad A \\<br />\/ c & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} \Large{\bullet} & \qquad b & \qquad a \\<br />\end{array}

Una moglie (o il marito) ritorna a prendere l'ultima
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/ \Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} C & \qquad B & \qquad A \\<br />\/ \Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} c & \qquad b & \qquad a \\<br />\end{array}


4 coppie - 2 posti

Descrizione: Descrizione: Descrizione: \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:

Descrizione: Descrizione: Descrizione: \begin{array}{cccc}<br />\text{4 donne} & \hspace{45}\text{3 donne} & \hspace{45}\text{2 donne} & \hspace{45}\text{1 donna}\\<br />\text{1 uomo} & \hspace{45}\text{2 uomini} & \hspace{45}\text{3 uomini} & \hspace{45}\text{4 uomini}<br />\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.


n coppie - 2 posti

Descrizione: Descrizione: Descrizione: \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 Descrizione: Descrizione: Descrizione: x persone assecondando le condizioni imposte, e vediamo se queste possono essere verificate anche quando sono passate Descrizione: Descrizione: Descrizione: x+1 persone.
Per la dimostrazione, consideriamo un Descrizione: Descrizione: Descrizione: x\/\ge\/n, e pari; ossia Descrizione: Descrizione: Descrizione: x\/=\/n\/+\/2k, con Descrizione: Descrizione: Descrizione: k\/=\/1,2,3,...,n.

Dunque, queste Descrizione: Descrizione: Descrizione: x+1 persone possono trovarsi in una delle Descrizione: Descrizione: Descrizione: ncondizioni seguenti:

Descrizione: Descrizione: Descrizione: \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 Descrizione: Descrizione: Descrizione: x pari, si ha che:
i primi Descrizione: Descrizione: Descrizione: \frac{x}{2} casi sono impossibili, perchè contraddicono l'enunciazione del problema, dato che sulla seconda riva, le donne sono in maggioranza e, di conseguenza, almeno una si trova in compagnia di un altro uomo senza il marito;
allo stesso modo sono impossibili i successivi Descrizione: Descrizione: Descrizione: \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 Descrizione: Descrizione: Descrizione: 2 uomini e Descrizione: Descrizione: Descrizione: 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 Descrizione: Descrizione: Descrizione: 1uomo e Descrizione: Descrizione: Descrizione: xdonne, situazione quindi analoga al primo caso.
Dunque, seguendo le condizioni poste dall'enunciato del problema, non è possibile far transitare Descrizione: Descrizione: Descrizione: x+1 persone, ed il problema è pertanto non risolvibile.


4 coppie - 3 posti

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

All'inizio passano tre donne
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{70}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/ D & \qquad C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\<br />\/ d & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} \Large{\bullet} & \qquad c & \qquad b & \qquad a \\<br />\end{array}

Una donna (o due) ritornano per portare sulla seconda riva la quarta
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{70}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/ D & \qquad C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\<br />\/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} d & \qquad c & \qquad b & \qquad a \\<br />\end{array}

Una delle donne ritorna, resta con suo marito, mentre passano gli altri tre uomini
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{70}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/ D & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad C & \qquad B & \qquad A \\<br />\/ d & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad c & \qquad b & \qquad a \\<br />\end{array}

Uno dei mariti ritorna assieme alla moglie e porta sulla seconda riva l'ultimo marito
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{70}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} D & \qquad C & \qquad B & \qquad A \\<br />\/ d & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad c & \qquad b & \qquad a \\<br />\end{array}

Infine, l'ultimo dei mariti torna a prendere sua moglie
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{70}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} D & \qquad C & \qquad B & \qquad A \\<br />\/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} d & \qquad c & \qquad b & \qquad a \\<br />\end{array}


5 coppie - 3 posti

Descrizione: Descrizione: Descrizione: \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
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{100}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/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} \\<br />\/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 \\<br />\end{array}

Una donna (o due) torna indietro e porta la quarta sulla seconda riva
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{100}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/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} \\<br />\/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 \\<br />\end{array}

Una delle donne ritorna, e tre mariti raggiungono le rispettive mogli
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{100}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/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 \\<br />\/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 \\<br />\end{array}

Una delle coppie ritorna, mentre passano gli altri tre mariti
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{100}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\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 \\<br />\/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 \\<br />\end{array}

Una delle mogli ritorna e porta altre due mogli sulla seconda riva
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{100}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\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 \\<br />\/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 \\<br />\end{array}

Una moglie (o il marito) ritorna a prendere l'ultima
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{100}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\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 \\<br />\/\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 \\<br />\end{array}


n coppie - 3 posti

Descrizione: Descrizione: Descrizione: \fbox{n\text{ coppie - 3 posti}\qquad\qquad n\/>\/5}
Possiamo utilizzare lo stesso ragionamento utilizzato per il caso di (Descrizione: Descrizione: Descrizione: 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 Descrizione: Descrizione: Descrizione: npersone assecondando le condizioni imposte, e vediamo se queste possono essere verificate anche quando sono passate Descrizione: Descrizione: Descrizione: n+1, ed Descrizione: Descrizione: Descrizione: n+2 persone.

Supponiamo, per comodità, che Descrizione: Descrizione: Descrizione: n sia pari.

Situazione con Descrizione: Descrizione: Descrizione: n+1 persone sulla seconda riva:

queste Descrizione: Descrizione: Descrizione: n+1 persone possono trovarsi in una delle Descrizione: Descrizione: Descrizione: n condizioni seguenti:

Descrizione: Descrizione: Descrizione: \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 Descrizione: Descrizione: Descrizione: \frac{n}{2} casi sono impossibili, perchè contraddicono l'enunciazione del problema, dato che sulla seconda riva, le donne sono in maggioranza e, di conseguenza, almeno una si trova in compagnia di un altro uomo senza il marito;
allo stesso modo sono impossibili i successivi Descrizione: Descrizione: Descrizione: \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 Descrizione: Descrizione: Descrizione: 3 uomini e Descrizione: Descrizione: Descrizione: 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 Descrizione: Descrizione: Descrizione: 2 uomini e Descrizione: Descrizione: Descrizione: n donne, situazione analoga alla precedente.
Dunque, seguendo le condizioni poste dall'enunciato del problema, non è possibile far transitare Descrizione: Descrizione: Descrizione: n+1 persone.

Tuttavia, sempre assecondando le condizioni imposte, potrebbe essere possibile passare direttamente, da Descrizione: Descrizione: Descrizione: n persone ad Descrizione: Descrizione: Descrizione: n+2 persone; pertanto analizziamo anche la situazione con Descrizione: Descrizione: Descrizione: n+2 persone sulla seconda riva.

Situazione con Descrizione: Descrizione: Descrizione: n+2 persone sulla seconda riva:

queste Descrizione: Descrizione: Descrizione: n+2 persone possono trovarsi in una delle Descrizione: Descrizione: Descrizione: n+1 condizioni seguenti:

Descrizione: Descrizione: Descrizione: \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 Descrizione: Descrizione: Descrizione: \frac{n}{2} casi sono impossibili, perchè contraddicono l'enunciazione del problema, dato che sulla seconda riva, le donne sono in maggioranza e, di conseguenza, almeno una si trova in compagnia di un altro uomo senza il marito;
allo stesso modo sono impossibili gli ultimi Descrizione: Descrizione: Descrizione: \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 Descrizione: Descrizione: Descrizione: 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:

Descrizione: Descrizione: Descrizione: \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 Descrizione: Descrizione: Descrizione: \frac{n}{2}-2 uomini e Descrizione: Descrizione: Descrizione: \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 Descrizione: Descrizione: Descrizione: \frac{n}{2}-1 uomini e Descrizione: Descrizione: Descrizione: \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 Descrizione: Descrizione: Descrizione: \frac{n}{2}-1 uomini e Descrizione: Descrizione: Descrizione: \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é Descrizione: Descrizione: Descrizione: n+1 persone, né Descrizione: Descrizione: Descrizione: n+2 persone; pertanto il problema non è risolvibile.


n coppie - x posti (prima parte)

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


n coppie - x posti (seconda parte)

Descrizione: Descrizione: Descrizione: \fbox{n\text{ coppie - }x\text{ posti}\qquad\qquad n\/\ge\/5\/,\/x\/\ge\/4\/,\/x\text{ dispari}\/,\/n\/\ge\/x}
Passano Descrizione: Descrizione: Descrizione: \large xmogli sulla seconda riva;
una delle mogli torna, resta con il marito, mentre altri Descrizione: Descrizione: Descrizione: \large x mariti passano sulla seconda riva;
una coppia torna indietro, ed altre Descrizione: Descrizione: Descrizione: \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 Descrizione: Descrizione: Descrizione: 2 viaggi abbiamo la seguente situazione

Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{100}Seconda\/riva}\\<br />n-x+1\;\text{coppie}\hspace{100} x-1\;\text{coppie}

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

Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{100}Seconda\/riva}\\<br />n-x+2\;\text{coppie}\hspace{100} x-2\;\text{coppie}

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

Descrizione: Descrizione: Descrizione: \large\left\lceil \frac{n-x+2-1}{\left(\frac{x-1}{2}\right)-1}\right\rceil<br />\qquad\Rightarrow\qquad \left\lceil \frac{n-x+1}{\left(\frac{x-1}{2}\right)-1}\right\rceil

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


3 coppie - 3 posti

Descrizione: Descrizione: Descrizione: \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
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/C & \qquad B & \qquad A & \hspace{45}\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} \\<br />\/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}c & \qquad b & \qquad a \\<br />\end{array}

Una delle mogli ritorna, mentre i tre mariti passano
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{50}  C & B & A \\<br />\/c & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}\Large{\bullet} & \qquad b & \qquad a \\<br />\end{array}

Una delle mogli sulla seconda riva ritorna a prendere l'ultima moglie sulla prima riva
Descrizione: Descrizione: Descrizione: \text{Prima\/riva  \hspace{20}Seconda\/riva}\\<br />\begin{array}{cccc}<br />\/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45}  C & B & A \\<br />\/\Large{\bullet} & \qquad\Large{\bullet} & \qquad\Large{\bullet} & \hspace{45} c & \qquad b & \qquad a \\<br />\end{array}


Data creazione: aprile 2012

Ultimo aggiornamento: aprile 2012

xhtml 1.0


Sito Web realizzato da Gianfranco Bo