Don't take life too seriously: it's just a temporary situation

Parcheggio (problema del)

Geometria  Probabilità e statistica  Problemi 

Consideriamo una strada di lunghezza x, lungo la quale sono parcheggiate a caso auto di lunghezza unitaria. Ogni guidatore sceglie un punto a caso e vi parcheggia l’auto, se vi è abbastanza spazio, altrimenti sceglie un altro punto a caso e riprova; il procedimento si ripete sino a quando non vi sono più spazi lunghi almeno 1. Possiamo considerare come punto lungo la strada quello dove andrà a finire l’estremità anteriore della vettura e includere nella lunghezza della vettura lo spazio necessario per le manovre.

Supponendo per semplicità che x sia intero, parcheggiando in modo perfetto si occupa tutto lo spazio, mentre lasciando tra un auto e l’altra appena meno dello spazio necessario per un’altra vettura si spreca appena meno di metà dello spazio. Il problema del parcheggio consiste nello stabilire la frazione di spazio sprecata se ogni guidatore parcheggia a caso.

 

Alfréd Rényi dimostrò nel 1958 che il numero medio di auto parcheggiate alla fine m(x) soddisfa, per x ≥ 1, l’equazione Equazione per il numero medio di auto parcheggiate, che tende a Rx + R – 1 al crescere di x e quindi lo spazio sprecato tende a R, detta “costante di Rényi” e definita come Formula per la definizione della costante di Rényi.

 

Sono state anche considerate le varianti nelle quali ogni auto occupa n spazi o due auto possono parcheggiare a contatto, purché ciascuna abbia almeno uno spazio libero di una unità a una delle estremità, per poter manovrare (v. costante di Rényi).

 

Il problema tuttora irrisolto è la generalizzazione a due o più dimensioni.

In due dimensioni il problema può essere posto in questi termini: se in uno spazio rettangolare si posizionano a caso rettangoli identici non sovrapposti, tutti orientati allo stesso modo e con i lati paralleli al rettangolo contenitore, fino a che non è più possibile aggiungerne, che frazione dello spazio resta in media inutilizzata?

Nel 1960 I. Palasti avanzò la congettura, tuttora non dimostrata, che al crescere dello spazio la frazione inutilizzata tenda al quadrato della costante di Rényi.

Vedi anche

Costante di Rényi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.