Hilbertův hotel Nekonečno

Od: Datum: 01.08.15 00:22 odpovědí: 8 změna: 04.08.15 18:25
Možná jste už někdo slyšel o Hilbertově hotelu Nekonečno. Jen jako připomínka, je to hotel s nekonečným spočetným počtem pokojů, které jsou všechny obsazeny. Postupně k němu přijíždí nový návštěvníci, kteří se chtějí ubytovat. A takhle jednou přijede k hotelu nekonečně mnoho vlaků, každý s nekonečným množstvím vagónů a ve všech je nekonečno sedadel (vždy spočetně). Já se ptám, jestli existuje nějaký vzorec, jak všechny ubytovat každého v jednom pokoji,tak, aby žádný pokoj nezůstal prázdný. A jestli existuje a někdo z vás, jenž čtěte tuhle otázku, ho zná nebo umí zjistit, ať ho sem pokud možno napíše.
Seznam odpovědí:
 
moment čekejte prosím, probíhá přenos dat...
Zobrazení struktury odpovědí v otázce
Skrytí struktury odpovědí v otázce
Zobrazení struktury odpovědí v otázce

 

Odpovědi na otázku:
Datum: 01.08.15 08:00
avatar

[ Obsah příspěvku byl skryt moderátorem z důvodu porušení pravidel poradny. ]

Ohodnoceno: 0x
 
Datum: 01.08.15 11:55
avatar

Nebuďte tak kategorický. Hilbert nebyl "muž jednoho výsledku".

Hilbertův hotel

Následující příklad uváděl svým studentům David Hilbert, aby jim ukázal, že běžná intuice může při práci s aktuálním nekonečnem velmi klamat.

Představme si hotel s nekonečným (spočetným) počtem pokojů. Na vrátnici tohoto hotelu přijde člověk, který se chce ubytovat, všechny pokoje však jsou již obsazené. Recepční však hosta nepošle pryč. Zato si zavolá pokojskou a nakáže jí, aby obešla všechny pokoje a každého z hostů požádala, aby se přestěhoval do pokoje s číslem o jedna vyšším, než v jakém dosud bydlel. Poté, co hosté udělají vše podle pokynů pokojské, jsou opět všichni ubytováni, ale navíc se uvolnil pokoj s číslem 1, kam se nyní může nastěhovat nově příchozí. Dokud chodí na vrátnici vždy jen konečné skupinky lidí, je vše v pořádku – pokojská vždy požádá hosty, aby se odstěhovali do pokojů s číslem o několik vyšším a požadovaný počet pokojů s nejnižšími čísly zůstane volný pro nové hosty. Jednoho dne však na vrátnici tohoto hotelu přijde nekonečně (spočetně) mnoho lidí najednou a všichni se chtějí ubytovat. Vrátný si se vzniklou situací neví rady, a tak zavolá majitele hotelu, aby tolika rozzuřeným hostům vysvětlil, že pro ně v hotelu již není místo. Hoteliér však dostane nápad. Opět vyšle pokojskou, aby obešla všechny pokoje, ale tentokrát má za úkol hostům vyřídit, aby se přestěhovali do pokoje s číslem dvojnásobným oproti tomu, v němž bydleli dosud. Tím se uvolní všechny pokoje s lichými čísly a všichni noví hosté se mohou pohodlně nastěhovat.

Ohodnoceno: 1x
 
Datum: 01.08.15 12:12
avatar

Musím si to promyslet, ale mám silný pocit, že to nepůjde.

Ohodnoceno: 0x
 
Datum: 01.08.15 15:28
avatar

Omlouvám se, kecám; samozřejmě to možné je.

Pžedvedu nejprve předpis, při kterém nekonečno pokojů zustane prázdných, což není to, na co se ptáte, ale teoreticky to zajišťuje, že existuje způsob, jak obsadit všechny. I takový "vzorec" bych uměl, ale to (zatím) nechám otevřené.

Nejprve si očísluju vlaky. Ale ne 1,2,3..., ale 2,3.5,... prostě n-tý vlak označím n-tám prvočíslem. Následně e vyhneme ubytovací kolizi tak, že vlaku, jehož identifikační prvočíslo je p1, přiřadíme pokoj, v jehož čísle je v prvočíselném rozkladu číslo p1 nejmenší.

Teď vagony: ty očíslujeme také prvočísly, ale počínaje prvním, které je větší než p; budiž to p2 a následují p3, p4, . A ubytováváme: prvnímu vagonu dáme pojoje, jejichž čísla jsou mocniny p1, Druhému pak pokoje s číslem p2. násobeným mocninami p1, atakdále.

Jak vidět, zůstane volný pokoj číslo jedna a také včechny pokoje, jejichř šísla obsahují v rozkladu na prvočinitele více než dvě prvočísla. Ale s tím si jistě poradíte

doplněno 01.08.15 18:27: oprava: že vlaku, jehož identifikační prvočíslo je p1, přiřadíme pokoje, v jeiichž čísle je v prvočíselném rozkladu číslo p1 nejmenší.
Ohodnoceno: 0x
 
Datum: 02.08.15 16:47
avatar

Vrátil bych se teď k postupu, který obsadí všechny pokoje.

