Diskreettiä matematiikkaa

Tämän kirjoitelman aiheena ovat rekursiiviset lukujonot. Jono on rekursiivinen, jos on jokin yleinen sääntö, minkä mukaan jonon seuraava termi määräytyy edellisen tai edellisten funktiona. Aihepiiri sisältyy nykyisin pitkän matematiikan 10:nteen kurssiin. Käsiteltävät esimerkit ovat peräisin Mäntän lukion matematiikkakerhon, ohjelmointikurssien ja muiden erikoiskurssien ohjelmistoista. Esimerkkien ymmärtäminen edellyttää hieman fysiikan, todennäköisyyslaskennan ja kombinatoriikan perustietoja. Tarvittavan kombinatoriikan voit katsoa Pascalin kolmiosta. Aloitetaan mekaniikan esimerkillä.

Diskreetti malli putoamisesta

Tutkitaan putoamisajan laskemista Maan gravitaatiokentässä, kun putoamismatka on niin pitkä, että putoamiskiihtyvyyttä ei voi pitää vakiona. Vaikuttavan esimerkin saamiseksi pysäytämme Kuun sivusuuntaisen liikkeen ja annamme gravitatiovoiman vetää Kuun Maahan. Matematiikassa voi vapaasti kuvitella kaikenlaisia mahdottomiakin asioita! Otamme tehtäväksi laskea putoamisajan. Ongelman voi ratkaista energiaperiaatetta ja differentiaalilaskentaa soveltaen, mutta siitä saatava integraali on perin hankala ratkaista. Probleemasta voidaan kuitenkin johtaa diskreetti malli, jolloin selvitään kahdella peruslaskutoimituksella!

Olkoon x-akselin origo Maan keskipisteessä ja Kuu kohdassa x(t) hetkellä t. Kuun nopeus ja kiihtyvyys hetkellä t ovat v(t) ja a(t). Edelleen oletetaan, että hetkellä t = 0 Kuun etäisyys Maasta on pyöreästi x(0) = L = 4*10⁸m ja v(0) = 0 eli Kuu lähtee levosta. Kiihtyvyys hetkellä t = 0 määräytyy painovoimasta ja on a(0) = -GM/L², missä G = 6,67*10^-11Nm²kg^-2 on gravitaatiovakio ja M = 6*10²⁴kg on Maan massa. Kiihtyvyys on negatiivinen, koska Kuu kulkee x-akselilla negatiiviseen suuntaan. Hetkellä t kiihtyvyys on a(t) = -GM/x(t)². Ilmeisesti ei tehdä suurta numeerista virhettä, jos ajatellaan, että pienessä aikavälissä [t, t+dt] kiihtyvyys on vakio a(t). Tällöin voidaan Kuun paikka, nopeus ja kiihtyvyys hetkellä t + dt laskea aivan perimmäisten fysiikan totuuksien avulla:

x(t + dt) = x(t) + v(t)*dt + ½*a(t)*dt²

v(t + dt) = v(t) + a(t)*dt

a(t + dt) = -GM/(x(t + dt))²

Kuva alla pyrkii selventämään tilannetta:

Valitaan dt:ksi yksi sekunti; yhtälöt yksinkertaistuvat:

x(t + 1) = x(t) + v(t) + ½*a(t)

v(t + 1) = v(t) + a(t)

a(t + 1) = -GM/(x(t + 1))²

Näiden pohjalta on helppo laatia tietokoneohjelma, joka laskee putoamisajan. Annetuilla alkuarvoilla ko. aika on noin 443800 sekuntia. Voit myös ratkaista ongelman jatkuvaa muuttujaa käyttäen tekemällä integroinnin graafisella laskimella tai jollakin matematiikkaohjelmalla.

Sputnik-animaatio

Tekokuun lentoa on helppo simuloida diskreetin mallin avulla tutkimalla putoamisliikettä erikseen x- ja y-suunnissa. Tietenkin täytyy antaa kappaleelle myös poikittainen alkunopeus. Tutkitaan liikettä suorakulmaisessa koordinaatistossa, jonka origo on Maan keskipisteessä.

Kappaleen paikka-, nopeus- ja kiihtyvyyskoordinaatit ovat r_x(t), r_y(t), v_x(t), v_y(t), a_x(t) ja a_y(t). Oletetaan kappaleen lähtevän Maan pinnalta hetkellä t = 0; tällöin r_x(0) = 6,4*10⁶m ja r_y(0) = 0. Alkunopeudeksi valitaan vaikkapa v_x(0) = 100 m/s ja v_y(0) = 9000 m/s; jälkimmäinen komponentti on poikittainen nopeus. Kiihtyvyys alussa on g, mutta kirjoitetaan se seuraavasti: a_x(0) = -G*M/R², a_y(0) = 0. G on gravitaatiovakio, M on Maan massa ja R on Maan säde. Rekursion kuluessa kokonaiskiihtyvyys määräytyy tietenkin gravitaatiovoimasta ja se täytyy projisoida x- ja y-suuntiin. Jos valitaan dt:ksi 1 sekunti, saadaan rekursiokaavat yksinkertaiseen muotoon:

