Il leopardo, la capra e il kassawi

Se il titolo di questa pagina fosse stato "Il lupo, la capra e il cavolo", probabilmente qualcuno avrebbe pensato: "Questa la so già. E' vecchia!"
E si sarebbe perso una grande occasione.

A dire il vero, è vecchia, ma non tanto.
Le prime versioni conosciute, in occidente, risalgono ad Alcuino di York, vissuto nel 900 circa.

1. Il lupo, la capra e il cavolo (compare anche nei top-ten)
Un pastore deve attraversare un fiume portando sull'altra riva un lupo e una capra affamati e una cassa di cavoli.
Ha a disposizione una barca a remi con la quale può traghettare un solo oggetto o animale alla volta.
Ma, attenzione! Non può lasciare da soli:
- il lupo e la capra perchè il lupo si mangia la capra;
- la capra ed i cavoli perché la capra si mangia i cavoli.
Quanti viaggi deve fare per portare sull'altra riva il lupo, la capra e la cassa di cavoli?
(Alcuino di York, Propositio de lupo et capra et fasciculo cauli, 900)

Gli etnomatematici hanno scoperto che questo problema è noto anche in altre culture, ad esempio africane: Isole del Capo Verde, Camerun, Etiopia, Zanzibar, Liberia e Algeria.
Claudia Zaslavsky nel suo libro Africa Counts, Boston, 1973, dice che il problema del leopardo, della capra e delle foglie di kassawi (manioca) è popolare presso i bambini Kpelle, in Liberia.
Marcia Ascher in "A river-crossing problem in cultural perspective", 1990 e in Ethnomatematics, 1991, descrive alcune varianti africane di questo problema nelle quali l'uomo può trasportare due animali e/o oggetti nella barca.
In questo modo il problema è più facile e richiede solo tre attraversamenti del fiume.
In altre versioni si dice che l'uomo non può tenere sotto controllo gli animali che sono sulla barca. Anche in questo caso il problema può essere risolto con tre attraversamenti.
Nelle diverse varianti del problema possono comparire altri personaggi, come: la volpe, l'uccello e il mais; la tigre, la pecora e le foglie d'erba; lo sciacallo, la capra e il fieno; il ghepardo, l'uccello e il riso; il leopardo, la capra e le foglie.

2. Il leopardo, la capra, il topo e il grano
Un pastore deve attraversare un fiume portando sull'altra riva un leopardo, una capra, un topo e un sacco di mais.
Ha a disposizione una barca a remi con la quale può traghettare un solo oggetto o animale alla volta.
Ma, attenzione! Non può lasciare da soli:
- il leopardo e la capra perchè il leopardo mangia la capra;
- il leopardo e il topo perché il leopardo mangia il topo;
- il topo e il mais perché il topo mangia il mais;
- la capra ed il mais perché la capra si mangia il mais.
Quanti viaggi deve fare per portare sull'altra riva il leopardo, la capra, il topo e il mais?

Numerose varianti europee sono state elaborate da: Alcuin, Abbot Albert, Chuquet, Tartaglia, van Etten, Ozanam, Gori, Pacioli, Cardano, etc.
I personaggi sono mariti gelosi e le loro mogli, padroni e i loro servitori, missionari e cannibali, carcerati che tentano l'evasione.

Ciascuna versione è una piccola avventura che ci fa entrare nella storia quotidiana del periodo e dell'ambiente in cui è stata inventata.

3. 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?
(Pacioli, 1500. De 3 mariti et 3 mogli gelosi)

4. Le madri gelose
Il problema è simile a quello dei mariti gelosi.
Tre madri e tre figli devono attraversare un fiume. I bimbi non possono essere lasciati soli con le mamme degli altri.
(Liz Allen, Londra, 1991)

5. Tre padroni e tre servitori
Tre padroni e tre servitori devono attraversare un fiume su una barca che ne può trasportare al massimo due alla volta.
Ciascun padrone non sopporta i servitori degli altri due e se viene lasciato solo con uno qualunque dei due, in assenza del suo padrone, lo bastona.
"None of the the masters can endure the valets of the other two; so that if any one of them were left with any of the other two valets, in the absence of his master, he would infallibly cane him."
(Ozanam, 1725, citato da D. Singmaster)

6. Gli schiavi assassini
Se nel 1700 i padroni bastonano i servitori, nel 1800 c'è il pericolo che avvenga il contrario.
Il problema è simile a quello precedente con la differenza che i servitori, in realtà, sono furfanti che possono derubare o addirittura uccidere i loro padroni.
Da ciò la necessità, per i padroni, di essere sempre in maggioranza o in egual numero rispetto ai servitori.
(Jackson. Rational Amusement, 1821, Arithmetical Puzzles)

7. I quattro mariti gelosi
E' simile al problema 3, solo che in questo caso abbiamo 4 coppie.
La barca può trasportare al massimo 3 persone.
L'attraversamento del fiume richiede 9 viaggi.

Il problema a questo punto si complica e sorgono diverse domande, ad esempio:
- 4 coppie possono attraversare il fiume con una barca a 2 posti? (sembra di no)
- se in mezzo al fiume c'è un'isola in cui si può fare tappa, le 4 coppie possono attraversare il fiume con una barca a 2 posti? (sembra in 24 passaggi)
(Lucas, L'Arithmétique Amusante, 1895)

8. I cinque mariti gelosi
Sempre più difficile, ma a questo punto diventa noioso!?
Questa volta abbiamo 5 coppie.
La barca può trasportare al massimo 3 persone.
L'attraversamento del fiume richiede 11 passaggi.
(Lucas, L'Arithmétique Amusante, 1895)

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)

10. Traghettare il tesoro
Dudeney, nel 1898, ha cambiato il tema.
Abbiamo 3 uomini e 3 sacchi di monete d'oro.
La barca può trasportare due uomini oppure un uomo e un sacco.
La fiducia è scarsa nel gruppo e nessun uomo può essere lasciato da solo con più di un sacco altrimenti se la svigna con il bottino. (13 passaggi?)
(Dudeney, 1898, semplificato)

11. Tre leopardi e tre capre
Un traghettatore deve far attraversare un fiume a 3 leopardi e 3 capre.
La barca può trasportare l'uomo e altri due animali.
Il numero dei leopardi sulle due rive non deve mai superare quello delle capre.
(9 passaggi?)
(H. Parker, Ancient Ceylon, 1909)

12. E se le donne non sanno remare?
Siamo nel 1914 e i mariti gelosi hanno delle mogli che non sanno remare.
Per il resto il problema è simile al numero 3. (17 passaggi?)
(Loyd, Cyclopedia, 1914)

13. Tre missionari e tre cannibali
Tre missionari e tre cannibali devono attraversare un fiume con una barca che può trasportare al massimo 3 persone.
Naturalmente i missionari non devono mai trovarsi in minoranza rispetto ai cannibali. Altrimenti questi se li mangiano!
(Abraham, 1933)

14. Quando il peso è importante
Un padre, una madre, i loro due figli ed il cane devono attraversare un fiume su una barca che può trasportare al massimo un carico di 160 kg.
Il genitori assieme pesano 160 kg.
I due figli assieme pesano 80 kg.
Il cane pesa 12 kg.
Come si organizzano?
(Nathan Altshiller, 1961)

15. Strani pesi
Tre persone che pesano 1, 2, 3 unità di peso devono attraversare un fiume con una barca che può trasportare non più di 3 unità di peso.
Come si organizzano?
(Technology Education, Document Series No. 29, UNESCO, Paris, 1988)

16. I cinque erranti
Cinque persone numerate 1, 2, 3, 4, 5 errano per il mondo.
Ad un certo punto della loro vita si trovano davanti ad un fiume e devono attraversarlo con una barca che può portarne soltanto due alla volta.
Per strani motivi psicologici che qui non indagheremo, due persone con i numeri consecutivi non possono mai stare da soli né sulla barca né sulla riva del fiume.
Come fanno ad attraversare il corso d'acqua?
(Technology Education, Document Series No. 29, UNESCO, Paris, 1988)

17. Fuga da Alcatraz
Tre innocenti ingiustamente condannati a vent'anni di prigione decidono di evadere calandosi dalla finestra della loro cella, posta a molti metri di altezza.
Il ciccione pesa 195 kg.
Il suo degno compare pesa 105 kg.
Il più magro pesa 90 kg.
Essi dispongono inoltre di un blocco di cemento del peso di 75 kg.
Per fuggire devono utilizzare una corda che scorre su una puleggia. Ai due capi della corda sono fissate due robuste ceste in ciascuna delle quali può stare un uomo o il blocco di cemento.
Praticamente devono calarsi in varie fasi facendosi da contrappeso l'uno con l'altro ed eventualmente con il blocco di cemento.
La differenza dei pesi nelle due ceste non deve superare i 15 kg, altrimenti la discesa è troppo rapida.
(Lemon, 1890, Lewis Carroll, 1899)

Risposte & riflessioni

1. Il lupo, la capra e il cavolo
di Alan Viezzoli
Ovviamente la soluzione è banale. Il contadino porta la capra, torna indietro, prende il lupo, riporta indietro la capra, prende il cavolo, torna indietro e prende la capra. 7 passaggi.

2. Il leopardo, la capra, il topo e il mais
di Pietro Vitelli
La traccia, devo dire, può far sorgere dubbi;
in particolare laddove dice:

"Ha a disposizione una barca a remi con la quale può traghettare un solo oggetto o animale alla volta."

Si deve intendere per forza che può portare un animale ed il mais contemporaneamente; anche perchè se così non fosse dovrebbe portare uno solo sulla barca (sia esso animale o oggetto), e ciò fa si che il problema non sia risolvibile date le condizioni in esso espresse.

Per cui procedo così:

Per comodità indico:

Leopardo = L
Capra = C
Topo = T
Mais = M

è evidente che il pastore sta sempre sulla barca.

1° viaggio)

Il pastore carica sulla barca L ed M;

SITUAZIONE
1° sponda: C,T (Tutto OK)
sulla barca: L,M (Tutto OK)
2° sponda: Nessuno (Tutto OK)

poi scarica sull'altra sponda L e M e ritorna al punto di partenza;

SITUAZIONE
1° sponda: C,T (Tutto OK)
sulla barca: Nessuno (Tutto OK)
2° sponda: L,M (Tutto OK)

2° viaggio)

Il pastore carica sulla barca C;

SITUAZIONE
1° sponda: T (Tutto OK)
sulla barca: C (Tutto OK)
2° sponda: L,M (Tutto OK)

poi scarica sull'altra sponda C e ricarica L ed M (facendo attenzione a non farli scontrare!!!);

SITUAZIONE
1° sponda: T (Tutto OK)
sulla barca: L,M (Tutto OK)
2° sponda: C (Tutto OK)

3° viaggio)

A questo punto scende L ed M e carica T (facendo attenzione a non farli scontrare!!!);

SITUAZIONE
1° sponda: L,M (Tutto OK)
sulla barca: T (Tutto OK)
2° sponda: C (Tutto OK)

giunto sull'altra sponda scarica T e ritorna al punto di partenza;

SITUAZIONE
1° sponda: L,M (Tutto OK)
sulla barca: Nessuno (Tutto OK)
2° sponda: C,T (Tutto OK)

4° viaggio)

Adesso carica L ed M e raggiunge l'altra sponda.

C'è un'altra soluzione, che comunque è uguale a questa:
al posto della capra nel 2° viaggio, si prende il topo.

3. I tre mariti gelosi
Chiamiamo A, B, C i tre mariti e a, b, c le loro rispettive mogli. Indichiamo la barca con un aterisco *.
La soluzione fornita da Pietro Vitelli può allora essere rappresentata così.

di Pietro Vitelli
Innanzitutto, osserviamo che il numero minimo di viaggi che bisogna fare è 5 (per viaggio si intende andata e ritorno);

infatti:

1° viaggio) salgono in due sulla barca: uno scende sull'altra sponda e l'altro ritorna;
2° viaggio) sale un altro, così sono di nuovo in due sulla barca: uno scende sull'altra sponda (e sono 2) e l'altro ritorna;
3° viaggio) sale un altro, così sono di nuovo in due sulla barca: uno scende sull'altra sponda (e sono 3) e l'altro ritorna;
4° viaggio) sale un altro, così sono di nuovo in due sulla barca: uno scende sull'altra sponda (e sono 4) e l'altro ritorna;
5° viaggio) sale un altro, così sono di nuovo in due sulla barca: scendono entrambi sull'altra sponda (sono 6).

Ora vediamo in che modo devono essere fatti:

indichiamo Mariti e mogli nel seguente modo:

Marito1 - Moglie1
Marito2 - Moglie2
Marito3 - Moglie3

1° viaggio)
salgono sulla barca Marito1 e Moglie1;sull'altra sponda scende Marito1;
Moglie1 ritorna al punto di partenza;

2° viaggio)
sale sulla barca Moglie2;

SITUAZIONE
1° sponda: Marito2,Marito3,Moglie3 (tutto OK)
sulla barca: Moglie1,Moglie2 (tutto OK)
2° sponda: Marito1 (tutto OK)

sull'altra sponda scende Moglie1;

SITUAZIONE
1° sponda: Marito2,Marito3,Moglie3 (tutto OK)
sulla barca: Moglie2 (tutto OK)
2° sponda: Marito1,Moglie1 (tutto OK)

Moglie2 ritorna al punto di partenza;

3° viaggio)
sale sulla barca Marito2;

SITUAZIONE
1° sponda: Marito3,Moglie3 (tutto OK)
sulla barca: Marito2,Moglie2 (tutto OK)
2° sponda: Marito1,Moglie1 (tutto OK)

sull'altra sponda scende Marito2;

SITUAZIONE
1° sponda: Marito3,Moglie3 (tutto OK)
sulla barca: Moglie2 (tutto OK)
2° sponda: Marito2,Marito1,Moglie1 (tutto OK)

Moglie2 ritorna al punto di partenza;

4° viaggio)
sale sulla barca Moglie3;

SITUAZIONE
1° sponda: Marito3 (tutto OK)
sulla barca: Moglie3,Moglie2 (tutto OK)
2° sponda: Marito2,Marito1,Moglie1 (tutto OK)

sull'altra sponda scende Moglie2;

SITUAZIONE
1° sponda: Marito3 (tutto OK)
sulla barca: Moglie3 (tutto OK)
2° sponda: Marito2,Moglie2,Marito1,Moglie1 (tutto OK)

Moglie3 ritorna al punto di partenza;

5° viaggio)
sale sulla barca Marito3;

SITUAZIONE
1° sponda: Nessuno
sulla barca: Marito3,Moglie3 (tutto OK)
2° sponda: Marito2,Moglie2,Marito1,Moglie1 (tutto OK)

sull'altra sponda scende prima Marito3 e poi Moglie3;

