Jeep nel deserto (ottimizzare)
Una Jeep deve effettuare un importante trasporto attraverso il deserto.
Lungo il tragitto non ci sono stazioni di servizio e la Jeep può portare una quantità di benzina sufficiente solo per arrivare a un terzo del percorso.
La Jeep viene quindi accompagnata da altre Jeep identiche, in questo modo la benzina può venire spostata da una Jeep all'altra, permettendo così alla Jeep principale di arrivare fino alla fine.
Domanda: qual è il numero MINIMO di Jeep che devono iniziare il viaggio (compresa la Jeep principale)? quale strategia devono adottare?
Nota bene. L'unica cosa importante è che la Jeep principale termini il viaggio.
In due maniere diverse ho trovato che sono necessarie 11 Jeep...
Ma nessuno dei due metodi mi garantisce che non si possa fare di meglio.
Mi sapreste dare una mano? Grazie
Lungo il tragitto non ci sono stazioni di servizio e la Jeep può portare una quantità di benzina sufficiente solo per arrivare a un terzo del percorso.
La Jeep viene quindi accompagnata da altre Jeep identiche, in questo modo la benzina può venire spostata da una Jeep all'altra, permettendo così alla Jeep principale di arrivare fino alla fine.
Domanda: qual è il numero MINIMO di Jeep che devono iniziare il viaggio (compresa la Jeep principale)? quale strategia devono adottare?
Nota bene. L'unica cosa importante è che la Jeep principale termini il viaggio.
In due maniere diverse ho trovato che sono necessarie 11 Jeep...
Ma nessuno dei due metodi mi garantisce che non si possa fare di meglio.
Mi sapreste dare una mano? Grazie
Risposte
Ho corretto, è mi trovo d'accordo con voi: le $11$ bastano.
Per andrea57.
Non ho mica capito, secondo il tuo ragionamento, dove la la jeep principale mette la benzina che le passano le altre jeep.
Nel serbatoio non c'è spazio. E' pieno.
Se c'è posto nel "bagagliaio", non occorre fare tutte queste storie. Basta caricare qualche tanica in più....
Evidentemente non hai colto il "senso" del problema.
Non ho mica capito, secondo il tuo ragionamento, dove la la jeep principale mette la benzina che le passano le altre jeep.
Nel serbatoio non c'è spazio. E' pieno.
Se c'è posto nel "bagagliaio", non occorre fare tutte queste storie. Basta caricare qualche tanica in più....
Evidentemente non hai colto il "senso" del problema.
"superpippone":
Per andrea57.
Non ho mica capito, secondo il tuo ragionamento, dove la la jeep principale mette la benzina che le passano le altre jeep.
Nel serbatoio non c'è spazio. E' pieno.
Se c'è posto nel "bagagliaio", non occorre fare tutte queste storie. Basta caricare qualche tanica in più....
Evidentemente non hai colto il "senso" del problema.
Uhm, credevo che nel serbatoio ci fosse solo abbastanza benzina per quel tragitto, non avevo capito che è anche il massimo che può trasportarne!
Devo correggiere, grazie per avermelo fatto notare!
Interessante questo.
Mi quadra che servono 11 jeep e di fatto ci sono infiniti modi per farlo con 11 jeep. Però quello che ottimizza dovrebbe essere unico, per l'esattezza supponendo che ogni jeep abbia benzina per percorrere tratti lunghi $1$, usando 11 jeep si dovrebbero percorrere tratti lunghi al massimo $3,0198$ circa. (In questo caso si vuole percorrere un tratto lungo $3$).
Mi quadra che servono 11 jeep e di fatto ci sono infiniti modi per farlo con 11 jeep. Però quello che ottimizza dovrebbe essere unico, per l'esattezza supponendo che ogni jeep abbia benzina per percorrere tratti lunghi $1$, usando 11 jeep si dovrebbero percorrere tratti lunghi al massimo $3,0198$ circa. (In questo caso si vuole percorrere un tratto lungo $3$).
Comunque chiedeva di dimostrare che non si possono usare meno di 11 jeep.
"xXStephXx":
...supponendo che ogni jeep abbia benzina per percorrere tratti lunghi $1$, usando 11 jeep si dovrebbero percorrere tratti lunghi al massimo $3,0198$ circa..
Come fai a dirlo?
La strategia che ho usato io è la seguente:
Ipotizzo che ogni jeep abbia benzina per fare $1$ metri e quindi si debbano percorrere $3$ metri, ci sono $n$ jeep. Il primo tratto che compiono tutte insieme è lungo $1/n$, a questo punto tutte le jeep avranno $(n-1)/n$ benzina. Una jeep dà la sua benzina alle altre $n-1$ jeep. Ogni jeep riceverà $((n-1)/n)/(n-1)$ benzina, quindi $1/n$ benzina e si avrà ancora $(n-1)/n+1/n=1$ benzina. Ripeto questa operazione ogni volta con le jeep rimaste. Salto qualche passaggio e arrivo a quando sono rimaste 3 jeep: percorrono $1/3$ metri e hanno tutte $2/3$ benzina, poi una dà la sua alle altre e rimangono due jeep con $1$ di benzina. Faccio $1/2$ metri e una dà la benzina all'altra che avrà $1$ benzina e farà l'ultimo $1/1$ metro.
Quindi il totale di metri percorsi sarà dato da:
$\sum_{i=1}^{n} 1/i$. Faccio prove sperimentali aumentando la $n$ fino a raggiungere un minimo di $3$ metri. Noto che per $n=10$ dà come risultato $2,92...$, mentre per $n=11$ dà proprio $3,019...$.
Quali sono gli infiniti metodi?
Ipotizzo che ogni jeep abbia benzina per fare $1$ metri e quindi si debbano percorrere $3$ metri, ci sono $n$ jeep. Il primo tratto che compiono tutte insieme è lungo $1/n$, a questo punto tutte le jeep avranno $(n-1)/n$ benzina. Una jeep dà la sua benzina alle altre $n-1$ jeep. Ogni jeep riceverà $((n-1)/n)/(n-1)$ benzina, quindi $1/n$ benzina e si avrà ancora $(n-1)/n+1/n=1$ benzina. Ripeto questa operazione ogni volta con le jeep rimaste. Salto qualche passaggio e arrivo a quando sono rimaste 3 jeep: percorrono $1/3$ metri e hanno tutte $2/3$ benzina, poi una dà la sua alle altre e rimangono due jeep con $1$ di benzina. Faccio $1/2$ metri e una dà la benzina all'altra che avrà $1$ benzina e farà l'ultimo $1/1$ metro.
Quindi il totale di metri percorsi sarà dato da:
$\sum_{i=1}^{n} 1/i$. Faccio prove sperimentali aumentando la $n$ fino a raggiungere un minimo di $3$ metri. Noto che per $n=10$ dà come risultato $2,92...$, mentre per $n=11$ dà proprio $3,019...$.
Quali sono gli infiniti metodi?
Quello che hai usato tu è quello che ottimizza.
Anzitutto si osserva che tutte le jeep viaggiano in parallelo, quindi tutte quelle ancora in moto consumano la stessa benzina e si deve cercare di ottimizzare la quantità totale di benzina disponibile (non importa com'è divisa tra le jeep).
All'inizio sono tutte in moto... supponiamo che le prime a fermarsi siano $k$ e si fermano tutte e $k$ contemporaneamente. ($k$ può anche valere $1$). Si dimostra che se le prime a fermarsi sono $k$, conviene che $k=1$ e che le altre jeep abbiano il serbatoio pieno. Infatti se $k!=1$ e alle altre $n-k$ jeep manca complessivamente $x$ benzina, allora la benzina totale usata è stata $k+x$ e la strada percorsa fino a quel momento è stata $(k+x)/n$ (poichè andavano tutte in parallelo).
Se invece la prima a fermarsi è unica e le altre sono cariche la benzina sprecata fino a quel momento è $1$ e la strada percorsa fino a quel momento è $1/n$. Per eguagliare la benzina sprecata nel caso di prima ci rimane ancora $k+x-1$.
Però stavolta viene usata da un numero di jeep minore o uguale a $n-1$ (dipende se nel frattempo se ne fermano anche altre) e quindi la strada percorsa prima di sprecare quella benzina sarà maggiore o uguale di $(k+x-1)/(n-1)$.
In entrambi i casi abbiamo consumato $k+x$ di benzina (conta solo la benzina totale) nel primo hanno percorso $(k+x)/n$ e nel secondo caso $ 1/n + (k+x-1)/(n-1)$. Chiaramente è maggiore la strada percorsa nel secondo caso, quindi conviene che la prima a fermarsi sia unica e tutte le altre siano ancora piene. E quindi si conclude come scritto da kobeilprofeta.
PS: per raggiungere un percorso lungo $3$ ci sono comunque infiniti modi perchè non è necessario ottimizzare, ad esempio quella $x$ può essere maggiore di $0$ purchè con moderazione, così come anche $k$ può essere maggiore di $1$.
Ad esempio le prime due jeep possono fermarsi contemporaneamente e in ogni passaggio ci sono infiniti modi per sprecare benzina
Anzitutto si osserva che tutte le jeep viaggiano in parallelo, quindi tutte quelle ancora in moto consumano la stessa benzina e si deve cercare di ottimizzare la quantità totale di benzina disponibile (non importa com'è divisa tra le jeep).
All'inizio sono tutte in moto... supponiamo che le prime a fermarsi siano $k$ e si fermano tutte e $k$ contemporaneamente. ($k$ può anche valere $1$). Si dimostra che se le prime a fermarsi sono $k$, conviene che $k=1$ e che le altre jeep abbiano il serbatoio pieno. Infatti se $k!=1$ e alle altre $n-k$ jeep manca complessivamente $x$ benzina, allora la benzina totale usata è stata $k+x$ e la strada percorsa fino a quel momento è stata $(k+x)/n$ (poichè andavano tutte in parallelo).
Se invece la prima a fermarsi è unica e le altre sono cariche la benzina sprecata fino a quel momento è $1$ e la strada percorsa fino a quel momento è $1/n$. Per eguagliare la benzina sprecata nel caso di prima ci rimane ancora $k+x-1$.
Però stavolta viene usata da un numero di jeep minore o uguale a $n-1$ (dipende se nel frattempo se ne fermano anche altre) e quindi la strada percorsa prima di sprecare quella benzina sarà maggiore o uguale di $(k+x-1)/(n-1)$.
In entrambi i casi abbiamo consumato $k+x$ di benzina (conta solo la benzina totale) nel primo hanno percorso $(k+x)/n$ e nel secondo caso $ 1/n + (k+x-1)/(n-1)$. Chiaramente è maggiore la strada percorsa nel secondo caso, quindi conviene che la prima a fermarsi sia unica e tutte le altre siano ancora piene. E quindi si conclude come scritto da kobeilprofeta.
PS: per raggiungere un percorso lungo $3$ ci sono comunque infiniti modi perchè non è necessario ottimizzare, ad esempio quella $x$ può essere maggiore di $0$ purchè con moderazione, così come anche $k$ può essere maggiore di $1$.
Ad esempio le prime due jeep possono fermarsi contemporaneamente e in ogni passaggio ci sono infiniti modi per sprecare benzina
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo