[HOME - BASE Cinque - Appunti di Matematica ricreativa]
Un'automobile deve percorrere in senso antiorario un circuito
circolare. Il suo serbatoio è inizialmente vuoto. Sulla pista è però presente
l'esatta quantità di carburante necessaria al percorso distribuita in n
parti non necessariamente uguali.
Dimostrare che, comunque si dispongano gli n
rifornimenti nel circuito, esiste sempre un punto dal quale l'automobile può
partire e completare l'intero giro.
Si provi a generalizzare la proposizione al caso di n rifornimenti.
Il problema può essere semplificato affrontando alcuni casi particolari, ad esempio per n=2, 3.
Nota.
Questo problema è stato proposto al Forum del Progetto Olimpiadi della
matematica, il 25-07-2004 e al SIG GIOCHI del Mensa Italia. Sembra che sia stato
assegnato agli esami di ammissione al primo anno di ingegneria della Normale di
Pisa.
Una formulazione più dettagliata
Ringrazio Carlo Acerbi per la seguente formulazione del
problema spiegata nei minimi dettagli.
C'è un circuito automobilistico percorribile con una data macchina.
Si può percorrere il circuito solo in un senso. Ha forma arbitraria, saliscendi
e quant'altro che fanno sì che il consumo di benzina per unità di lunghezza
sia in generale diverso da punto a punto del circuito. Si sa però che per
compiere un giro del circuito è necessaria una certa quantità di benzina, che
indichiamo con X litri.
Questi X litri vengono distribuiti in un numero N>1 arbitrario di recipienti
posti a caso lungo il circuito. Si può pensare a dei distributori di benzina
disposti a caso sul circuito nei quali la somma della benzina in essi
disponibile è esattamente pari alla benzina necessaria a compiere un giro.
La macchina è vuota all'inizio e può partire da uno qualsiasi dei
"distributori", usando la benzina in esso disponibile. Ad ogni
successivo distributore - se ci arriva - la macchina carica la benzina e
prosegue. Chiaramente c'è il rischio che tra un distributore e il successivo la
benzina finisca. Se invece tutto va bene, la macchina riesce ad arrivare ad ogni
distributore e a completare il giro arrivando al distributore da cui era partita
consumando l'ultimissima goccia di benzina.
Le domande sono:
1) esiste sempre un distributore da cui partendo, la macchina riesce a
completare il giro ? Oppure esistono distribuzioni di benzina nelle quali
completare il giro partendo da qualsiasi punto è impossibile ? Dipende dalla
forma del circuito e dalla disposizione dei distributori ?
2) se esiste, il distributore da cui partire è unico ? e se esiste, come si
determina il punto da cui partire ?
Ultimo aggiornamento: marzo 2005
Questo problema può essere risolto in diversi modi.
Una elegantissima dimostrazione di esistenza del punto
iniziale
Questa soluzione è stata inviata da Alex.
Supponiamo che esista un rifornimento A tale da consentire di
raggiungere il rifornimento successivo B (partendo da A col serbatoio vuoto)
Allora partendo da A possiamo considerare A e B come un unico rifornimento
situato in A di dimensione A+B.
Due rifornimenti tali devono esistere, poiché se da ogni rifornimento non si
può raggiungere il rifornimento successivo, la benzina totale non coprirebbe
interamente il circuito.
Le condizioni sono le stesse di prima, ma c'è un rifornimento in meno.
Ripeto la cosa per induzione finché resta un solo rifornimento.
Una bella soluzione grafico-analitica
Questa soluzione è stata inviata da Carlo Acerbi
Supponiamo di partire in auto avendo una tanica di benzina di
dimensione sufficiente (basta X). Partiamo da un punto qualsiasi e disegniamo il
grafico del livello del serbatoio in funzione dei km percorsi. Il grafico
risulterà una spezzata del tipo:
Ad ogni rifornimento il livello salta di una quantità pari alla benzina caricata. Tra due rifornimenti successivi il livello decresce con una pendenza tanto maggiore quanto maggiore è il consumo su quel tratto.
(Qui abbiamo messo quantità casuali in ogni rifornimento e consumi casuali su ogni tratto – ma per semplicità abbiamo scelto che il consumo su ogni tratto fosse costante. L’assunzione non ha alcuna importanza. Nel caso più generale i segmenti obliqui sarebbero curvi anziché lineari, ma sempre decrescenti ovunque)
Nel caso generale la macchina non ce la farà a fare il giro. Nel caso del grafico ad esempio è evidente che la macchina si sarebbe arrestata al 170° km perché il livello della benzina si azzera. Tuttavia, con una tanica di riserva possiamo “barare” e completare il giro, tracciando il grafico fino alla fine. E’ quello che abbiamo fatto.
La spezzata finirà esattamente a zero a fine giro (qui il 300° km). Questo perché la benzina caricata è pari a quella usata.
La soluzione adesso è ovvia. Basta osservare che una curva di questo tipo avrà SEMPRE un minimo in corrispondenza di un distributore. Era quello il punto da cui si sarebbe dovuti partire. Nel caso in questione il distributore era al km 215. Infatti, partendo da quel distributore, e facendo lo stesso grafico è chiaro che si ottiene esattamente la stessa curva ma traslata verso l’alto di una quantità pari al massimo deficit della precedente, traslata in avanti di 215 km e con l’inizio e la fine incollati tra loro. Eccola: questa curva per costruzione non tocca mai lo zero se non alla fine, come ci aspettiamo. Rappresenta quindi la curva di una macchina che completa il giro senza bisogno di tanica di riserva.
Si conclude immediatamente che:
1) partendo da qualsiasi altro punto non si sarebbe completato il giro, perché la curva risultante avrebbe intersecato il livello zero. Quindi, se le quantità in gioco (distanze e quantità di benzina) sono davvero casuali, la soluzione sarà una sola perché il minimo della spezzata sarà uno solo a meno di coincidenze di probabilità zero. Partendo da qualsiasi distributore quindi non si completa il giro.
2) L’algoritmo macchina + tanica individua sempre la soluzione in modo univoco. E lo capisce anche un bambino.
3) Se le quantità di benzina sono distribuite in modo continuo, il metodo funziona lo stesso. La spezzata diventa una curva continua e per il teorema di Weierstrass ammette sempre un minimo su un supporto compatto (una circonferenza). Quindi anche in quel caso esiste tipicamente un solo punto geometrico da cui si deve partire, a meno di coincidenze o simmetrie.
Una soluzione "costruttiva"
Complimenti ad Alex che ci ha dato una dimostrazione di esistenza del
punto iniziale e a Carlo per la sua bella soluzione grafico-analitica.
Riporto qui sotto anche la mia soluzione algebrica. E' proprio vero che anche
nelle risoluzioni dei problemi matematici, ciascuno esprime il proprio stile e
le proprie preferenze.
Nelle seguenti considerazioni mostrerò anche un modo (ottimale?) per trovare un punto di partenza.
Vale l'uguaglianza:
A+B+C+...+N = a+b+c+...+n
----------------------
Parto da un punto qualsiasi, è quello che ho chiamato A'.
La sequenza dei rifornimenti e dei consumi è espressa dalla
seguente somma algebrica:
A-a + B-b + C-c + D-d + ... + N-n
I casi sono due:
1) Sono stato fortunato e non vado mai sotto zero, il problema è risolto.
2) Ad un certo punto vado sotto zero.
Supponiamo che vada sotto zero dopo una certa sequenza, ad
esempio:
A-a + B-b + C-c = -m1 (con m1 positivo)
Ciò vuol dire che:
1) nessuno dei punti A', B', C' va bene come punto di partenza
2) la somma algebrica dei restanti termini è m1
3) potrei completare il giro se nel punto A' avessi m1 carburante IN
PIU' di quello che c'è.
----------------------
A questo punto scarto la sequenza che non va e considero la restante parte:
D-d + E-e + F-f + ... + N-n = m1
Parto da D' e ripeto lo stesso ragionamento.
I casi sono due:
1) Non vado mai sotto zero, il problema è risolto. Infatti, giunto all'ultima
tappa (N-n) avrò m1 carburante che è proprio quello che mi serve
per riprendere da A' e completare il giro.
2) Ad un certo punto vado sotto zero.
Supponiamo che vada sotto zero dopo una certa sequenza, ad
esempio:
D-d + E-e + F-f = -m2 (con m2 positivo)
Ciò vuol dire che:
1) nessuno dei punti D', E', F' va bene come punto di partenza
2) la somma algebrica dei restanti termini è m1+m2
3) potrei completare il giro se nel punto A' avessi m1+m2
carburante IN PIU' di quello che c'è.
A questo punto scarto la sequenza che non va e considero la
restante parte:
G-g + H-h + I-i + ... + N-n = m1+m2
Se non vado mai sotto zero, il problema è risolto. Infatti,
giunto all'ultima tappa (N-n) avrò m1+m2 carburante che è proprio quello che
mi serve per riprendere da A' e completare il giro.
Se invece vado sotto zero ripeto il procedimento precedentemente descritto.
----------------------
Va bene, penso che si sia capito il procedimento.
Siccome il numero di tappe è n, numero finito, al massimo in n passaggi
troverò il punto buono per partire.
E alla fine (N-n) mi troverò con m1+m2+m3+...+mn
carburante che è proprio quello che mi serve per riprendere da A' e completare
il giro.
Sito Web realizzato da Gianfranco Bo