SITUAZIONE FINALE
1° sponda: Nessuno
sulla barca: Nessuno
2° sponda: Marito3,Moglie3,Marito2,Moglie2,Marito1,Moglie1 (tutto OK)

Attenzione!!!
Quando moglie1 ritorna al punto di partenza (vedi 1° viaggio), dato che Marito1 è rimasto sull'altra sponda, essa si viene a trovare effettivamente sola con Marito2 e Marito3, per cui sembrerebbe non rispettata la condizione imposta dal problema.
Beh! essendo che la traccia lascia spazio a varie interpretazioni in proposito, io ho ritenuta rispettata la condizione imposta dal problema in quanto moglie1 non scende dalla barca, e quindi non si trova sola con marito2 e marito3 in quanto si trovano su posizioni diverse (barca - sponda).

In ogni caso, volendo considerare non valida la soluzione sopra riportata, vi sarebbe un'altra possibile soluzione, che però presenta anch'essa una situazione ambigua;
comincio a mostrarvi la soluzione:

1° viaggio)
salgono sulla barca Moglie1 e Moglie2;sull'altra sponda scende Moglie1;
Moglie2 ritorna al punto di partenza;

2° viaggio)
sale sulla barca anche Marito2;

SITUAZIONE
1° sponda: Marito1,Marito3,Moglie3 (tutto OK)
sulla barca: Marito2,Moglie2 (tutto OK)
2° sponda: Moglie1 (tutto OK)

sull'altra sponda scendono Moglie2 e Marito2 e sale sulla barca Moglie1; (situazione ambigua)

SITUAZIONE
1° sponda: Marito1,Marito3,Moglie3 (tutto OK)
sulla barca: Moglie1 (tutto OK)
2° sponda: Marito2,Moglie2 (tutto OK)

Moglie1 ritorna al punto di partenza;

3° viaggio)
Moglie1 scende sulla barca e salgono Marito1 e Marito3;

SITUAZIONE
1° sponda: Moglie1,Moglie3 (tutto OK)
sulla barca: Marito1,Marito3 (tutto OK)
2° sponda: Marito2,Moglie2 (tutto OK)

sull'altra sponda scende Marito3;

SITUAZIONE
1° sponda: Moglie1,Moglie3 (tutto OK)
sulla barca: Marito1 (tutto OK)
2° sponda: Marito3,Marito2,Moglie2 (tutto OK)

Marito1 ritorna al punto di partenza;

4° viaggio)
sale sulla barca Moglie1;

SITUAZIONE
1° sponda: Moglie3 (tutto OK)
sulla barca: Marito1,Moglie1 (tutto OK)
2° sponda: Marito3,Marito2,Moglie2 (tutto OK)

sull'altra sponda scendono Marito1 e Moglie1 e sale Marito3;

SITUAZIONE
1° sponda: Moglie3 (tutto OK)
sulla barca: Marito3 (tutto OK)
2° sponda: Marito2,Moglie2,Marito1,Moglie1 (tutto OK)

Marito3 ritorna al punto di partenza;

5° viaggio)
sale sulla barca anche Moglie3;

SITUAZIONE
1° sponda: Nessuno
sulla barca: Marito3,Moglie3 (tutto OK)
2° sponda: Marito2,Moglie2,Marito1,Moglie1 (tutto OK)

sull'altra sponda scende prima Marito3 e poi Moglie3;

SITUAZIONE FINALE
1° sponda: Nessuno
sulla barca: Nessuno
2° sponda: Marito3,Moglie3,Marito2,Moglie2,Marito1,Moglie1 (tutto OK)

Come già detto, anche in questa soluzione, volendo, c'è una situazione ambigua:
infatti, nel 2° viaggio, Marito1 si trova sulla 1° sponda, mentre sull'altra sponda scendono dalla barca Marito2 e moglie2, e ne contempo, Moglie1 sale sulla barca.
Ora è chiaro che (volendo essere precisi eh!) in questo salire-scendere dalla barca, inevitabilmente Moglie1 si trovi sola con Marito2 e Moglie2.

Per cui, in definitiva, volendo accettare le situazioni ambigue illustrate come non influenti sulla condizione richiesta dal problema, le due soluzioni sono più che valide.

In caso contrario sembra non ci siano soluzioni possibili.

Penso comunque che il problema, quando è stato ideato non tenesse conto di queste situazioni particolari.

Ivana Niccolai
In merito al problema "I tre mariti gelosi", per evitare le situazioni ambigue, acutamente rilevate da Pietro Vitelli, i personaggi possono organizzarsi nel seguente modo:

Primo viaggio
Passano dapprima due mogli (es.Moglie1 e Moglie2)
Una delle due (es.Moglie1) ritorna al punto di partenza.

Secondo viaggio
Moglie1 e Moglie3 attraversano il fiume e arrivano sull'altra sponda
Una delle tre mogli (es. Moglie3) ritorna indietro e resta con suo marito (Marito3)

Terzo viaggio
Gli altri due mariti (Marito1 e Marito2) attraversano il fiume e giungono sull'altra sponda.
Una moglie e il proprio marito (es. Moglie2 e Marito2) ritornano indietro

