Il problema:

I Rudi stanno ricostruendo RUDI “Robot Ultralento Decisamente Inutile” che dovrà circumnavigare il Pianeta Rosso seguendo la linea dell’equatore (in realtà dovrà solo fare un girotondo in giardino). Il robot è dotato di un serbatoio capace di contenere tutto il carburante necessario (facendo dei rapidi conti, anche ammettendo che sia talmente efficiente da percorrere 100 Km con un litro di carburante, sarebbe necessaria una capienza di oltre 200 litri) ma sarà fatto atterrare con il serbatoio vuoto vicino ad uno degli N distributori che si trovano lungo l’equatore ciascuno con capacità diverse e distribuiti in modo casuale. La scelta del distributore dove far atterrare RUDI sarà effettuata dopo aver studiato la loro posizione definitiva.
Bisogna capire quale sia la probabilità che, con una distribuzione casuale sia dei distributori sia della loro capacità, la circumnavigazione di Marte sia possibile.

Soluzione:

Scegliendo in modo opportuno il distributore dal quale partire, è sempre possibile effettuare la circumnavigazione.

Spiegazione:

Possiamo dire che, partendo da un distributore scelto a caso, se in un determinato tratto si rimane a secco, significa che, partendo dal deposito successivo si ha a disposizione, per raggiungere il distributore iniziale, una quantità di carburante in più, proprio uguale a quella che mancava nel tratto precedente. Continuando con l’analisi si arriverà a considerare un distributore dal quale si può raggiungere quello iniziale senza mai rimanere a secco e avendo ancora nel serbatoio esattamente la quantità di carburante necessaria per colmare le carenze successive.

Una spiegazione formale è fornita qui

La spiegazione precedente fornisce anche un algoritmo per determinare il distributore di partenza.

Di seguito c'è una simulazione.

Bisogna selezionare il numero di distributori ed il software imposta (quasi casualmente) la distanza tra i distributori e la loro capienza (per semplicità si considera la distanza complessiva da coprire come 100 volte la capienza totale dei distributori).