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

Rényi (costante di)

Geometria  Probabilità e statistica 

La costante di Rényi, detta anche “costante del parcheggio” trae la sua origine dalla soluzione di un problema pratico.

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 Un mezzo dello spazio, ma che succede parcheggiando 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 Limite cui tende la frazione di spazio sfruttata, dove Formula per la definizione della costante di Rényi è da allora detta “costante di Rényi”.

In termini pratici il teorema indica che se non si predispongono spazi segnati, si spreca in media poco più di Un quarto dello spazio.

 

Alla voce espansione di Engel si trova un’ottima approssimazione della costante di Rényi.

Qui trovate le prime 100 cifre della costante di Rényi (Eric W. Weisstein, The Online Encyclopedia of Integer Sequences, http://oeis.org).

 

La costante può anche essere calcolata come: Formula per il calcolo della costante di Rényi;

 

Nel 1964 A. Dvoretzky e H. Robbins dimostrarono che la varianza di m(x) / x tende a Limite cui tende la varianza di m(x) / x, dove R1(x) = m(x) – Rx – R + 1 e R2(x) vale (1 – R – Rx)2, per x da 0 a 1 e Formula per la definizione di R2(x), per x > 1. Questo significa che in genere lo spazio sprecato sarà sempre piuttosto vicino a Un quarto.

 

H. Solomon studiò una variante del problema, nella quale si permette al guidatore che non trova posto nel punto prescelto di spostarsi verso l’estremità più vicina del veicolo che occupa il posto e parcheggiare a contatto di questo.

Questo algoritmo migliora l’utilizzo del parcheggio, come è logico aspettarsi, portando il limite della frazione utilizzata a Limite cui tende la frazione di spazio sfruttata.

Qui trovate le prime 101 cifre della costante (Jean-François Alcover, The Online Encyclopedia of Integer Sequences, http://oeis.org).

 

Quindi se si parcheggia a caso si utilizza poco meno di Tre quarti dello spazio, mentre un minimo sforzo per accostarsi alle auto già presenti permette di arrivare a oltre Quattro quinti. Conviene dunque disegnare righe sul terreno, in modo da fissare le posizioni nelle quali le auto devono essere lasciate, per arrivare all’utilizzo ottimale. Da notare che nel caso reale le differenti lunghezze dei veicoli complicano non poco il problema.

 

Se vengono predisposti spazi corti e ogni vettura ne occupa esattamente n, la frazione di spazio sprecato tende a Limite cui tende la frazione di spazio sprecata, che è 0 per n = 1, per n = 2 vale Limite cui tende la frazione di spazio sprecata per n = 2, per n = 3 vale Limite cui tende la frazione di spazio sprecata per n = 3 e continua a crescere al crescere di n, tendendo a 1 – R per n tendente a infinito.

 

Nel 2005 Michael L. Gargano, Arthur Weissenseel, Joseph F. Malerba e Marty Lewinter considerarono un’altra variante, nella quale gli spazi per parcheggiare sono segnati e contigui, ma a ogni veicolo serve uno spazio libero, davanti o dietro, per manovrare. Due veicoli possono quindi occupare due spazi contigui, a condizione che i due spazi alle altre estremità siano liberi. Gli spazi adiacenti alle estremità del parcheggio non sono considerati disponibili per la manovra.

Il problema resta quello di determinare la quantità di spazio occupata in media, supponendo che chi arriva scelga a caso uno spazio libero, ma sempre in modo di non bloccare un veicolo già parcheggiato, occupando sia lo spazio precedente, che quello seguente.

 

Per parcheggi con pochi spazi è possibile calcolare lo spazio mediamente occupato, considerando tutte le possibili sequenze di parcheggio. La tabella seguente mostra i risultati per parcheggi da 1 a 15 posti.

Numero di spazi

Numero medio di auto parcheggiate

Frazione media di spazio occupata

1

1

1

2

1

1 / 2

3

5 / 3

5 / 9

4

2

1 / 2

5

43 / 15

43 / 75

6

67 / 20

67 / 120

7

1243 / 315

1243 / 2205

8

15401 / 3360

15401 / 26880

9

697 / 135

697 / 1215

10

5232119 / 907200

5232119 / 9072000

11

31780169 / 4989600

31780169 / 54885600

12

39736579 / 5702400

39736579 / 68428800

13

2945813593 / 389188800

2945813593 / 5059454400

14

6594480509 / 807206400

6594480509 / 11300889600

15

477838232177 / 54486432000

477838232177 / 817296480000

Non si conosce un’espressione per il limite cui tende la frazione media di spazio occupata; il calcolo indica che sembra tendere a circa 0.598.

 

Il problema del parcheggio è stato oggetto di studi approfonditi, perché ha importanti applicazioni in fisica, chimica, nella scienza dei materiali, nei modelli di liquidi, e addirittura in informatica.

 

Sono importanti anche le generalizzazioni a 2 dimensioni (che possiamo considerare come il problema di parcheggiare auto rettangolari in piazzali rettangolari) e oltre, ma per essi non si conoscono ancora soluzioni esatte.

Nel 1960 I. Palasti avanzò la congettura che Limite cui tende la frazione di spazio sfruttata.

Contattami

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