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?
Questo problema è molto antico.
Questo tipo di problema fu posto probabilmente per la prima volta da Alcuino da York, 800 circa, nella sua collezione "Ad acuendos juvenes" e ancora oggi è utilizzato persino all'Università per illustrare alcune tecniche di ottimizzazione delle risorse.
Probabilmente risale ad Alcuino di York (900) ed è stato ripreso da Pacioli (1500), Cardano (1500), Loyd (1900), Dudeney (1900), e molti altri.
Di seguito riporto un esempio tratto da Pacioli (con variazioni), simile ad una versione di Alcuino.
2. Il trasporto delle mele (Pacioli, 1500)
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?
3. La traversata del deserto
Si devono trasportare 3000 pannocchie di mais, attraverso il deserto, dall'oasi A all'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 (Johannes Lehmann, 1980)
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?
Risolvere il problema nei tre casi seguenti:
1. Evaristo vuole fare tutto da solo, senza l'aiuto dei portatori (vedi 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.
5. Il giro del mondo in aereo (Liz Allen, 1991)
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?
Esistono le più svariate versioni di questo problema.
• Cardano (1539), lo ambienta nella torre di Babele, alta 36 miglia e mette in campo 15.625 trasportatori.
• Loyd (1911), al Polo Sud.
• Dudeney (1925) e molti altri, nel deserto.
SOLUZIONI E 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.
• Per percorrere MZ occorre avere un pieno di carburante in M.
• Per avere 1 pieno (= 1/3+2/3) in M occorre avere 2 pieni in C.
Infatti, parto da C con un pieno, percorro CM consumando 1/3, deposito 1/3 in M, percorro MC consumando 1/3, carico il secondo pieno, percorro CM consumando 1/3 e mi ritrovo in M con 2/3 nel serbatoio e 1/3 depositato prima.
• Ragionando allo stesso modo, per avere 2 pieni (= 4/3 + 2/3) in C occorre avere 5 pieni in B. Devo fare 4 viaggi in cui deposito 1/3 più 1 viaggio senza ritorno in cui rimango con 2/3.
• Per avere 5 pieni (= 13/3 + 2/3) in B occorre avere 14 pieni in A.
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. (carburante: 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)
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.
• 90-5x<=30 12<=x
• distanza percorsa 12 km
• mele mangiate 5x=60
• mele rimaste 90-60=30
• km da percorrere d=18 km
Mele arrivate 12
Chiamo S questa soluzione.
Se x<12
• distanza percorsa <12 km
• mele mangiate m=5x<60
• mele rimaste 90-m>30
• km da percorrere d=30-x>18 km
Mele arrivate 30-d<30-18=12
E rimangono delle mele alla posizione x che non sono riuscito a trasportare
Se x>12
• distanza percorsa >12 km
• mele mangiate m=5x>60
• mele rimaste 90-m<30
• km da percorrere d=30-x<18 km
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 suggerisce che la soluzione è analoga a quella delle mele: 400 pannocchie con due tratte di 400 km e 600 km.
Gianfranco Bo afferma:
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:
• 1 viaggio - dal km 0 al km 200. Parto con 1000 pannocchie, ne lascio 600. Torno indietro.
• 2 viaggio - dal km 0 al km 200. Parto con 1000 pannocchie, ne lascio 600. Torno indietro.
• 3 viaggio - dal km 0 al km 200. Parto con 1000 pannocchie, arrivi al km 200 con 800 pannocchie e li ce ne erano gia' 1200. Quindi al km 200 ci sono complessivamente 2000 pannocchie.
• 4 viaggio - dal km 200 al km 533. Parto con 1000 pannocchie, ne lascio 334. Torno al km 200.
• 5 viaggio - dal km 200 al km 533. Parto con 1000 pannocchie, arrivi al km 533 con 667 pannocchie e li ce ne erano gia' 334. Quindi al km 533 ci sono complessivamente 1001 pannocchie.
• 6 viaggio visto che una pannocchia mi conviene buttarla piuttosto che tentare di recuperarla, mi carico le mie 1000 pannocchie al km 533 e vado diritta fino al km 1000 dove mi rimarranno esattamente 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. L'esploratore dovrebbe attraversare il deserto senza mai fermarsi né tornare indietro, usufruendo dell'aiuto dei portatori: quanti? come?
Ivan Furlan
Ce la può fare con 0 portatori.
Metodo per giungere alla meta:
I'esploratore parte solo carico al massimo, 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, può fare il pieno con viveri per un giorno che troverà sulla strada.
Dopo il secondo giorno di cammino potrà 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 impiegare 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'esploratore 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'esploratore 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 approvvigionarsi di nuove scorte. L'esploratore all'inizio parte col carico al massimo, 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 ri-viaggia 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
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 è rifornito 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.