Nejprve vyjdu z předpokladu, že hotel je prázdný; postup, který zvolím, bude trochu odlišný od toho, který jsem zkoušel minule. K očíslování vlaků použiju mocniny dvojky, k očíslování vagonů mocniny trojky; pasažérů ve vagonu bude spočetně, základní ošíslování bude 1., 2., 3.,... Takže číslo pasažéra trochu upravím, to zákládní číslo k rozložím na prvočínitele a v tomto rozkladu s-té prvočíslo nahradím s+2-tým prvočíslem. Tedy třeba 1 zůstane beze změny, 2→ 5, 3→ 7, 4 = 2*2 → 5*5=25, 5 → 11, 6→ 35 atd.; takto upravené číslo k označím třeba k , No a teď už stačí k-tému pasažéru j-tého vagonu i-tého vlaku přiřadit pokoj číslo 2(i–1)*3(j–1)*k a je to.

Pokud bych měl ty vlaky ubytovat v plném hotelu, tak bych nejprve nechal stávající hosty přestěhovat do pokoje s dvojnásobným číslem, čímž bych uvolnil liché pokoje, a následně bych mírně modifikoval právě popsanou akci s tím, ře bych zapomněl na dvojku, v číslování vlaků a vagonů bych ji nahradil trojkou a trojku čtyřkou a v rozkladu na prvošinitele byk s-té prvočíslo nahradil s+3-tým.

Ohodnoceno: 0x
 
Datum: 04.08.15 10:25
avatar

Jinak standardní postup při "spočítání" (ubytování) nekonečna nekonečen spočívá v tom, že se očíslují po vedlejší diagonále. Na příkladu jednoho vlaku by to vypadalo tak, že pasažéry očísluji dvěma indexy, (první bude číslo vagonu a druhý číslo pasažéra) a pak je budu "ubytovátat" v tomto pořadí: a1,1, a1.2, a2,4, a1,3, a2,2, a3,1,..., tedy skupinu dělám podle stoupajícího součtu indexů a uvnitř té skupiny pak uspořádám podle prvního indexu. Když takhle očísluji každý vlak, tak následně mohu (indukcí) aplikovat stejný postup na nekonečno vlaků, jejichž pasažéry mám už "seřazeny do jednoho vagonu". To je ovšem spíš teoretický důkaz, že přijelo spočetně mnoho lidí, ale "ubytovací vzorec" v tom zrovna nevidím.

doplněno 04.08.15 16:51: Tam jsem se jednou přepsal v indexech, má být a1,1, a1.2, a2,1, a1,3, a2,2, a3,1,...
Ohodnoceno: 0x
 
Od: hm®
Datum: 04.08.15 17:42
avatar

Propánakrále, co ty lidi nevymyslej!? *ee* :)

Ohodnoceno: 0x
 
Datum: 04.08.15 18:25
avatar

To je prostě teorie kardinálních čísel čili mohutností. Prostě srovnávání velikostí nekonečných množin. "Nejmenší" nekonečná množina je množina přirozených čísel, jejíž mohutnost označujeme alef nula, a takové množiny se nazývají spočetné. Obecně říkáme, že dvě množiny mají stejnou mohutnost, jestliže existuje vzájemně jednoznačné prosté zobrazení jedné na druhou. U konečných množin to znamená, že mají stejný počet prvků, a pokud budu přiřazovat prvky jedné množiny prvkům množiny druhé, tak ty obrazy vždy vyčerpají celou cílovou množinu; třeba když vyprodám sál, tak ke každému lístku patři jedna židle a žádné nezbyde. Pokud by nějaká zbyla, nebyl by sál vyprodaný, pokud by se nějaké nedostávalo, bylo by lístků víc něž židlí a asi by některé byly falešné.

Právě takovéhle úvahy typu hotel Nekonečno ukazují, že při práci s nekonečnými množinami to není tak jednoduché. Tam je možné, že dvě množiny mají stejnou mohutnost (hotel je plně obsazen), a přesto může existovat prosté zobrazení jedné množiny do druhé, které tu druhou nevyčerpá (v původně plně obsazeném hotelu snadno uvolníme jeden, dva, deset nebo i nekonečno pokojů, aniž bychom museli nejaké hosty z hotelu vyhodit). Přesto existují možiny různých mohutností. Množina A má menší mohutnost než množina B ("má méně prvků", řečeno názorně), jestliže existuje zobrazení množiny A do množiny B (což ovšem může nastat i v honelu Nekonečno posunutím hostů o sedm pokojů), ale, a to je podstatné, neexistuje zobrazení A na celou B. Příkladem je množina reálných čísel; ta má větší mohutnost než mnořina přirozených čísel, reálná čísla nelze "spočítat", rozuměj seřadit do posloupnosti. (Naproti tomu množina racionálních čísel je spočetné; i když na první pohled vypadá větší, očíslovat se dá.)

A k čemu to je? Samozřejmě chleba pro to nebude levnější, v tom smyslu to není k ničemu, ale například odsud plyne existence transcendentních čísel, aniž bychom nějaké museli najít. Transcendentní čísla jsou taková, která nejsou algebraická, tj, nejsou kořenem žádné algebraické rovnice s celočíselnými koeficienty. Takové je například číslo pí nebo zákllad přirozených logaritmů e. Ovšem dokázat to o nich vůbec není peříčko. Ale poměrně snadno (podobnou úvahou jako s těmi vlaky) se dá dokázat, že množina čísel algebraických je spočetné a tudíž ne jen jedno či dvě čísla, ale přímo nespočetně čísel je transcendentních.

Ohodnoceno: 1x
 

 

 

 

 

Přihlásit se k odběru odpovědí z této otázky:

Neneseme odpovědnost za správnost informací a za škodu vzniklou jejich využitím. Jednotlivé odpovědi vyjadřují názory jejich autorů a nemusí se shodovat s názorem provozovatele poradny Poradte.cz

 
Copyright © 2004-2016 Poradna Poradte.cz. Všechna práva na poradně Poradte.cz vyhrazena.