[HOME - BASE Cinque - Appunti di Matematica ricreativa]

Il problema della Jeep

1. Il problema della Jeep
Il famoso esploratore Evaristo Slogai vuole compiere una grande impresa: attraversare il deserto con la sua jeep e senza l'aiuto di nessuno.
Il problema è che la sua Jeep può trasportare al massimo il carburante sufficiente per attraversare metà deserto.
Inoltre in questo problema esiste uno e uno solo distributore di carburante che si trova nella località di partenza.
Nonostante ciò, Evaristo riesce a risolvere il problema.
Come?
Quanti carichi di carburante dovrà consumare per portare a termine l'impresa?
Quanti carichi di carburante sono necessari per effettuare sia l'andata che il ritorno?
G.G. Alway, 1957

Questo problema è molto antico.
Probabilmente risale ad Alcuino di York (900) ed è stato ripreso da Pacioli (1500), Cardano (1500), Loyd (1900), Dudeney (1900), e molti altri.
Ecco un esempio tratto da Pacioli (con variazioni), simile ad una versione di Alcuino.

2. Il trasporto delle mele
Un uomo deve trasportare 90 mele a 30 km di distanza.
Può trasportarne al massimo 30 alla volta e ne mangia una ogni chilometro.
Come deve organizzarsi per portare a destinazione il maggior numero possibile di mele?
Quante mele riuscirà a trasportare a destinazione al massimo?
Pacioli, 1500

3. La traversata del deserto
Si devono trasportare 3000 pannocchie di mais, attraverso il deserto, da un'oasi A ad un'oasi B distanti 1000 km.
Si ha a disposizione solo un cammello che può trasportare 1000 pannocchie al massimo, e che deve mangiare una pannocchia per ogni chilometro di viaggio.
Qual è il massimo numero di pannocchie che si possono trasportare da A a B?

4. Il problema dell'esploratore
Il famoso esploratore Evaristo Slogai è alle prese con un'altra avventura: vuole attraversare il deserto a piedi.
La traversata richiede 6 giorni, ma Evaristo è in grado di trasportare viveri sufficienti per 4 giorni, non di più.
Gli indigeni possono aiutarlo mettendogli a disposizione dei portatori.
Ciascun portatore può trasportare viveri sufficienti per 4 giorni e deve tornare sano e salvo alla base.
Qual è il miglior sistema per attraversare il deserto e qual è il minimo numero di portatori necessario per l'impresa?

Ivan Furlan ha risolto correttamente il problema con 0 (zero) portatori.
Desidero allora porre qualche domanda in più.

Risolvere il problema nei tre casi seguenti:

  1. Evaristo vuole fare tutto da solo, senza l'aiuto dei portatori (soluzione data da Ivan).
  2. Evaristo è disposto a portare il proprio zaino ma non vuole né fermarsi né tornare indietro. Vuole attraversare il deserto non stop.
  3. Evaristo vuole attraversare il deserto non stop e non vuole trasportare pesi.

Johannes Lehmann, 1980

5. Il giro del mondo in aereo
Un aereo deve compiere il giro del mondo senza scalo, ma può trasportare carburante sufficiente per metà del viaggio. Altri aerei dello stesso tipo possono raggiungerlo e rifornirlo in volo ma devono ritornare alla base.
Come può essere organizzata l'impresa?
Liz Allen, 1991

Esistono le più svariate versioni di questo problema.


Risposte & riflessioni

1. Il problema della Jeep
In sintesi il problema chiede come si possa attraversare un deserto di lunghezza 2 con una jeep che può trasportare al massimo il carburante necessario per percorrere la distanza 1.
Risolvo qui il caso di sola andata.

Divido il tragitto in due parti di lunghezza 1 e divido la prima parte in tre terzi.

A......B.....C.....M.....................Z
|------|------|------|------|------|------|

0....1/3..2/3.....1.......................2

Parto dal punto M e procedo a ritroso.

Dunque, con 14 pieni in A posso attraversare il deserto, solo andata.

Non credo che questo sia il metodo più efficiente, chissà se qualcuno ne trova uno migliore...
Che cosa accadrebbe se ci fossero più tappe?
E se le distanze fra le tappe successive fossero diverse?

