I rompicapi di Alice: C'è posto sull'ascensore?

Gli ascensori sono stati uno dei primi elementi di discordia ne Il condominio di JG Ballard. In una lettura un po' più ottimistica per come sono andate le cose nel romanzo, si potrebbe dire che se i componenti del condominio fossero stati più addentro alla cultura matematica, probabilmente le cose sarebbero andate diversamente, perché magari sarebbe stato loro noto il famoso paradosso dell'ascensore.

Su e giù dai piani

Progetto di un ascensore di Konrad Kyeser
del 1405 - via commons

Il paradosso venne per la prima volta formulato nel 1958 da George Gamow e Marvin Stern nel loro libro di matematica ricreativa Puzzle-Math. I due lavoravano nello stesso edificio, ma su due piani diversi: Gamow al secondo piano di un palazzo di sette e Stern al sesto piano. Visto che i due collaboravano, a volte uno prendeva l'ascensore per andare nell'ufficio dell'altro. Così quando Gamow andava da Stern, notava che 5 volte su 6 l'ascensore che si fermava al suo piano proveniva dai piani alti, mentre l'ascensore che si fermava al piano di Stern l'ascensore all'incirca 5 volte su 6 proveniva dai piani bassi⁽²⁾.
Il problema venne successivamente ripreso da Donald Knuth prima nel 1969 nell'articolo The Gamow-Stern elevator problem uscito sul Journal of Recreational Mathematics. Il primo passo è abbastanza banale, ed è spiegato anche nel libro di Gamow e Stern: nel caso di un palazzo con un ascensore, la probabilità che l'ascensore si trovi sopra o allo stesso piano di Gamow è 5/6, mentre la probabilità che si trovi sotto è 1/6. Allo stesso modo per Stern la probabilità che l'ascensore si trovi sotto o al suo stesso piano è 5/6, mentre la probabilità che si trovi al di sopra è 1/6. E' qui, però, che Gamow e Stern commettono un errore, almeno secondo l'analisi compiuta successivamente da Knuth: le probabilità restano le stesse anche se aumentiamo il numero di ascensori⁽²⁾.
Secondo Knuth, invece, bisogna prendere in considerazione le probailità condizionate. Innanzitutto il matematico definisce la unbiased portion, la porzione imparziale. Supponiamo che l'ascensore si trovi al quarto piano. Questo va giù fino al primo piano e poi risale fino al secondo, percorrendo i $4/12 = 1/3$ del percorso totale dell'ascensore. Durante la prima parte del percorso, l'ascensore si ferma al secondo piano quindi scende giù e risale fermandosi nuovamente al secondo piano. Questo percorso è detto porzione imparziale.
Knuth, a questo punto, si pone nella situazione in cui ci sono $n$ ascensori e distingue tra due casi:

1. Nessun ascensore è nella porzione imparziale. La probabilità di ciò è $(2/3)^n$, poiché la probabilità di ciascun ascensore di non essere nella porzione imparziale è $2/3$. Questo vuol dire che il prossimo ascensore che si fermerà al secondo piano, scenderà verso il basso.
2. Almeno un ascensore si trova nella porzione imparziale. In questo caso la probabilità è $1 - (2/3)^n$ e questo vuol dire che il prossimo ascensore che raggiungerà il secondo piano avrà probabilità $1/2$ di scendere.

Combinando questi due risultati si ottiene una probabilità di \[\left ( \frac{2}{3} \right )^n + \frac{1}{2} \left (1 - \left (\frac{2}{3} \right )^n \right ) = \frac{1}{2} + \frac{1}{2} \left ( \frac{2}{3} \right )^n\] che il primo ascensore ad arrivare al secondo piano vada verso il basso. Se nel palazzo ci sono due ascensori, tale probabilità risulta essere di $13/18$ che è leggermente più bassa rispetto ai $5/6$ di un solo ascensore, a tutto vantaggio di Gamow. La probabilità si abbatte velocemente con sette ascensori, arrivando a $2315/4374$, non molto lontana da $1/2$⁽²⁾.
Se si definisce come $p$ la distanza di un dato piano dal piano terra diviso il numero di piani che separano il piano terra dalla cima, allora è possibile generalizzare la formula come segue: \[\frac{1}{2} + \frac{1}{2} \left (1-2p \right ) \left | 1-2p \right |^{n-1}\] In particolare nel caso del palazzo di Gamow e Stern, $p_G = 1/6$, mentre $p_S = 5/6$.
Conseguenza delle formule di Knuth è che nel limite di infiniti ascensori, la probabilità che l'ascensore arrivi dall'alto o dal basso è esattamente di $1/2$^{(2, 1)}.