Quarto viaggio
I due mariti(M2 e M3) attraversano il fiume
La Moglie1 ritorna indietro

Quinto viaggio
La Moglie1 e la Moglie 2 attraversano il fiume
Una delle due oppure il Marito3 torna indietro

Sesto viaggio
Una delle due Mogli, oppure il Marito3 attraversa con la Moglie3.

4. Le madri gelose
Pietro Vitelli
Non è simile, è identico al precedente;
per cui uso ancora una volta la stessa soluzione:

Innanzitutto, osserviamo che il numero minimo di viaggi che bisogna fare è 5 (per viaggio si intende andata e ritorno);

infatti:

1° viaggio) salgono in due sulla barca: uno scende sull'altra sponda e l'altro ritorna;
2° viaggio) sale un altro, così sono di nuovo in due sulla barca: uno scende sull'altra sponda (e sono 2) e l'altro ritorna;
3° viaggio) sale un altro, così sono di nuovo in due sulla barca: uno scende sull'altra sponda (e sono 3) e l'altro ritorna;
4° viaggio) sale un altro, così sono di nuovo in due sulla barca: uno scende sull'altra sponda (e sono 4) e l'altro ritorna;
5° viaggio) sale un altro, così sono di nuovo in due sulla barca: scendono entrambi sull'altra sponda (sono 6).

Ora vediamo in che modo devono essere fatti:

indichiamo Madri e figli nel seguente modo:

Madre1 - Figlio1
Madre2 - Figlio2
Madre3 - Figlio3

1° viaggio)

salgono sulla barca Madre1 e Figlio1;sull'altra sponda scende Madre1;
Figlio1 ritorna al punto di partenza;

2° viaggio)

sale sulla barca Figlio2;

SITUAZIONE
1° sponda: Madre2,Madre3,Figlio3 (tutto OK)
sulla barca: Figlio1,Figlio2 (tutto OK)
2° sponda: Madre1 (tutto OK)

sull'altra sponda scende Figlio1;

SITUAZIONE
1° sponda: Madre2,Madre3,Figlio3 (tutto OK)
sulla barca: Figlio2 (tutto OK)
2° sponda: Madre1,Figlio1 (tutto OK)

Figlio2 ritorna al punto di partenza;

3° viaggio) sale sulla barca Madre2;

SITUAZIONE
1° sponda: Madre3,Figlio3 (tutto OK)
sulla barca: Madre2,Figlio2 (tutto OK)
2° sponda: Madre1,Figlio1 (tutto OK)

sull'altra sponda scende Madre2;

SITUAZIONE
1° sponda: Madre3,Figlio3 (tutto OK)
sulla barca: Figlio2 (tutto OK)
2° sponda: Madre2,Madre1,Figlio1 (tutto OK)

Figlio2 ritorna al punto di partenza;

4° viaggio)

sale sulla barca Figlio3;

SITUAZIONE
1° sponda: Madre3 (tutto OK)
sulla barca: Figlio3,Figlio2 (tutto OK)
2° sponda: Madre2,Madre1,Figlio1 (tutto OK)

sull'altra sponda scende Figlio2;

SITUAZIONE
1° sponda: Madre3 (tutto OK)
sulla barca: Figlio3 (tutto OK)
2° sponda: Madre2,Figlio2,Madre1,Figlio1 (tutto OK)

Figlio3 ritorna al punto di partenza;

5° viaggio)
sale sulla barca Madre3;

SITUAZIONE
1° sponda: Nessuno
sulla barca: Madre3,Figlio3 (tutto OK)
2° sponda: Madre2,Figlio2,Madre1,Figlio1 (tutto OK)

sull'altra sponda scende prima Madre3 e poi Figlio3;

SITUAZIONE FINALE
1° sponda: Nessuno
sulla barca: Nessuno
2° sponda: Madre3,Figlio3,Madre2,Figlio2,Madre1,Figlio1 (tutto OK)

Ovviamente vale lo stesso discorso fatto nel problema precedente per le situazioni ambigue.
Non mi sembra il caso di riportare anche l'altra soluzione.

5. Tre padroni e tre servitori
Pietro Vitelli

Innanzitutto, osserviamo che il numero minimo di viaggi che bisogna fare è 5 (per viaggio si intende andata e ritorno);

infatti:

1° viaggio) salgono in due sulla barca: uno scende sull'altra sponda e l'altro ritorna;
2° viaggio) sale un altro, così sono di nuovo in due sulla barca: uno scende sull'altra sponda (e sono 2) e l'altro ritorna;
3° viaggio) sale un altro, così sono di nuovo in due sulla barca: uno scende sull'altra sponda (e sono 3) e l'altro ritorna;
4° viaggio) sale un altro, così sono di nuovo in due sulla barca: uno scende sull'altra sponda (e sono 4) e l'altro ritorna;
5° viaggio) sale un altro, così sono di nuovo in due sulla barca: scendono entrambi sull'altra sponda (sono 6).

Ora vediamo in che modo devono essere fatti:

indichiamo servitori e padroni nel seguente modo:

Padrone A - Servitore A = PA - SA
Padrone B - Servitore B = PB - SB
Padrone C - Servitore C = PC - SC

1° viaggio) salgono sulla barca PA e SA;sull'altra sponda scende PA;
SA ritorna al punto di partenza;

2° viaggio) sale sulla barca SB;

SITUAZIONE
1° sponda: PB,PC,SC (tutto OK)
sulla barca: SA,SB (tutto OK)
2° sponda: PA (tutto OK)

sull'altra sponda scende SA;

SITUAZIONE
1° sponda: PB,PC,SC (tutto OK)
sulla barca: SB (tutto OK)
2° sponda: PA,SA (tutto OK)

SB ritorna al punto di partenza;

3° viaggio) sale sulla barca PB;

SITUAZIONE
1° sponda: PC,SC (tutto OK)
sulla barca: PB,SB (tutto OK)
2° sponda: PA,SA (tutto OK)

sull'altra sponda scende PB;

SITUAZIONE
1° sponda: PC,SC (tutto OK)
sulla barca: SB (tutto OK)
2° sponda: PB,PA,SA (tutto OK)

SB ritorna al punto di partenza;

4° viaggio) sale sulla barca SC;

SITUAZIONE
1° sponda: PC (tutto OK)
sulla barca: SC,SB (tutto OK)
2° sponda: PB,PA,SA (tutto OK)

sull'altra sponda scende SB;

SITUAZIONE
1° sponda: PC (tutto OK)
sulla barca: SC (tutto OK)
2° sponda: PB,SB,PA,SA (tutto OK)

SC ritorna al punto di partenza;

5° viaggio) sale sulla barca PC;

SITUAZIONE
1° sponda: Nessuno
sulla barca: PC,SC (tutto OK)
2° sponda: PB,SB,PA,SA (tutto OK)

sull'altra sponda scende prima PC e poi SC;

SITUAZIONE FINALE
1° sponda: Nessuno
sulla barca: Nessuno
2° sponda: PC,SC,PB,SB,PA,SA (tutto OK)

Anche qui vale lo stesso discorso del problema 3 per quanto riguarda le situazioni ambigue.

6. Gli schiavi assassini
Indichiamo com P, P, P i tre padroni e con s, s, s i loro servitori e con l'asterisco la barca.

1 - PPPs>>>ss*
2 - PPPss*<<<s
3 - PPP>>>sss*
4 - PPPs*<<<ss
5 - Ps>>>PPss*
6 - PPss*<<<Ps
7 - ss>>>PPPs*
8 - Pss*<<<PPs
9 - s>>>PPPss*
10 - Ps*<<<PPss
11 ->>>PPPsss*

Ivana Niccolai
Per quanto riguarda il problema "I quattro mariti gelosi" si può risolvere se la barca può trasportare fino a tre persone alla volta.

Primo viaggio
S'imbarcano la Moglie1, la Moglie2 e la Moglie3 e arrivano sull'altra sponda
Una delle tre torna indietro

Secondo viaggio
Quella che è tornata indietro (es.Moglie1) passa insieme con la Moglie 4
La Moglie4 torna indietro

Terzo viaggio
La Moglie4 resta con il Marito4 e gli altri tre mariti attraversano il fiume
Uno dei tre mariti, che sono passati, (es.Marito1) torna indietro con la propria Moglie1

Quarto viaggio
Marito1, Moglie1 e Marito4 attraversano il fiume.
Il Marito4 (oppure una delle tre mogli) ritorna indietro

Quinto viaggio
Il Marito4 (oppure una delle tre mogli) attraversa con la Moglie4

8. I cinque mariti gelosi
Chiamiamo A, B, C, D, E i tre mariti e a, b, c,d ,e le loro rispettive mogli. Indichiamo la barca con un aterisco *.
La soluzione può allora essere rappresentata così.

di Pietro Vitelli

Come indicato dalla traccia, n è il numero di persone che devono attraversare il fiume, ed x e il numero di posti della barca.

Se la barca ha x posti, ciò vuol dire che possono scendere da essa al massimo x-1 persone alla volta sull'altra sponda, dato che una deve sempre rimanere sulla barca per remare.
Ovviamente all'ultimo passaggio scenderanno x persone.
E' facile quindi rendersi conto che il numero minimo di passaggi che ,in ogni caso, si possono effettuare sarà:

PASSmin= 2*[(n-x)/(x-1)]+1 con [(n-x)/(x-1)] approssimata per eccesso all'intero.

Infatti n-x è il numero massimo di persone che possono scendere sull'altra sponda dopo tutti i passaggi, senza però considerare l'ultimo passaggio, che ovviamente servirà per traghettare le restanti x persone, dato che i posti sulla barca sono x.
Ora, dividendo n-x per x-1 sapremo quanti viaggi (1 viaggio = 2 passaggi) sono necessari per traghettare tutte le n-x persone a gruppi da x-1 alla volta.
Ovviamente il +1 sta ad indicare l'ultimo viaggio fatto per traghettare le restanti x persone.
Se il risultato della divisione non è un intero, bisogna arrotondarlo per eccesso, proprio perchè, dato che tale espressione ci indica il numero MINIMO di passaggi, essa tende a togliere il più possibile.