In questo caso esiste un'altra strategia che permette di attraversare il deserto con soli 8 pieni.
Il segreto sta nella seguente successione numerica:

1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/13 + 1/15 >1

A....B......C......D........E........F..........G..........H
|-----|------|-------|-------|--------|---------|----------|----------------------------------------------------------|
1/15.....1/13......1/11.......1/9.........1/7..........1/5............1/3......1.......................................................................2

Ecco il ragionamento.

1) L'obiettivo è avere 1 pieno in H posto a distanza 1 dall'origine.

2) Si può trasportare 1 pieno in H se si hanno 2 pieni in G, posto a distanza 1/3 da H.
Sono necessari 2 viaggi. (caburante: 1/3 + 2/3)

3) Si possono trasportare 2 pieni in G se si hanno 3 pieni in F, posto a 1/5 da G.
Sono necessari 3 viaggi. (carburante: 3/5 + 3/5 + 4/5)

4) Si possono trasportare 3 pieni in F se si hanno 4 pieni in E, posto a 1/7 da F.
Sono necessari 4 viaggi. (carburante: 5/7 + 5/7 + 5/7 + 6/7)

In generale (posta uguale ad 1 la distanza che si percorre con un pieno) si possono trasportare n pieni in un punto X se si hanno (n+1) pieni in un altro punto che dista 1/(2n+1) da X

Procedendo allo stesso modo, all'8° passaggio ci si trova addirittura un po' prima dell'origine, con 8 pieni di carburante.

Infatti:

1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/13 + 1/15 = 1,02180042...

2. Il trasporto delle mele
di Roberto Callegari

N.d.R. Riporto in sintesi la soluzione di Roberto e di seguito le sue spiegazioni chiare ed esaurienti.
L'uomo può portare a destinazione 12 mele.
A tale scopo divide il percorso in 2 tappe: la prima di 12 km e la seconda di 18 km.
Poi porta in tre viaggi tutte le mele al termine della prima tappa. Infine porta a destinazione tutte le mele rimaste.
Roberto dimostra inoltre che questa è la soluzione migliore se si divide il percorso in due tappe.

Se l'uomo parte con 30 mele e compie l'intero percorso arriva con 0 mele.

Per questo l'uomo deve dividere il percorso almeno in due tratti.

Detto x il primo tratto, vale la condizione:

x<15 km

Se x=15 km allora l'uomo può arrivare al massimo a metà percorso e ci arriva con 15 mele che deve utilizzare per tornare a prendere le mele rimaste; all'ultimo passaggio avrà 15 mele e sarà a metà percorso e arriverà al traguardo con 0 mele.

DESCRIZIONE DELLA SOLUZIONE PER IL PERCORSO DIVISO IN DUE TRATTI

Tutto il percorso diviso in due tratti può essere così descritto.

Mele al punto di partenza/direzione Km percorsi Mele mangiate Mele alla distanza x Totale mele
90 (inizio) 0 0 0 90+0+0+0
60 andata>>>>> x x 30-x 60+x+30-x
60 ritorno<<<<< x 2x 30-x-x=30-2x 60+2x+30-2x
30 andata>>>>> x 3x 30-2x+30-x=60-3x 30+3x+60-3x
30 ritorno<<<<< x 4x 60-3x-x=60-4x 30+4x+60+4x
00 andata>>>>> x 5x 60-4x+30-x=90-5x 0+5x+90-5x

A questo punto alla distanza x ho esattamente 90-5x mele e restano da percorrere 30-x km  e saranno mangiate 30-x mele.

90-5x vale al massimo 30 mele, se valesse di più non riuscirei a trasportarle con un unico viaggio e dovrei fare più viaggi.

Mele arrivate 12

Chiamo S questa soluzione.

Se x<12

Mele arrivate 30-d<30-18=12

E rimangono delle mele alla posizione x che non sono riuscito a trasportare

Se x>12

Mele arrivate 90-m-d=90-5x-30-x=60-4x<60-4*12=12

Le mele che arrivano quindi sono meno di quelle della soluzione S

Per cui risulta che la soluzione S è valida se il percorso è diviso in due parti.

3. La traversata del deserto
Roberto Callegari
La soluzione è analoga a quella delle mele:
400 pannocchie con due tratte di 400 km e 600 km.

Gianfranco Bo
Ripeto il testo del problema:
Si devono trasportare 3000 pannocchie di mais, attraverso il deserto, da un'oasi A ad un'oasi B distanti 1000 km.
Si ha a disposizione solo un cammello che può trasportare 1000 pannocchie al massimo, e che deve mangiare una pannocchia per ogni chilometro di viaggio.
Qual è il massimo numero di pannocchie che si possono trasportare da A a B?

La soluzione di Roberto va bene ma io mi chiedo: è possibile fare di più, cioè portare a destinazione più di 400 pannocchie?
E' possibile se si divide il percorso in più di due tratte.
Il problema è riuscire a depositare 1000 pannocchie (il massimo carico trasportabile) il più vicino possibile alla destinazione.

0---------200---------534---------1000
I-------------I--------------I----------------I arrivo con 532 pannocchie

Ecco una possibile soluzione:

In 3 viaggi riesco a depositare 600+600+800=2000 pannocchie al chilometro 200.
In altri 2 viaggi, dal chilometro 200 al chilometro 534, riesco a depositare 332+666=998 pannocchie al chilometro 534.
In 1 viaggio percorro gli ultimi 466 km e porto a destinazione 998-466=532 pannocchie.

Un particolare ringraziamento a Lucia Di Mauro che ha trovato e corretto un errore permettendo così di trovare il punto ottimale e di scrivere la soluzione esatta.

Infatti il punto ottimale dovrebbe essere il km 533 con il quale si riescono a trasportare 533 pannocchie:

Ora la domanda è: questa è la strategia ottimale o ne esiste un'altra migliore?

4. Il problema dell'esploratore
Riporto l'interessante soluzione di Ivan ma lascio il problema ancora aperto. Lesploratore dovrebbe atraversare il deserto senza mai fermarsi né tornare indietro, usufruendo dell'aiuto dei portatori: quanti? come?
Ivan Furlan
Ce la puo' fare con 0 portatori.
Metodo per giungere alla meta:
I'esploratore parte solo carico al masssimo, viveri per 4 giorni.
Dopo un giorno di cammino, lascia sulla strada viveri per due giorni, e ritorna a casa con il giorno di viveri restatogli.
Giunto a casa, riparte carico con viveri per 4 giorni, riviaggia per un giorno, quindi recupera viveri per un giorno dai viveri per due giorni lasciati nel viaggio precedente.
E' quindi ancora carico al massimo, parte viaggiando ancora per un giorno, e lascia sulla strada viveri per un giorno, rimanendo con viveri per 2 giorni sufficienti per il ritorno.
Parte quindi per l'ultima volta carico al massimo, viveri  per 4 giorni.
Dopo il primo giorno, puo' fare il pieno con viveri per un giorno che trovera' sulla strada.
Dopo il secondo giorno di cammino potra' nuovamente fare il pieno di viveri, trovando viveri per un giorno sulla strada,
Si trova ora a 4 giorni dalla meta con 4 giorni di viveri, sufficienti per arrivarci.
...

Dino
La strategia da utilizzare per attraversare il deserto a piedi dipende da che tipo di impresa si vuole realizzare: infatti, se come obiettivo occorre impiegare il minor tempo possibile, cioè sei giorni, sarà necessario sicuramente l'aiuto degli indigeni ed allora bisognerà determinare il numero minimo di questi, mentre se è quello di realizzare l'impresa sfruttando il numero minore di portatori di viveri, al limite farla proprio da solo, occorreranno sicuramente più giorni per raggiungere la meta ed allora bisognerà determinare il tempo minimo affinchè ciò sia possibile.