r_x(t + 1) = r_x(t) + v_x(t) + ½*a_x(t)

r_y(t + 1) = r_y(t) + v_y(t) + ½*a_y(t)

v_x(t + 1) = v_x(t) + a_x(t)

v_y(t + 1) = v_y(t) + a_y(t)

d = SQRT(r_x*r_x + r_y*r_y)

a_x =-G*M*r_x/d³

a_y =-G*M*r_y/d³

SQRT tarkoittaa neliöjuurta. Allaoleva Pascal-ohjelman pätkä sisältää algoritmin oleellisimman osan:

dt:=1; d:=6.4e6; 
G:=6.67e-11;M:=6e24;
rx:=6.4e6;ry:=0; 
vx:=100; vy:=9000;
ax:=-G*M/d/d; ay:=0;

   repeat
       rx:=rx+vx*dt+0.5*ax*dt*dt;
       ry:=ry+vy*dt+0.5*ay*dt*dt;
       d:=SQRT(rx*rx+ry*ry);
       xkuva:=(getmaxx div 2)+round(2e-5*rx);
       ykuva:=(getmaxy div 2)-round(2e-5*ry);
       putimage(xkuva,ykuva,p^,normalput);
       vx:=vx+ax*dt;
       vy:=vy+ay*dt;
       ax:=-G*M*rx/d/d/d;
       ay:=-G*M*ry/d/d/d;
   until keypressed;

Sputnikin kuva on talletettu p^:n osoittamaan muistipaikkaan. Huomaa, että tämä on aito simulaatio, sillä kappale kiertää Maata puhtaasti fysiikan lakien mukaan; rataa ei ole laskettu valmiiksi taulukkoon minkään valmiin käyrän mukaan, vaan sitä lasketaan kaiken aikaa Newtonin tavalla!

080297 MH

Palloja uurnissa

Seuraava kysymys on harjoitustehtävänä G. Elfingin klassisessa teoksessa "Todennäköisyyslaskenta", joka on nykyisin antikvaarinen harvinaisuus. Esimerkki sopii matematiikkaa harrastavalle lukiolaiselle syventäväksi tehtäväksi:

Uurnassa U₁ on yksi musta pallo ja N-1 valkoista palloa. Uurnassa U₂ on N valkoista palloa. Kerta toisensa jälkeen otetaan kummastakin uurnasta yksi pallo ja annetaan pallojan vaihtaa uurnaa. Millä todennäköisyydella musta pallo on n:nen siirron jälkeen uurnassa U₁?

Saattaa ensilukemalta tuntua mahdottomalta kysymykseltä, mutta jos tulee ajatelleeksi rekursiivisia lukujonoja samanaikaisesti, tehtävä ratkeaa helposti. Olkoon p_n todennäköisyys sille, että musta pallo on n:n siirron jälkeen uurnassa U₁. Selvästi p₀ = 1 ja p₁ = 1/N. On kaksi toisensa poissulkevaa mahdollisuutta sille, että pallo n:nnen siirron jälkeen on U₁:ssä: pallo on (n-1):nnen siirron jälkeen U₁:ssä ja ei tule nostetuksi n:nnessä otossa tai pallo on (n-1):nnen siirron jälkeen U₂:ssa ja tulee siirretyksi. Matematiikaksi käännettynä tämä näyttää seuraavalta:

pn = pn-1*(N - 1)/N + (1 - pn-1)*1/N

Sieventämällä ja merkitsemällä kertoimia yksinkertaisemmin, saadaan perimmäistä tyyppiä oleva rekursiokaava

pn = a*pn-1 + b,

josta p_n ratkeaa välittömästi.

Sekoittuneet päällystakit

Ravintolasta on sulkemisaikaan lähdössä n asiakasta. Väsynyt narikanhoitaja jakaa päällystakit satunnaisessa järjestyksessä. Millä todennäköisyydellä kukaan ei saa omaansa?

Tämäkin on klassinen ongelma ja aika vaikea. Kaavailemamme ratkaisustrategia lienee harvinaisempi. Ajattelemme taas rekursiivisia lukujonoja ja merkitsemme a_n = "niiden takkijonojen lukumäärä, joissa yksikään n:stä ei osu omistajalleen". Pienellä päättelyllä havaitaan, että a₁ = 0, a₂ = 1 ja a₃ = 2. Jos a_n-1 ja a_n-2 ovat tunnettuja, voidaan a_n päätellä seuraavasti: jos n-1 takkia on jo täysin sekaisin, voi n:s tyyppi vaihtaa takkinsa kenen kanssa tahansa ja tällöin ovat kaikki takit sekaisin tai jos (n-1):stä yksi on saanut omansa, voi n:s tyyppi vaihtaa takkinsa hänen kanssaan; taas kaikki ovat sekaisin. Tuloperiaatetta soveltaen saadaan rekursiokaava

an = (n-1)an-1 + (n-1)an-2

a_n:n laskemiseksi. Laske rekursiokaavaa soveltaen kysytty todennäköisyys. Laske myös todennäköisyyden raja-arvo, kun n kasvaa suureksi. Raja-arvo on perin mielenkiintoinen!

(Linkki ratkaisuun; yritä ensin itse!.)

100297 MH