ricordo che deve essere sempre fatta prima la divisione e poi la moltiplicazione per 2 (eventuali semplificazioni tra denominatore e il 2 compromettono il risultato dei passaggi).

Ex. Se n=6 e x=2 avremo Num.Pass.Min.= 2*(4/1)+1 = 9 passaggi

Detto ciò bisogna vedere se con tale numero di passaggi è possibile traghettare tutte le persone.
Premetto che qui (come nel problema 3)si vengono a creare entrambe le situazione ambigue, che citerò alla fine:

Analizziamo dapprima alcuni casi fondamentali per poi generalizzare il problema:

Caso I) n coppie e barca a 2 posti

Consideriamo per ora solo le prime due coppie che indicheremo con Ma1-Mo1, Ma2-Mo2:
Mo1 e Mo2 salgono sulla barca; sull'altra sponda scende Mo2 mentre Mo1 torna indietro;
a questo punto anche Ma1 sale sulla barca; dall'altra parte scendono sia Mo1 che Ma1 mentre Mo2 torna indietro e scende dalla barca.

A questo punto la situazione è la seguente:

1° SPONDA: Ma2-Mo2,Ma3-Mo3,...,Man-Mon
SULLA BARCA: Nessuno
2° SPONDA: Ma1-Mo1

Tale situazione è uguale a quella iniziale con la differenza che una coppia è passata dalla 1° alla 2° sponda.
In particolare, mentre all'inizio avevamo n coppie sulla 1° sponda, adesso ne abbiamo n-1 sulla 1° sponda.
Per cui applicando nuovamente i due viaggi sopra descritti con altre 3 coppie, si riesce a portare dall'altro lato un'altra coppia e così vià, fino alla fine.
Ora, dato che ad ogni viaggio, una persona scende sull'altra sponda, avremo anche il minimo numero di passaggi possibili, calcolabile mediante la formula sopra scritta.

Caso II) n coppie e barca a 3 posti

Mo1, Mo2 e Mo3 salgono sulla barca (è l'unica situazione ammissibile affinchè sulla barca salgano 3 persone); sull'altra sponda scendono Mo2 e Mo3, mentre Mo1 ritorna indietro;
a questo punto salgono sulla barca insieme a Mo1, Ma1 e Ma2; dall'altra parte scendono Mo1, Ma1 e Ma2, e, nel contempo Mo3 sale sulla barca;Mo3 ritorna indietro e scende.

A questo punto la situazione è la seguente:

1° SPONDA: Ma3-Mo3,Ma4-Mo4,...,Man-Mon
SULLA BARCA: Nessuno
2° SPONDA: Ma1-Mo1,Ma2-Mo2

Tale situazione è uguale a quella iniziale con la differenza che 2 coppie sono passate dalla 1° alla 2° sponda.
In particolare, mentre all'inizio avevamo n coppie sulla 1° sponda, adesso ne abbiamo n-2 sulla 1° sponda. Per cui applicando nuovamente i due viaggi sopra descritti con altre 3 coppie, si riesce a portare dall'altro lato altre 2 coppie e così vià, fino alla fine.
Ora, dato che ad ogni viaggio, 2 persone scendono sull'altra sponda, avremo anche il minimo numero di passaggi possibili, calcolabile mediante la formula sopra scritta.

Caso III) n coppie e barca a 4 posti

Analizziamo quest'altro caso per poi generalizzare il tutto:

Mo1,Mo2,Mo3 e Mo4 salgono sulla barca; sull'altra sponda scendono Mo2,Mo3 e Mo4, mentre Mo1 torna indietro; a questo punto salgono sulla barca insieme a Mo1, Ma1,Ma2 e Ma3; sull'altra sponda scendono tutti e quattro, mentre Mo4 ritorna indietro e scende dalla barca.

A questo punto la situazione è la seguente:

1° SPONDA: Ma4-Mo4,Ma5-Mo5,...,Man-Mon
SULLA BARCA: Nessuno
2° SPONDA: Ma1-Mo1,Ma2-Mo2,Ma3-Mo3

Tale situazione è uguale a quella iniziale con la differenza che 3 coppie sono passate dalla 1° alla 2° sponda.
In particolare, mentre all'inizio avevamo n coppie sulla 1° sponda, adesso ne abbiamo n-3 sulla 1° sponda.
Per cui applicando nuovamente i due viaggi sopra descritti con altre 4 coppie, si riesce a portare dall'altro lato altre 3 coppie e così vià, fino alla fine.
Ora, dato che ad ogni viaggio, 3 persone scendono sull'altra sponda, avremo anche il minimo numero di passaggi possibili, calcolabile mediante la formula sopra scritta.

Dall'analisi di questi tre casi risulta evidente che, ripetendo più volte la sequenza dei 2 passaggi, si giunge alla soluzione utilizzando anche il minimo numero di passaggi possibili;

Si nota che i passaggi sono differenti a seconda del numero di posti che la barca ha;

In generale, essendo n il numero di persone che deve traversare il fiume ed x i posti della barca, la soluzione è la seguente:

1° viaggio:

salgono sulla barca x mogli; scendono dall'altra parte x-1 mogli; una moglie torna indietro.

2° viaggio:

sale sulla barca insieme alla moglie tornata indietro, anche suo marito; salgono anche tutti i mariti delle mogli che si trovano sull'altra sponda tranne uno a scelta; in tal modo sono saliti esattamente in x sulla barca; dall'altra parte scendono tutti, mentre la moglie il cui marito è rimasto dall'altra parte, ritorna indietro e scende dalla barca.

SITUAZIONE ATTUALE:

1° sponda: Ci sono n-(x-1) coppie
Sulla barca: Nessuno
2° sponda: x-1 coppie

Ripetere più volte i viaggi sopra indicati finchè tutte le n persone non avranno attraversato il fiume.

-----------------------

Veniamo ora alla situazione ambigua già discussa nel problema 3:

Notiamo che nel secondo dei due viaggi da effettuare per poi ripetere sempre il tutto, quando l'equipaggio sbarca sull'altra sponda, su questa vi si trova una moglie il cui marito è rimasto sull'altra sponda, che quindi deve tornare indietro;
ora è logico che essa per qualche istante, prima che salga sulla barca si trovi sola con altri mariti, non rispettando la condizione iniziale del problema.

Per cui, in definitiva, volendo accettare la situazione ambigua illustrata come non influente sulla condizione richiesta dal problema, la generalizzazione è corretta.

In caso contrario sembra non ci siano soluzioni possibili.

Penso comunque che i vari problemi del genere, quando ideati, non tenessero conto di queste situazioni particolari.

11. Tre leopardi e tre capre
Riccardo Fusilli
Dato che il numero dei leopardi non deve mai superare il numero delle capre sulle due rive e che il pastore può trasportare due animali sulla barca, il traghettamento può essere risolto con cinque passaggi: basta che il pastore trasporti un leopardo ed una capra alla volta; sulle rive, quindi, il numero dei leopardi non sarà mai superiore al numero delle capre.

15. Strani pesi
Pietro Vitelli

E' molto semplice.

1° viaggio (2 passaggi):

Salgono per primi sulla barca le persone che pesano 1 e 2.
Sull'altra sponda scende la persona che pesa 2.
La persona pesante 1 ritorna al punto di partenza.

2° viaggio (2 passaggi):

La persona pesante 1 scende dalla barca e sale la persona che pesa 3.
Sull'altra sponda scende la persona che pesa 3 e sale quella pesante2 la quale ritorna al punto di partenza.

3° viaggio (1 passaggio):

A questo punto, sale anche la persona pesante 1 sulla barca, e si avviano verso l'altra sponda.

Per un totale di 3 viaggi, o meglio di 5 passaggi.
Semplice no!

16. I cinque erranti
di Pietro Vitelli

1° viaggio (2 passaggi):

Salgono sulla barca 2 e 4; sull'altra sponda scende 2; 4 ritorna al punto di partenza.

2° viaggio (2 passaggi):

4 scende dalla barca e salgono 3 e 5; sull'altra sponda scendono 3 e 5, e sale 2;
2 ritorna al punto di partenza.

3° viaggio (2 passaggi):

2 scende dalla barca e salgono 1 e 4; sull'altra sponda scende 1; 4 ritorna al punto di partenza.

4° viaggio (1 passaggio):

Sale anche 2 sulla barca insieme a 4 e si avviano verso l'altra sponda.

Per un totale di 4 viaggi, cioè di 7 passaggi.

Quello che non mi quadra é ciò che viene esattamente specificato come vincolo nel quiz
" Ai due capi della corda sono fissate due robuste ceste in ciascuna delle quali può stare un uomo o il blocco di cemento."

Ora mi accorgo che il passo 3 del mio ragionamento è in aperta contraddizione con le condizioni del problema, "o solo l'uomo" o "solo il blocco", perche' salgono e l'uomo e il blocco.

Allora esiste una soluzione diversa da quella da me prospettata e che non trovo nel sito?

Gianfranco Bo
"...un uomo o il blocco di cemento."
La soluzione di Giovanna è corretta se si intende "o" come alternativa inclusiva (il vel latino), che significa: uno dei due o entrambi.
Il problema è risolubile anche nel caso "o" sia un'alternativa esclusiva (l'aut latino), che significa: uno dei due ma non entrambi?

Alan Viezzoli
Il problema, se consideriamo l'aut, è impossibile in quanto il ciccione pesa
195 kg e non c'è nient'altro con un peso maggiore o uguale a 195-15=180 kg
ed è impossibile per il ciccione scendere.

ABCabc*
BCbc >>>Aa*
BCbc <<<a*	A
ABCc >>>ab*	A
BCc <<<b*	Aa
ACc >>>Bb*	Aa
Cc <<<b*	ABa
C >>>cb*	ABa
C <<<c*	ABab
>>>Cc*	ABab
	ABCabc*