Hilbert Grand Hotel-paradoxonja

A Wikipédiából, a szabad enciklopédiából


A végtelen mennyiségek paradox viselkedését demonstrálja a Grand Hotel-paradoxon, amely a német matematikus, David Hilbert nevéhez fűződik.

A Grand Hotel-paradoxon[szerkesztés | forrásszöveg szerkesztése]

Az alapprobléma[szerkesztés | forrásszöveg szerkesztése]

Egy valódi hotelben ha minden szobát kiadnak, akkor nem tudnak több vendéget elhelyezni, ebben nincs semmi meglepő. De képzeljünk el egy olyan szállodát, amelynek végtelen sok szobája van, azaz a szobaszámok 1-től kezdve folyamatosan növekednek, és nincs olyan szoba, amelynél ne lenne nagyobb számú. A szállodának van egy hangosbemondórendszere is, amelyen keresztül a portás az összes szobavendégnek tud üzenni egyszerre. Tegyük fel, hogy egy ilyen hotelben az összes szoba megtelt, olyan sok vendég van. A kérdés, hogy ha jön még egy vendég, el kell-e küldeni. A meglepő válasz az, hogy nem. Az új vendég elhelyezéséhez a portásnak csak annyit kell tennie, hogy bemondja: minden vendég költözzön át az eggyel nagyobb számú szobába. Az a vendég, aki eddig az 1-es szobában lakott, átköltözik a 2-esbe, amelynek eddigi lakója a 3-asba megy át, és így tovább. Így az 1-es szoba felszabadul, és az új vendég beköltözhet.

Végtelen sok vendég[szerkesztés | forrásszöveg szerkesztése]

Talán még ennél is meglepőbb, hogy nem csak egy vendéget, hanem végtelen sok vendéget is el lehet helyezni. Tegyük fel ugyanis, hogy érkezik egy autóbusz, amelynek a szállodához hasonlóan végtelen sok ülése van, és a busz is tele van. A portás ekkor arra kéri a szállóvendégeket a hangosbemondóján keresztül, hogy költözzenek a szobaszámuk kétszeresét viselő szobába. Az 1-esben lakó tehát a 2-esbe költözik, az a 4-esbe, a 3-as a 6-osba stb. Ezzel az összes páratlan számú szoba felszabadult, ezekbe pedig sorban beköltözhetnek a busz utasai, az 1-es ülésen ülő az 1-esbe, a 2-esen ülő a 3-asba, és így tovább.

Végtelenszer végtelen sok vendég[szerkesztés | forrásszöveg szerkesztése]

De még ennél is szerencsésebb a helyzet, ugyanis akár végtelen sok végtelen kapacitású busz vendégeit is mind el lehet helyezni. Egy lehetséges megoldás, hogy a portás ugyanazt mondja be, mint előbb, majd az első busz utasait a 3n számú szobákba költözteti (ahol n az ülés száma), a második busz utasait az 5n számú szobákba, a harmadik busz utasait a 7n számúakba, és így tovább, az i-edik busz utasait a pin számúba, ahol pi az i+1-edik prímszám. Vegyük észre ugyanis, hogy a prímszámok hatványai mindig páratlanok (tehát már bentlakó szállóvendégekkel nem lesz ütközés), és különböző prímszámok hatványai mindig különbözőek (tehát a beköltözők között sem lesz konfliktus). Így ráadáasul még üres szobák is maradnak szép számban, örülhet a portás!

Végtelen sok busz utasainak egy lehetséges rendezése

Vegyük észre, hogy azzal, hogy az utasokhoz egész számokat (prímhatványokat) rendeltünk, tulajdonképpen egyetlen végtelen sorba állítottuk őket, és visszavezettük a feladatot az előzőre, amikor csak egy buszunk volt. Ilyen sorbaállítás sokféleképpen lehetséges. Az egyik, más bizonyításoknál is előszeretettel alkalmazott mód, hogy sorban egymás alá felírjuk a buszok utasait, majd egy spirálvonallal összekötjük őket. A vonal mentén végighaladva egyértelműen megkapjuk a sorrendet (ld. ábra).

Ismeretlen számú késői látogató[szerkesztés | forrásszöveg szerkesztése]

Még a következő kínos helyzetet is meg tudja oldani a portás (feltéve, hogy elég okos): kap egy telefonhívást, hogy az éjszaka közepén egy busszal vendégek érkeznek. Szerencsére véges sok vendég jön, viszont egymás melletti szobákban akarnak aludni. Sajnos nem tudják megmondani, hogy hányan jönnek, és a portásnak előre intézkednie kell, hogy mindenképpen egymás melletti szobákban legyenek elszállásolva. Persze a vendégeket éjszaka már nem lehet zavarni, így az egész költöztetést még este le kell bonyolítani.

Kicsit átfogalmazva ez azt jelenti, hogy úgy kell a vendégeket átköltöztetni, hogy legyen akárhány szomszédos üres szobából álló szekció. Ha a portás a következő utasítást adja, akkor ez a feltétel teljesül: Mindenki tegye a szobaszámát 2 kitevőjébe, és költözzön át az így kapott számú szobába. Vagyis, aki eddig az n-edik szobában lakott az most elköltözik a 2n sorszámú szobába. Könnyen igazolható, hogy a kettőhatványok között tetszőlegesen nagy hézagok vannak. (Az n-edik szoba lakóit küldhettük volna az n-edik prímszám sorszámú szobába is, de akkor sokat kellett volna számolniuk a vendégeknek, és a megoldás helyessége is kicsit nehezebben bizonyítható. Vagy küldhettük volna őket az n2 sorszámú szobába is. A négyzetszámok között is tetszőlegesen nagy hézagok, a páratlan számok vannak.)

Paradoxon?[szerkesztés | forrásszöveg szerkesztése]

Az itt leírtak nem rejtenek ellentmondást, csak a józan észnek mondanak valamelyest ellent. Nehéz ugyanis megszokni, hogy végtelen sok dolog csoportjairól gondolkodjunk, és nehéz elfogadni, hogy az ilyen csoportok tulajdonságai és viselkedése bizony gyakran eltér véges sok dolog csoportjainak tulajdonságaitól és viselkedésétől. Egy valódi szállodában a páratlan számú szobák száma nyilvánvalóan kisebb, mint az összes szoba száma. Hilbert Grand Hoteljének esetében azonban ez a két mennyiség megegyezik: mindkettő megszámlálhatóan végtelen. Ezt a mennyiséget a matematikában \aleph_0-lal jelöljük. Ilyen számosságú minden halmaz, amelynek elemei kölcsönösen egyértelműen megfeleltethetők a természetes számok halmazának. A Hotel esetében a portás instrukciója a költözésre pontosan ez a megfeleltetés.

A Grand Hotel és a teljes indukció[szerkesztés | forrásszöveg szerkesztése]

A Grand Hotel kapcsán azt is szemléltetni lehet, hogy a teljes indukció, a bizonyítás egy előszeretettel alkalmazott módszere csak egy irányba működik, és feltétlenül szükség van hozzá egy nulladik lépésre. Tegyük fel ugyanis, hogy a szállodában nem szabad dohányozni, sőt, szivart még behozni sem szabad. Ennek ellenére egy megtelt szállodában minden vendégnél van egy-egy szivar. Hogyan lehetséges ez? Az 1-es szobában lakó vendég a 2-esben lakótól kapta. Az viszont kettőt kapott a 3-as lakójától, egyet megtartott magának, egyet továbbadott. A 3-asban lakó hármat kapott a 4-es szoba vendégétől, aki viszont négyet kapott, és így tovább. Nem jutunk ellentmondásra, a bizonyítás mégis hibás, mert hiányzik az indukció nulladik lépése, annak előfeltétel nélküli igazolása, hogy valakinél valamikor kellő számú szivar volt.

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]