MATEMATIKA Dobrodošli v Hotelu neskončno1 nU vU NU Tilen Lušovnik, Špela Pušnik, Tisa Ževart in Jana Vidrih (mentorica) -> Tretji teden avgusta smo srednješolci, ki nas veseli matematika, in skupina mentorjev, v veČini študentov matematike, preživeli v Bohinju na 8. Matematičnem Raziskovalnem Srečanju, na kratko MaRS-u. Tam smo poslušali predavanja z različnih področij matematike, imeli matematično - računalniške delavnice, v manjših skupinah pa smo pripravili in na konču predstavili tudi svoje projekte. Našega smo začeli s krajšo zgodbo o Hotelu neskončno. MaRS je vedno bolj priljubljena turistična destin-cija. Povpraševanje se izjemno hitro povečuje, zato so tam zgradili Hotel neskončno, hotel z neskončno enoposteljnimi sobami. Ta se je začel hitro polniti in se je nekega dne tudi napolnil. Poleg vseh običajnih postopkov na rečepčiji so bili vsi gostje primorani podpisati izjavo, da bodo ubogali vse ukaze, ki jih bodo dobili preko zvočnika, tudi če bodo zelo nenavadni. Tisti dan, ko se je hotel napolnil, je prišla petčlanska družina. Ker je pred hotelom visel napis Proste sobe, so zahtevali svojo sobo. Rečeptor jim je ugodil, naslednji dan pa ga je čakala še težja naloga. Najprej se je pripeljala vesoljska ladja z neskončno potniki, nato pa še neskončno vesoljskih ladij, vsaka z neskončno potniki. Rečeptor je bil v vseh primerih dolžan sprejeti vse goste v hotel. Kako? 1Clanek je nastal na poletnem taboru MaRS 2013 (Matematično Raziskovalno Srečanje za srednješolče). Množice Pri reševanju naloge, opisane v uvodu, smo si pomagali z množičami. Poznamo končne in neskončne množiče. Moč končne množiče je enaka številu elementov, ki jih množiča vsebuje. Dve množiči imata enako moč, če vsebujeta enako število elementov. Množiča {*, •} ima enako moč kot množiča z elementi {1, 2, 3,4}. Moč obeh množič je 4. Najbolj »vsakdanja« neskončna množiča je množiča naravnih števil, množiča števil, s katerimi štejemo. Množiče, ki imajo enako število elementov kot množiča naravnih števil, imenujemo števno neskončne množice. Neskončne množiče, ki imajo večjo moč, pa so neštevne. Da bomo lahko ugotovili, kdaj imata dve množiči enako elementov, definiramo bi-jektivno preslikavo. Preslikava iz množiče A v mno-žičo B je bijektivna, če je vsak element iz množiče B slika natanko enega elementa iz množiče A. Množiča je števno neskončna, če jo bijektivna preslikava preslika na množičo naravnih števil. Rečemo lahko tudi, da je množiča števna, če lahko vse elemente postavimo v neko zaporedje. Moč števno neskončne množiče je enaka K0, kar preberemo alefnič. Za lažje razumevanje pojma moči množič si najprej poglejmo nekaj osnovnih primerov. Ce je neka množiča podmnožiča, še ne pomeni, da ima tudi manjšo moč. Ceprav je množiča sodih naravnih števil podmnožiča naravnih števil, imata obe množiči enako moč. Da bi dokazali to izjavo, moramo skon- SLIKA1. Avtorji: Špela, Tilen, Tisa (z leve) in Jana (zgoraj) 8 PRESEK 41 (2013/2014) 3 8 MATE M ATI KA struirati bijekcijo med danima množicama. Preslikava f naj bo podana z naslednjim predpisom: ■ f : N - 2N n — 2n. Preslikava f številu 1 priredi število 2, številu 2 število 4, številu 3 število 6 in tako naprej. Na ta nacin smo vsakemu naravnemu številu priredili natanko eno sodo število in vsakemu sodemu natanko eno naravno število. Torej je preslikava f bijektivna. Da je množica sodih števil števno neskončna, bi lahko dokazali tudi tako, da bi soda števila uredili v zaporedje 2,4,6, 8, ... Tako bi vsakemu številu določili, na katerem mestu stoji ter mu tako enolično priredili neko naravno število - njegovo zaporedno mesto v zapisu zaporedja. Iz zgornjega razmisleka je razvidno, da je množica števno neskoncna natanko tedaj, ko lahko njene elemente razvrstimo v zaporedje. To bomo v nadaljevanju veckrat uporabili. Števna so tudi cela števila Z = {...,-3,-2,-1,0,1, 2, 3,...}. Vsakemu celemu številu priredimo natanko eno naravno število tako, da jih uredimo v zaporedje ■ 0,1,-1, 2,-2, 3,-3,4, -4,... Racionalna števila Množica racionalnih števil je števno neskoncna. To bomo dokazali s pomocjo tabele na sliki 2. V prvi vrstici tabele so vsa cela števila, zapisana po prejšnjem zaporedju, brez števila 0, v prvem stolpcu pa vsa naravna števila. Ostala števila dobimo z deljenjem celih števil z naravnimi. Tako dobimo vsa racionalna števila razen 0. Razvrstimo sedaj racionalna števila v zaporedje. Prvi clen zaporedja je 0, naslednje clene pa dolo-camo po diagonalah. Na prvi diagonali je en clen 1, na drugi sta dva clena: 2 in -1, na tretji so trije cleni: 1, - 2 in 2. Clene na vsaki diagonali, po vrsti od spodaj navzgor, zapisujemo v zaporedje. Clenov, ki smo jih že izpisali, ne izpisujemo vec. Ulomka 1 2 2 in 2 sta enaka, zato ulomka ^ ne izpišemo. Zapišimo prvih nekaj clenov zaporedja: 0,1, 1, -1, 1, -1, 2, 1, -1, -2, 1, ' ' 2' ' 3 2 ' 4' 3' 5' 4, 3, 3 6, ... 1 -1 2 -2 3 -3 ,1 2, 2 ,•• 3 , 3 1 , "1 ,'1 ~y ,1 2,- 2, 3 ... • ' 3 2 , ~2 /2 , "2 .2 2 ,1 2. ' 2/ 3 , 3 3 , ~3 ,3 , "'3 3- ' "3 ,1 2, 2, 3 , 3 4 , ~4 ,4 /A V "4 ,1 ' X' 2. 2/ 3 , 3, 5 .. ~5 }i /i .1 ,1 2' .3 6 .. ~6 ,6 ,6 2 ,2 ,3 7 ■•'"i y 7 , '"i ,• •'' 7 . /~1 SLIKA 2. Dokaz števne neskončnosti množice racionalnih števil Realna števila in Cantorjev diagonalni dokaz Najpreprostejši zgled neštevne množice je množica realnih števil R. Da realnih števil ni števno neskon-cno, je leta 1877 dokazal Georg Ferdinand Cantor. Njegov dokaz nam pove, da je realnih števil vec kot naravnih, ceprav sta obe množici neskoncni. Izrek. Interval [0,1] ni števno neskoncen. Predpostavimo, da interval [0,1] je števno nes-koncen. Potem lahko števila iz tega intervala ozna-cimo z r1 ,r2 ,r3..., saj jih lahko uredimo v zaporedje. Vsa števila ri, za i e N podamo v desetiškem zapisu. Decimalni zapis števila ni enolicen, zato za števila, ki imajo dva razlicna desetiška zapisa (npr. 0,6999... = 0,7000...), uporabimo zapis, ki se kon-cuje z deveticami. Vzemimo primer tega zaporedja realnih števil: 9 PRESEK 41 (2013/2014) 3 MATEMATIKA r1 = 0,62985765. r2 = 0,35634274. r3 = 0,72938906. r4 = 0,67298331. r5 = 0,14265386. r6 = 0,98564352. r7 = 0,21435746. r8 = 0,64532185. Iz tega zaporedja skonstruiramo novo število % tako, da pogledamo k-to števko za desetiško vejico v zapisu k-tega števila rk. Torej pri številu r1 pogledamo prvo decimalko, pri r2 drugo, pri r17 pa sedemnajsto decimalko. Če je ta k-ta števka števila rk enaka 5, bo k-ta števka števila % enaka 4; ce pa k-ta števka rk ni enaka 5, bo k-ta števka števila % enaka 5. Tako bomo dobili realno število % iz intervala [0,1], Iz zgornjega primera bi npr. skonstruirali takšno število: ■ % = 0,54554554... G [0,1]. Ker smo na začetku predpostavili, da zaporedje r1,r2,r3, ... zajame vsa realna števila na intervalu [0,1], bi moral obstajati tudi tak n G N, da bi bil % = rn. Zaradi nacina izbire števk števila % pa se % od rn razlikuje vsaj v števki na n-tem mestu. Od števila r1 se npr. razlikuje v prvi števki, od števila r2 v drugi itd. To pomeni, da števila % v zaporedju r1,r2,r3, ... ni. Torej v zaporedju niso oštevilcena vsa realna števila iz intervala [0,1]. S tem pridemo do protislovja s predpostavko iz zacetka dokaza, da je interval [0,1] števno neskoncen in lahko njegove elemente uredimo v zaporedje. Tako smo pokazali, da interval [0, 1] ni števno neskoncen. Posledica. Moc množice realnih števil je vecja od moci množice naravnih števil, tj. |R| > |N|. Ker vemo, daje |[0,1]| > |N|, je dovolj pokazati |[0,1]| = |R|. Poišcimo torej bijektivno preslikavo, ki preslika interval [0,1] c R v množico realnih števil R. To lahko naredimo s kompozitumom dveh bijektivnih preslikav. Najprej interval [0,1] preslikamo v interval (0,1) s funkcijo f(%) = 1; 2 ; 1; 3 ; 1 ; n+2 ; %; %=0 % = 1 % = n, n G N sicer. Funkcija f število 0 preslika v 2, 1 v 3, 1 v Podobno kot število 1 1 2' x v 3, 2 v 42 preslikamo tudi druga števila oblike n'; imenovalcu ulomka prištejemo 2. Vsa ostala števila preslikamo sama vase. Enostavno je videti, daje f injektivna in surjektivna, torej bijektivna.2 Zdaj poišČcimo še bijektivno preslikavo iz intervala (0,1) v množico realnih števil R. To naredimo s funkcijo g, ki je podana z: g(%) = %(% -1)' 4 2 - -2 - -4 SLIKA 3. Graf bijektivne funkcije g, ki preslika interval (0,1) v realna števila. 2Namig: števila oblike n obravnavaj posebej. 0 2 0 2 4 10 PRESEK 41 (2013/2014) 3 10 MATEMATIKA Funkcija g je zaradi monotonosti injektivna, surjek-tivna pa je zato, ker je zvezna in ima ustrezni limiti limX|0 = in limiti = Kompozitum g ◦ f : [0,1] — R je bijektiven, torej imata množici [0,1] in R enako moc. Iz tega sledi, da je tudi množica realnih števil R neštevno neskončna, torej ima večjo moč od množice naravnih števil N. prve ladje, ki je imel vsoto enako 2. Za njim sta sobi dobila potnika z vsoto 3 in za njima še ostali po nara-šcajocem zaporedju izracunane vsote 4, 5, 6, ... Število potnikov, ki imajo enako vsoto, je vedno koncno, kar je razvidno iz tabele 1. Vsak potnik ima tako pred seboj le koncno drugih gostov in ve, da bo v koncnem casu dobil svoj kljuc. Hotel neskončno Literatura Ko je prišla v hotel petclanska družina, je bil hotel že poln. Receptor jim je moral dodeliti sobe. Po zvoc-niku je sporocil, da naj se vsak gost pomakne za pet sob naprej. Clani družine so dobili sobe od 1 do 5. Nekega dne pa je prispela vesoljska ladja z ne-skoncno potniki. Receptor je moral najti novo rešitev. Vsem gostom v hotelu je ukazal, da pomnožijo številko svoje sobe z 2 in poišcejo sobo z dobljeno številko. Nove goste je razporedil v sobe z lihimi številkami. To je delovalo, dokler ni prišlo neskoncno ladij, vsaka z neskoncno potniki. Receptorja je to najprej presenetilo in ni vedel, kaj naj stori, po premisleku pa se je spomnil rešitve. Najprej je goste v hotelu ponovno premestil v sobe s sodimi številkami in tako izpraznil neskoncno sob z lihimi številkami. Vsak potnik v ladji ima doloceno številko ladje in številko sedeža v ladji. Receptor je gostom ukazal, naj seštejejo številko svoje ladje in sedeža. Nato jim je delil kljuce praznih (lihih) sob po zaporedju njihove izracunane vsote. Najprej je sobo dobil prvi potnik iz 1 2 3 4 5 6 1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 4 5 6 7 8 9 4 5 6 7 8 9 10 5 6 7 8 9 10 11 6 7 8 9 10 11 12 7 8 9 10 11 12 13 [1] N. Casey, Welcome to the Hotel Infinity!, http://www.ccs3.lanl.gov/mega-math/ workbk/infinity/inhotel.html, citirano dne 19. 8. 2013. [2] Števna množica, http://sl.wikipedia.org/ wi ki /stevna_mnozi ca, citirano dne 19. 8. 2013. [3] Cantorjev diagonalni dokaz, http://sl.wiki pedi a.org/Cantorjev_ diagonalni_dokaz, citirano dne 19. 8. 2013. _XXX Križne vsote •is ■i' ■i' -> Naloga reševalca je, da izpolni bele kvadratke s števkami od 1 do 9 tako, da bo vsota števk v zaporednih belih kvadratkih po vrsticah in po stolpcih enaka številu, ki je zapisano v sivem kvadratku na začetku vrstice (stolpca) nad (pod) diagonalo. Pri tem morajo biti vse števke v posamezni vrstici (stolpcu) razlicne. TABELA 1. Številke v prvi vrstici predstavljajo številko sedeža v ladji, številke v prvem stolpcu pa številko ladje. V tabeli je za vsakega potnika napisana vsota teh dveh števil. 8 6 5 15 16 11 12 11 4 14 XXX PRESEK 41 (2013/2014) 3 11