Esaminiamo dapprima come occorre procedere se l'obiettivo è quello di impegare solo sei giorni. In tal caso ad Evaristo Slogai bastano solo due portatori di viveri. Infatti, se ognuno dei tre all'inizio del viaggio portano viveri per quattro giorni, alla fine del primo ognuno avrà consumato una dose a testa e perciò restano con scorte per altri tre giorni. A questo punto, quindi, uno dei due indigeni che sta accompagnando il nostro eroe può cedere la dose per un giorno all'altro portatore e una dose anche a Slogai e tornarsene a casa con la dose restante sano e salvo. Quindi dopo il primo giorno continuano il viaggio solo l'esporatore con un portatore di viveri ed entrambi hanno un carico sufficiente per altri quattro giorni. Alla fine del secondo giorno ognuno di essi avrà consumato un'altra dose di viveri e restano così con scorte sufficienti per altri tre giorni. L'indigeno però può cedere la dose giornaliera a Evaristo Slogai e con le due restanti tornarsene a casa da solo sano e salvo. Dunque dopo il secondo giorno continuerà il viaggio solo l'esporatore con un carico di viveri pari ancora a quattro giorni sufficienti a farlo giungere alla meta finale da solo.

Esaminiamo invece il caso in cui l'obiettivo è quello di riuscire nell'avventura da solo e senza alcun aiuto da parte di terzi. In questo caso occorreranno più di sei giorni, come detto, per poter tornare indietro e approvigionarsi di nuove scorte. L'esploratore all'inizio parte col carico al masssimo, cioè con viveri per quattro giorni. Dopo un giorno di cammino, lascia sulla strada viveri per due giorni, e ritorna indietro con il giorno di viveri restatogli. Giunto a casa due giorni dopo l'inizio dell'impresa, riparte con un altro carico di viveri per ulteriori quattro giorni e riviaggia per un giorno, quindi recupera viveri per un giorno da quelli lasciati per strada nel viaggio precedente. E' quindi ancora carico al massimo. Continua viaggiando ancora per un altro giorno, e lascia sulla strada viveri per due giorni, rimanendo con viveri per un solo giorno sufficienti per farlo ritornare indietro dove per strada recupera anche il carico giornaliero che aveva lasciato lungo il suo percorso e giunge così di nuovo a casa dopo sei giorni dall'inizio della sua avventura. Ancora però non ha concluso la sua impresa quando invece nello stesso tempo, ma con l'aiuto degli indigeni, avrebbe potuto già terminarla come già esaminato prima nel dettaglio. Dopo tanta fatica riparte quindi per l'ultima volta col carico al massimo, viveri per quattro giorni, e dopo altri due giorni di cammino farà nuovamente il pieno, ritrovando i viveri sulla sua strada, che aveva lasciato in precedenza, per appunto due giorni. Si trova ora a quattro giorni dalla meta con quattro giorni di viveri, sufficienti per arrivarci dopo la bellezza di 12 giorni della sua esperienza.

N.d.R.
(n uomini possono aiutarne 1 per un deserto di 2nd/(n+1), d=4
1+1/3+1/5+...+1/(2n-1)

5. Il giro del mondo in aereo
Dino

Tre aerei sono sufficienti ad assicurare il volo di un aereo attorno al mondo.

Vi sono molti modi per realizzare il giro del mondo, ma il seguente sembra il più efficace; con questo si usano solo cinque serbatoi di carburante ed ha una simmetria di sviluppo.

Gli aerei A, B e C partono insieme.

Dopo aver percorso 1/8 della distanza C trasferisce 1/4 del suo carburante ad A ed 1/4 a B: a C resta 1/4 di serbatoio pieno (proprio quanto basta per tornare sull'isola). A e B continuano insieme ancora per 1/8 di percorso, poi B trasferisce 1/4 di serbatoio ad A.

B rimane con 1/2 serbatoio, proprio quanto gli basta per tornare indietro alla base dove arriva col serbatoio vuoto.

L'aereo A, col serbatoio pieno, continua sino ad 1/4 di strada dalla base dove resterebbe senza carburante.

Qui viene incontrato da C, che si è rifronito alla base e che gli trasferisce 1/4 di carburante, dopodichè entrambi si dirigono alla base.

I due aerei resterebbero senza carburante ad 1/8 di percorso dalla base, dove però vengono incontrati dall'aereo B che ha fatto rifornimento.

B trasferisce ad ognuno degli altri due 1/4 del suo serbatoio e tutti e tre gli aerei hanno ora esattamente il carburante sufficiente per raggiungere la base in riserva sparata, ma sani e salvi.


Sito Web realizzato da Gianfranco Bo