Un po' d'ordine, please!

Sempre Donald Knuth, questa volta nel 1973 nel terzo volume di The art of computer programming, propone un nuovo problema con gli ascensori, anzi con un ascensore. Un palazzo di $n$ piani contiene a ciascun piano $c$ persone. Per andare da un piano all'altro ci si sposta tramite un ascensore che può portare un massimo di $b$ persone. Il palazzo è pieno, ovvero nel palazzo ci sono $c \, n$ persone. Inoltre si definisce viaggio unitario lo spostamento dell'ascensore da un piano a quello superiore o inferiore. Ogni abitante del palazzo vuole spostarsi a un piano differente rispetto a quello in cui si trova. Il problema è, allora, trovare il numero minimo di viaggi unitari necessari per l'ascensore per accontentare tutti gli abitanti del palazzo.
A questo punto, detto $k$ il numero del piano, si definisce $u_k$ il numero di abitanti del piano $k$ o di quelli inferiori che vogliono salire a un piano superiore rispetto a $k$, mentre $d_k$ il numero di abitanti del piano $k$ o di quelli superiori che vogliono scendere a un piano superiore. Per determinare il numero minimo di viaggi dell'ascensore, si andrà a calcolare per ciascun piano con approssimazione per eccesso il rapporto $u_k / b$ e $d_k / b$.
Mettiamo alla prova l'algoritmo di Knuth con un caso semplice, quello di un palazzo di 5 piani con un ascensore a 2 posti. Vediamo lo schema qui sotto⁽²⁾:

Esaminiamo un paio di righe, partendo dal 5.o piano. Ovviamente $u_k / b = 0$ visto che nessuno vuole andare oltre il 5.0 piano, mentre $d_k / b = 3/2$ visto che tutti vogliono andare a un piano inferiore o uguale al 5.o. Questo vuol dire che l'ascensore non farà alcun viaggio verso l'alto (terza colonna della tabella) e due viaggi verso il basso (quarta colonna della tabella).
Vediamo il 3.o piano. In questo caso $u_k / b = 5/2$ poiché al terzo piano ci sono 3 abitanti che vogliono andare oltre il 3.o piano, al secondo piano c'è un abitante che vuole andare al quarto, e al primo piano c'è un abitante che vuole anch'esso raggiungere il quarto. Gli abitanti che vogliono scendere, invece, sono nessuno al terzo piano, uno al quarto (vuole raggiungere il primo piano) e due al quinto (uno vuole andare al secondo e l'altro al primo) per un totale di 3 e dunque $d_k / b = 3/2$. Questo vuol dire che l'ascensore farà 3 viaggi verso l'alto e 2 viaggi verso il basso per un totale di 5.
Fatti tutti i conti su tutti i piani alla fine si scopre che lo schema di esempio si risolve con 18 viaggi⁽²⁾.
Sempre nel terzo volume del suo volume, Knuth propose un terzo rompicapo sugli ascensori, basato su alcuni risultati di Robert Floyd che cercava un algoritmo di ottimizzazione per la risistemazione dei dati all'interno di una memoria magnetica. In questo caso, partendo dallo schema in figura (un palazzo di 6 piani con 6 abitanti a ciascun piano), bisogna determinare il numero minimo di viaggi dell'ascensore, che in questo caso può trasportare 6 abitanti alla volta, per ordinare le persone secondo i loro desideri.
Mentre Knuth risolse il rompicapo in 12 passi, i lettori di Martin Gardner gli inviarono soluzioni che prevedevano 11 passi².

---

1. Gardner, M. (1973). Mathematical Games: Up-and-down elevator games and Piet Rein's mechanical puzzles. Scientific American, 232(1), 110-117. doi:10.1038/scientificamerican0273-106 (jstor) ↩
2. Gardner, M. Elevators. Ch. 10 in Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, pp. 123-132, 1986. ↩↩↩↩↩↩↩