Zibaldone Scientifico: 216. Hilbert’s Hotel

lunedì 22 agosto 2016

216. Hilbert’s Hotel

Prima o poi, in un blog che si rispetti, si deve parlare di questo paradosso. E visto che ci sono molti blog degni di rispetto, basta scrivere su un motore di ricerca alcune parole chiave, per trovare un’infinità di post che parlano di questi argomenti. Quel che faremo qui è di esporre i diversi approcci utilizzati per risolvere brillantemente le varie situazioni che si presentano di volta in volta.

http://www.delcampe.net/

Immaginate un hotel (che chiameremo hotel di Hilbert) con infinite stanze tutte occupate.

Caso 1 - Arriva un nuovo cliente. L’arguto albergatore pensa: non c’è problema; metto il nuovo ospite nella stanza che desidera e sposto nella stanza successiva alla loro tutti gli occupanti delle varie stanze. In questo semplice esempio, se il nuovo ospite sceglie la stanza numero 1, basterà spostare l'ospite della 1 nella 2, quello della 2 nella 3, ecc.; essendo un hotel infinito è possibile trovare una soluzione.

Caso 2 - Dopo un’ora arriva un autobus con infiniti nuovi ospiti. L’arguto albergatore pensa: basta spostare ogni ospite nella stanza con numero doppio rispetto a quello attuale (dalla 1 alla 2, dalla 2 alla 4, ecc.), lasciando ai nuovi arrivi tutte le camere con i numeri dispari, che sono anche esse infinite. Problema risolto.

Ma non è finita qui.

Caso 3 - Il giorno dopo arrivano infiniti autobus (tutti numerati) ed ognuno di questi contiene infiniti passeggeri (che siedono su sedili anch’essi numerati).

A questo punto la faccenda sembra farsi complicata, ma anche in questo caso esiste una soluzione, anzi esistono almeno 5 modi diversi di risolvere la questione:

Modo 1

Che i numeri primi siano infiniti, fu dimostrato da Euclide in una delle più belle dimostrazioni matematiche, e non è complicato rendersi conto che qualsiasi potenza di un primo è divisibile solo per il numero primo stesso. Per cui se poniamo i clienti attualmente residenti nelle camere con numero uguale alle potenze di 2 e i vari autobus in quelle corrispondenti alle potenze dei successivi primi. Cioè, indicando con k il numero della stanza o del sedile occupato, basta seguire questa semplice regola:

ospiti residenti andranno nella camera 2^k es. da camera 7 a camera 128
primo autobus andranno nella camera 3^k es. da posto 4 a camera 81
secondo autobus andranno nella camera 5^k es. da posto 3 a camera 125
terzo autobus andranno nella camera 7^k es. da posto 5 a camera 16807

Questo modo ha il difetto di lasciare libere troppe camere. Ad esempio: 6, 10 e tutte le camere scomponibili in numeri primi differenti, non saranno occupate.

Modo 2

Nel libro “La piccola bottega delle curiosità matematiche del professor Stewart” viene suggerito di iterare il procedimento utilizzato in precedenza per sistemare un solo autobus, per ogni autobus che si deve sistemare. L’inconveniente in questo caso è che ogni ospite dovrà continuare a spostarsi.

Modo 3

Posto k, autobus j, va in 2^j(2k -1)

residenti, vanno nella camera 2⁰ (2k -1) es. da camera 7 a camera 13
primo bus, vanno nella camera 2¹ (2k -1) es. da posto 4 a camera 14
secondo bus, vanno nella camera 2² (2k -1) es. da posto 3 a camera 20
terzo bus, vanno nella camera 2⁴ (2k -1) es. da posto 5 a camera 144

Modo 4

Immaginiamo l’hotel di Hilbert come un classico hotel (ma infinito). Le infinite camere k sono posizionate lungo gli infiniti corridoi j e in infiniti livelli (o piani) p (immaginate un cubo infinito). Possiamo anche complicare ulteriormente la questione, cioè pensare che arrivino infinite persone, su infiniti autobus e per infiniti giorni. Basterà dire loro di recarsi nel corridoio corrispondente al numero del loro autobus, al livello relativo al giorno e applicare il caso 2 visto in precedenza.

Esempio: il primo giorno, il quarto passeggero del terzo autobus, andrà a sistemarsi nella camera numero 7, del terzo corridoio (III), al livello 1 (corridoio giallo).

Modo 5

Per diagonali, utilizzato nella pagina di Wikipedia: “Paradosso del Grand Hotel di Hilbert”. Il metodo si capisce subito osservando l’illustrazione riportata nel post messicano: http://masciencia.org/blog/bienvenidos-al-hotel-hilbert

Il celebre paradosso del Grand Hotel è stato inventato dal grande matematico David Hilbert negli anni ’20 e, come commentato in Wikipedia: “Questo paradosso, nonostante sia piuttosto elementare, ha contribuito, all'epoca ai matematici, ed oggi ai profani, a far comprendere la differenza profonda e sostanziale tra gli insiemi finiti e infiniti…”.

Come detto all’inizio, esistono molti post che parlano di questo paradosso e sono presenti in rete anche molti interessanti video come questo di Jeff Dekofsky: