Fibonacci-tall og fraktaler

Leseren har kanskje hørt om Fibonacci-rekken. Det er en spesiell tallrekke som vokser veldig raskt. Regelen er enkel: vi må starte med to tall, 1 og 1. Så får vi neste tall i rekka ved å summere to to forrige. Så vi får 1+1=2. Dermed har vi 1,1,2. Så får vi neste ved å regne ut 1+2=3. Så vi har 1,1,2,3. Og så videre: 1,1,2,3,5,8,13,21,34,55,89,...

Det er lett å skrive et lite Python-skript som regner ut, si, de 200 første Fibonacci-tallene.

fiblist = [1,1]
n = 100
i = 2
while i <= n:
 fiblist += [fiblist[i-1]+fiblist[i-2]]
 i += 1

Vi lager altså en liste på to elementer, og så lager vi en while-løkke hvor vi regner ut neste Fibonacci-tall ved hjelp av de to forrige. Resultatet ser omtrent slik ut (skroll til høyre for å se alle):

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842,10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738L, 19740274219868223167L, 31940434634990099905L, 51680708854858323072L, 83621143489848422977L, 135301852344706746049L, 218922995834555169026L, 354224848179261915075L, 573147844013817084101L]

Som vi ser, blir tallene fort utrolig store. Det er faktisk en nøyaktig formel for Fibonacci-tallene. La \varphi = \frac{1+\sqrt 5}{2} være "det gylne snitt". Da viser det seg at det n'te Fibonacci-tallet er gitt ved

F_n = \frac{\varphi^n - (-\varphi)^n}{\sqrt 5}

Formelen ble bevist av de Moivre på 1700-tallet en gang. Vi skal ikke ha bruk for den. Vi skal nemlig snakke om et morsomt resultat av Zeckendorf: det sier at ethvert positivt tall kan skrives som en sum av forskjellige Fibonacci-tall. Dette er unikt om vi krever at vi ikke tillater etterfølgende Fibonacci-tall i summen. Hva betyr dette?

Jo, 1 er et Fibonacci-tall, og det er 2 også, så det er en "liten" sum. Det første ikke-Fibonacci-tallet er 4, som kan skrives 1+3. Neste tall er 5, som er et Fibonacci-tall. Neste igjen er 6, som kan skrives 6=1+5. Og 7=5+2. Og 9=1+8. 10=8+2. 11=8+3.

Så skjer det noe morsomt! Hittil har alle tallene kunne skrives med kun to Fibonacci-tall. Men dette går ikke når vi prøver med 12! Men vi kan skrive 12=8+3+1, som er en sum av 3 Fibonacci-tall. Det neste tallet som vi trenger 3 Fibonacci-tall for å skrive er 18, som kan skrives 18=13+1+5.

Ok, nå har vi lært dette. Så vi har lyst å skrive et program som skriver naturlige tall som summer av Fibonacci-tall. Det er flere måter å gjøre dette på, og min er sikkert ikke den mest effektive - kan du programmere, så kom gjerne med raskere forslag.

Det første jeg gjør, er å lage en liste over de 2000 første Fibonacci-tallene ved måten over. En måte å skrive et tall som en sum av andre Fibonacci-tall er "slags rekursivt". Du finner det største Fibonacci-tallet som er lavere enn tallet du jobber med. Og så trekker du det fra. Da er oppgaven redusert til å skrive et lavere tall som sum av to Fibonacci-tall. Og slik jobber du deg bakover:

def fibrep(N):
 if N in fiblist:
   return [N]
 else:
   largest = 1
   for n in fiblist:
     if n > N:
       break
     largest = n
   return fibrep(N-largest) + [largest]

Tester man dette, ser man dette går overraskende raskt (til tross for rekursjonen!). Faktisk vil denne koden også gi en såkalt Zeckendorf-representasjon av tallet N. Dette betyr at svaret vi får er den unike måten å skrive N på som sum av forskjellige, ikke etterfølgende Fibonacci-tall (et kort bevis på hvorfor: anta først at vi får ut en liste med to like Fibonacci-tall (f.eks 10=5+5). Dette kan ikke skje, fordi 5 er et Fibonacci-tall, og da vil koden terminere på den første av dem. Anta så at vi får to etterfølgende Fibonacci-tall: f.eks 21=13+8. Men da er 21 selv Fibonacci-tall, så koden terminerer allerede da)

Her er for eksempel Zeckendorf-representasjonen av de 100 første naturlige tallene:

[[1], [2], [3], [1, 3], [5], [1, 5], [2, 5], [8], [1, 8], [2, 8], [3, 8], [1, 3, 8], [13], [1, 13], [2, 13], [3, 13], [1, 3, 13], [5, 13], [1, 5, 13], [2, 5, 13], [21], [1, 21], [2, 21], [3, 21], [1, 3, 21], [5, 21], [1, 5, 21], [2, 5, 21], [8, 21], [1, 8, 21], [2, 8, 21], [3, 8, 21], [1, 3, 8, 21], [34], [1, 34], [2, 34], [3, 34], [1, 3, 34], [5, 34], [1, 5, 34], [2, 5, 34], [8, 34], [1, 8, 34], [2, 8, 34], [3, 8, 34], [1, 3, 8, 34], [13, 34], [1, 13, 34], [2, 13, 34], [3, 13, 34], [1, 3, 13, 34], [5, 13, 34], [1, 5, 13, 34], [2, 5, 13, 34], [55], [1, 55], [2, 55], [3, 55], [1, 3, 55], [5, 55], [1, 5, 55], [2, 5, 55], [8, 55], [1, 8, 55], [2, 8, 55], [3, 8, 55], [1, 3, 8, 55], [13, 55], [1, 13, 55], [2, 13, 55], [3, 13, 55], [1, 3, 13, 55], [5, 13, 55], [1, 5, 13, 55], [2, 5, 13, 55], [21, 55], [1, 21, 55], [2, 21, 55], [3, 21, 55], [1, 3, 21, 55], [5, 21, 55], [1, 5, 21, 55], [2, 5, 21, 55], [8, 21, 55], [1, 8, 21, 55], [2, 8, 21, 55], [3, 8, 21, 55], [1, 3, 8, 21, 55], [89], [1, 89], [2, 89], [3, 89], [1, 3, 89], [5, 89], [1, 5, 89], [2, 5, 89], [8, 89], [1, 8, 89], [2, 8, 89]]

(skroll for å se alle) Vi ser nå at noen tall krever 4 Fibonacci-tall, for eksempel 33=1+3+8+21. Andre krever enda flere. Så vi kan spørre oss, hvis vi plotter naturlige tall mot lengden på en Zeckendorf-representasjon av dem, hvordan vil denne grafen se ut? Vi ser allerede at for de 11 første tallene er den konstant lik 2 (bortsett fra på Fibonacci-tallene hvor den er lik 1).

La oss se hvordan dette ser ut for de 200 første naturlige tallene:

Plot of the 200 first natural numbers versus the length of their Zeckendorf representation.

Plott av de 200 første naturlige tallene mot lengden på deres Zeckendorf-representasjon.

Vi ser et slags mønster, men det er ikke helt klart hva som skjer. La oss plotte de 1000 første også:

De 1000 første naturlige tallene og lengden til deres Zeckendorf-representasjon.

De 1000 første naturlige tallene og lengden til deres Zeckendorf-representasjon.

Hmhm. Mønsteret er ennå litt tydeligere! La oss prøve med de 10.000 første naturlige tallene!

De 10.000 første naturlige tallene og lengden på deres Zeckendorf-representasjon.

De 10.000 første naturlige tallene og lengden på deres Zeckendorf-representasjon.

Dette er morsomt! Nå ser vi helt tydelig et mønster. Det er til og med noe fraktal-lignenden over det. På den nederste "linjen" ser vi tall som har lengde 1 Zeckendorf-representasjon. Dette er Fibonacci-tallene. På linje 2 er det de som har lengde 2, og så videre. Det vi ser er at disse tynnes ut når vi nærmer oss neste Fibonacci-tall, og sånn er det på hver linje.

Nå kan vi spørre oss hvor raskt denne funksjonen vokser, hvor regulær den er, og så videre! Men det får vente til en anne bloggpost...

Posted in Uncategorized | Leave a comment

Hva er sannsynligheten for at ditt telefonnummer er primtall?

Et illustrasjonsbilde for å gjøre artikkelen mer interessant. Det har ingenting med matematikk å gjøre. Kilde: Wikipedia.

Et illustrasjonsbilde for å gjøre artikkelen mer interessant. Det har ingenting med matematikk å gjøre. Kilde: Wikipedia.

La oss snakke litt om telefonnummer og primtall og sannsynlighet. Hva er sannsynligheten for at ditt telefonnummer er primtall?

La oss starte med telefonnummer. I prinsippet kan et telefonnummer være en hvilken som helst åttesifret tallkombinasjon mellom 0 og 10^8-1. Men la oss være litt mer realistiske. Ingen privatpersoner i Norge har et mobilnummer som begynner på 0, 1 eller 8. De resterende tallene er enten fasttelefon eller mobil (her er kilden min denne to år gamle tråden på Norsk Freakforum). Så for oss er definisjonen på et telefonnummer et hvilken som helst 8-sifret tall som starter på en av tallene 2,3,4,5,6,7 eller 9 (det gir 7 \cdot 10^{7} mulige nummer, altså ca. 14 nummer per person i Norge. Dette er egentlig ikke så mye - ettersom bedrifter ofte har mange nummer).

La oss snakke litt om primtall. Et primtall er et tall som ikke er en 1, og er delelig med kun seg selv og 1. (for de matematisk sofistikerte: vi vil at restkroppen \mathbb Z/(p) skal være en kropp, og hvis p=1, får vi \mathbb Z/(p) =0, altså "kroppen med ett element", som er problematisk). For å friske minnet, her er de første primtallene: 2,3,5,7,11,13,17,19,23,29,31,37,41,43..,101,... So far so good!

Det er lett å se at det er uendelig mange primtall. Dette ble bevist for flere tusen år siden, og det mest kjente beviset, som fremdeles er det eneste man lærer i dag, ble gitt av Euklid. Det går som følger: Vi skal konstruere en uendelige følge med primtall (ikke nødvendigvis alle, men likefullt en uendelig følge). La første tall i følgen være 2. Anta så induktivt at vi har konstruert følgen opp til a_k. Dann så tallet a_1a_2a_3 \cdots a_k + 1 (produktet av alle tallene i følgen sålangt pluss en). Dette er et tall som ikke har noen faktor felles med noen av tallene i følgen så langt, så det må finnes et primtall p som er ulik a_i for i=1,2,\cdots,k. Sett a_{k+1}=p. Dette viser at vi kan danne en uendelig lang liste med forskjellige primtall. QED.

Legg merke til at teknikken i beviset ikke produserer alle primtall. For å se dette, prøv å konstruér følgen over, og se hvilke primtall som mangler. Hint: følgen vil starte med 2,3,7,....

Men dette var en digresjon. Det neste store spørsmålet med primtall, nå når vi vet at det er uendelig mange av dem, er: hvordan fordeler primtallene seg? Med andre ord, hvor mange primtall er det i intervallet [0,x] når x varierer? For eksempel, for x=10, ser vi at det er 4 primtall mellom 0 0g x=10. Mellom 0 og 20 har vi 8 primtall. Mellom 0 og 30 har vi 10 primtall. Allerede nå ser vi et mønster: primtallene blir sjeldnere og sjeldnere. Faktisk kan vi komme med en tilnærmet formel for hvordan hvor mange primtall det er lavere enn x (vi kaller "antall primtall lavere enn x for \pi(x)):

 \pi(x) \sim \frac{x}{\ln x}.

Her betyr "\sim" at formelen er en god tilnærming for store x. Denne formelen er kjent som "primtallssatsen", og ble først bevist av Hadamard og Poussin ved hjelp av komplekse teknikker (både billedlig og bokstavelig talt). Et mer elementært bevis ble gitt mye senere av den norske matematikeren Atle Selberg og den ungarske matematikeren Paul Erdös uavhengig av hverandre (noe som forøvrig skapte en ørliten plagiatkonflikt i matematikermiljøet, men det er annen sak...).

y-aksen viser antall primtall lavere enn x. Bildet er sakset fra Wolphram Mathworld.

y-aksen viser antall primtall lavere enn x. Bildet er sakset fra Wolphram Mathworld.

Det som er så fint med primtallssatsen, er at vi nå kan beregne hvor mange telefonnummer som er primtall (circa, selvfølgelig!). Siden ingen telefonnummer starter på 8, må vi gjøre dette i to omganger. Først regner vi ut hvor mange primtalltelefonnummer det er som begynner på 2,3,4,5,6,7, og så hvor mange som begynner 9. Det første tallet er \pi(80000000)-\pi(20000000) (klarer leseren å se hvorfor??). Det andre tallet er \pi(100000000)-\pi(90000000). Nå kan vi bruke primtallformelen over for å regne ut hva disse differansene er. Gjør vi det får vi henholdsvis 3.206.519  og 514.762 (rundet til nærmeste heltall). Dermed er det circa 3.206.519+514.762=3.721.281 \approx 3.7 \cdot 10^6 telefonnummer som er primtall.

Vi konkluderer med at prosentmessig er det

 100 \cdot \frac{3.7 \cdot 10 ^6}{7 \cdot 10^7}\approx 5.3\%

Så med andre ord, det er omtrent like mange folk med primtallstelefonnummer som Venstre-velgere i dette landet.

Posted in Uncategorized | Leave a comment

Matematisk julepynt

Det er jul og eksamenstid. Det betyr at vi har ekstra motivasjon til å gjøre ting som ikke innebærer å lese til eksamen - for eksempel å lage julepynt.

Først en liten forhistorie

Et polyeder er en matematisk figur som er satt sammen av polygoner. Eksempler på polyedre er:

image003 Leonardo_polyhedra

Polyedret til venstre er satt sammen av 18 kvadrater og 8 trekanter. Polyedret til høyre, også kjent som en såkalt "fotball" (red. anm: utstyr brukt av sportsinteresserte), er satt sammen av 12 femkanter og 20 sekskanter.

Men noen polyedre er likere enn andre. Dette er polyedre som er satt sammen av helt like figurer, og der alle figurene møtes på samme måte i hvert hjørne. Dette er de platonske legemene:

 platonic

Disse er satt sammen av trekanter, kvadrater eller femkanter. Det gule polyedret er satt sammen av fire trekanter, det grønne er satt sammen av åtte trekanter, det røde er satt sammen av seks kvadrater (red. anm: også kalt en terning). Det lilla er satt sammen av 20 trekanter, og det blå er satt sammen av 12 femkanter. De kalles (i samme rekkefølge) for tetraeder, oktaeder, hexaeder, icosaeder og dodekaeder (på engelsk bytter man ut "eder" med "hedron").

Her er en funfact kjent som Eulers teorem: teller du antall hjørner (H), antall kanter (E) og antall flater (F) i figurene over, får du alltid at forskjellen H-E+F=2. (prøv selv!)

Julepynt

Nå har vi kommet til poenget med denne posten. Polyedre eksisterer ikke bare i matematikernes fantasi, men også på juletrærne - ihvertfall om man henger dem der. Du må bare lage dem først.

Alt du trenger er piperensere, gjerne av typen som glitrer. Jeg fant mine på juggelbutikken "Tiger" på Arkaden i Oslo. Antakelig selges de andre steder også.

Greia er følgende: bruk en linjal, og brett piperenserne slik at du deler dem i tre, fire, eller fem like store deler (ha en liten del til overs slik at du "knyte" kantene). Så setter man dem sammen. Her er noen bilder:

2013-12-12 10.40.18De over er tetraederet, kuben og oktaederet. (Beklager bildekvaliteten, men jeg skal liksom drive med matematikk og ikke drasse på gode kameraer!)2013-12-12 10.40.22Her er oktaederet på nytt, og på høyresiden er dodekaederet.

2013-12-12 10.40.30Til slutt har vi ikosaederet. Det var vanskeligst å lage, og ble ikke så veldig symmetrisk. Utfordring: gjør det bedre selv.

Posted in Uncategorized | Leave a comment

"hva er MATEMATIKK" av Liza Lorentzen

Hva er matematikk?Boken "hva er MATEMATIKK" av professor i matematikk ved NTNU, Lisa Lorentzen, kom ut i november. Den er en del av Universitetsforlagets "hva er"-serie. Jeg fullførte nylig boken.

Boken er ment for folk flest, og det er meningen at hvem som helst skal kunne lese boken uten å gå glipp av noe.  Boken har syv kapitler, hvor de seks siste begynner med "matematikk og ...": tall, verden, struktur, sannhet, uendeligheten og skjønnhet.

Målet med boken er ikke å gi noe hurtigkurs i matematikk eller å være noe "survival kit" gjennom Kalkulus-kurset. Den prøver, tvert om, å beskrive hva matematikk er gjennom å appellere til hva en matematiker gjør og hva som er så fascinerende med matematikk. Nettopp på siste punktet skinner forfatterens egen fascinasjon gjennom. Matematikk er utrolig fascinerende, og har man ikke allerede denne fascinasjonen, smitter den over fra Lorentzens engasjerte beskrivelser.

På enkelte steder virker hun så fascinert at det nesten virker kunstig - men man skal ikke klage så mye over overdreven fascinasjon for matematikk! Slikt finner man ikke over alt.

Hun tar blant annet opp Möbius-båndet, at \sqrt{2} er irrasjonal, Koch-snøflak, fraktaler, matriser, matematiske modeller, uendelighet, tesseleringer av planet, Euler-karakteritistikk, med mer.

Boken er lettlest (kan hende enkelte deler ikke er kjempelettlest om man ikke er vant til å lese tung matte) - fin sengelesing/trikkelesestoff.

Posted in Anmeldelser | Leave a comment

Fire farger-teoremet

Jeg postet for ikke lenge siden følgende tweet@MatematikkFakta:

Du vil aldri trenge mer enn 4 farger om du skal fargelegge et kart.

Kort tid etterpå var noen av mine observante følgere ute og kommenterte at påstanden ikke var helt presis. Dette er selvsagt riktig, og kudos til dem og alle andre med observant blikk.

For at påstanden skal stemme, må den gjøres presis. Det er to ting som er uklart slik påstanden står nå. 1) Hva menes med å fargelegge et kart? 2) Hva er et kart!?

I denne bloggposten skal jeg prate litt om punktene 1) og 2), og litt om hvordan påstanden til slutt ble bevist. Vi vil se at å reformulere problemer er vanlig og nyttig i matematikken.

"Moteksempel" til fire farger-teoremet. Fra Wikimedia Commons, laget av Inductiveload.

Først og fremst, i virkeligheten er påstanden feil. For at fire farger skal holde om vi skal fargelegge et kart, må landene være enkeltsammenhengende. Dette betyr at tilfeller som Russlands Kaliningrad eller andre land med enklaver ikke kan tillates. Se bildet til høyre. Det skal forestille et land A med en enklave. Resultatet er at vi er nødt til å bruke 5 farger. I tillegg må vi tillate at hjørnene til landene får lov til å møte i samme farge.

Så, siden vi har utelukket Russland med Kaliningrad (også Aserbajdsjan med Nakhitsjevan), så virker plutselig ikke teoremet særlig relevant for virkeligheten. Faktisk forteller Wikipedia-artikkelen om teoremet at selv ikke folk som lager kart bryr seg - for de velger som regel å bruke flere farger uansett.

Så vi kan likegjerne omdefinere hva problemet handler om. For å unngå problemer med rare kart, hjørner, pussige kurver, og så videre - reformulerer vi problemet ved hjelp av grafteori. Kort sagt: fra et kart lager vi en graf (en graf er en samling noder, med kanter mellom dem), som i bildet under:

Fra kart til graf. Fra Wikimedia Commons, laget av Inductiveload.

Det vi gjør er følgende: la hvert land være representert med en node (=prikk). Om to land grenser til hverandre, tegner vi en strek mellom dem. Fire farger-teoremet kan nå reformuleres til følgende:

Nodene til enhver graf i planet kan fargelegges med 4 farger slik at ingen nabo-noder har samme farge.

Eller mer teknisk: "enhver planar graf kan fire-farges". Fordelen med denne omformuleringen er at vi nå kan bruke masse verktøy fra algebraisk topologi og grafteori for å arbeide med problemet (i tillegg til at problemstillingen er mye mer presis).

Teoremet har en lang historie. Det ble først formodet i 1852, hvoretter flere gale bevis ble presentert. I 1890 ble fem farger-teoremet bevist - som faktisk er betraktelig lettere å bevise enn fire farger-teoremet. Først på 60-70-tallet begynte man igjen å gjøre framskritt, og da ved hjelp av datamaskiner. I 1976 annonserte Kenneth Appel og Wolfgang Haken ved University of Illinois at de hadde bevist teoremet - mye ved hjelp av en datamaskin.

Det de hadde gjort, var å redusere problemet. De fant ut at, enkelt sagt, enhver slik graf kan bli bygd opp av et endelig antall enklere grafer. De fant 1,936 slike, så for å bevise teoremet var det nok å be en datamaskin gå gjennom alle disse mulighetene, og sjekke èn og èn.

Dette var langt fra enkelt, og krevde mye manuelt arbeid. For å finne disse 1,936 tilfellene, måtte de gjøre mye for hånd. Det endte opp med et over 400 sider langt bevis. De tekniske detaljene krevde mange originale ideer og annen matematisk analyse. En rekke observasjoner reduserer teoremet til såkalte triangulerte grafer, og litt tellearbeid setter begrensninger på eventuelle moteksempler. Til slutt med en metode som er inspirert fra fysikk brukt; på engelsk "method of discharging". Man ser for seg at grafen er en elektrisk ledning, og har en viss ladning. Så kan man redusere grafen steg for steg sålenge man holder styr på "ladningen". Mer informasjon om dette smarte trikset er på Wikipedia-artikkelen om beviset.

Men matematikere er kresne typer, og beviset fikk mye kritikk. De mente for eksempel at for at et bevis skulle være et ordentlig matematisk bevis, måtte det kunne sjekkes av mennesker. Andre mener at datamaskiner kun skal gjøre utregninger, og ikke steg i bevisene (det er en forskjell her).

Tross dette er det et faktum at maskiner tross alt gjør færre feil enn mennesker. Den største innsigelsen mot teoremer bevist av datamaskiner er estetisk: beviset gir ikke noen ny innsikt i problemet eller gir opphav til nye nyttige begreper. Det er jo tross alt dette som er vakkert med matematikk: det å få innsikt i et stort problem.

Til slutt: På en torus (=smultring) stemmer heller ikke 4-farge-teoremet. Her kreves 7 farger:

Torusen krever 7 farger.

Posted in Applications, Smalltalk | 2 Comments

En altfor vanskelig måte å løse en enkel ligning på

La oss si at vi har ligningen x=2x-2. Dette lærte man å løse på ungdomsskolen ved å få x-ene på èn side. (i dette tilfellet ser vi raskt at x=2 er eneste løsning). Men hva om vi har lyst til å være vanskelige?

Siden x=2x-2, kan vi skrive x=2(2x-2)-2=4x-6. Så vi har nå at x=4x-6. På samme måte kan vi sette inn for x i denne ligningen, og få x=4(2x-2)-6=8x-14. Fortsetter vi n ganger, får vi at x=2^nx-2^n-2^{n-1}+\cdots+2. Det siste leddet er en geometrisk rekke, som forenkler til 2^{n+1}-2.

Vi har altså nå at x=2^nx-2^{n+1}-2.  Vi deler på 2^n på begge sider og får \frac{x}{2^n}=x-2-\frac{2}{2^n}. Lar vi nå n gå mot uendelig, forsvinner venstresiden av ligningen og mye av høyresiden. Vi står igjen med 0=x-2, så x=2.

Posted in Smalltalk | 2 Comments

En veldig enkel tilfeldig tall-generator

Akkurat nå leser jeg boken "Chaos - A Very Short Introduction". Den definerer et kaotisk system til å være et system som er veldig ømfintlig overfor initialbetingelsene. På et tidspunkt nevner boken et veldig enkelt dynamisk system.

Hva mener vi med et dynamisk system? For våre formål mener vi bare en følge med tall, x_0, x_1, \ldots. En enkel klasse av dynamiske systemer er på formen x_0=a for en eller annen a, som vi kaller initialverdien. Så definerer vi rekursivt alle andre verdier av x_n som x_{n+1}=f(x_n) hvor f(x) er en eller annen funksjon.

Nå skal vi la f(x)=4x(1-x). Denne har to nullpunkter, nemlig x=0 og x=1. Den har et toppunkt i x=1/2.

Dette gir opphav til et dynamisk system så snart vi velger en initialverdi. Det kule med denne enkle funksjonen, er at i tidligere tider brukte man denne for å generere "tilfeldige" tall. La oss se litt på dette. En enkel, rekursiv implementasjon i SAGE er gitt ved:

def r(x,n):
    if n==0:
        return x
    else:
        return r(4*x*(1-x),n-1)

Vi genererer listen:

def generateList():
    return [[i,r(1/float(pi),i)] for i in range(0,500)];
L = generateList()

Og vi plotter den:

p = line(L)
p.show(xmin=0,xmax=500,ymin=0,ymax=1)

Her er resultatet vi får (klikk på bildet for noe større versjon):

Dette er kanskje litt overveldende. La oss bare ta 100 punkter:

Dette er ganske kult, for vi ser at oppførselen til følgen er helt vill. Betydningen av "vill" kan defineres matematisk, men la oss hoppe over det. Poenget er at følgen i stor grad oppfører seg "tilfeldig". Vi ser også at små endringer i startverdien kan gi helt forskjellige følger. Under er først for startverdien 0.3, så for startverdien 0.31.

Vi ser at grafene er ganske like, men at verdiene opptrer på ganske forskjellige steder. Dette kan utnyttes for å lage tilfeldige tall. Man kan for eksempel først velge en initialverdi, så kjøre det dynamiske systemet, og bruke dette til å generere en følge av 100 tall. Neste gang velger man en annen initialverdi, og man vil få en følge som ikke ligner på den forrige.

Posted in Applications, Smalltalk | 1 Comment

Litt om telling

La oss være litt filosofiske. Du er et steinaldermenneske, eller noe enda eldre enn det, eller bare dum. Du kan nemlig ikke tallene, men vil likevel finne ut om det er du eller naboen som har flest fisk.

Hadde du kunnet telle,  hadde det vært mye enklere, for det er lett å sjekke om et tall er større enn et annet. Matematisk kan vi si at du har en funksjon fra mengden av fiskehauger (F) til heltallene. La oss kalle den f:F \to \mathbb{N}. Så om din fiskehaug kalles A, og naboen B, er alt vi trenger å sjekke om f(A)  data-recalc-dims= f(B)" />.

Men du kjenner ikke til heltallene \mathbb{N}! Fiskehauger er mengder bestående av fisk. Symbolsk kan vi si A = \bigcup_{a \text{ fisk}} \{a\}. Så hvordan kan vi telle uten tall? Vel, det kan vi ikke! Men vi er ikke helt fortapte. La oss si at du har to hauger, A og B,  med like mange fisk. Da kan hver fisk fra haug A "parres" med nøyaktig en fisk fra haug B, og hver fisk fra haug B kan parres med èn fra haug A. Vi ser at vi får en 1-1-korrespondanse mellom fisk i haug A og fisk i haug B.  Matematisk har vi en bijeksjon g:A \to B, det vil si en funksjon fra A til B som er både 1-1 og "på"/surjektiv.

Men hvordan er situasjonen om det er færre fisk i haug A enn i haug B? (for enkelhets skyld kan du tenke at det er to fisk i haug A og 5 i haug B) Da ser vi at det er umulig å få til en funksjon fra A til B som er "på" B, eller surjektiv. Det betyr at det er umulig å gi hver fisk i haug B en "partner" i A, fordi det er færre fisk i haug A.

Motsatt, om det er flere fisk i haug A enn i haug B, sier litt ettertanke oss at det er umulig å få til en injeksjon A \to B. En injeksjon er en funksjon som ikke sender to forskjellige tall til samme tall b . Om det er flere fisk i haug A, må minst to a sendes til samme b.

Dermed ser vi at det eneste tilfellet hvor vi klarer å få til en funksjon som er både surjektiv og injektiv, er når det er like mange fisk i haug A som i haug B. Dette gir oss også muligheten til å si når det er færre eller flere fisk i haug A enn i haug B. Vi definerer det til å være flere fisk i haug A enn i haug B om det ikke finnes noen injeksjoner A \to B, og vi definerer det til å være færre fisk i haug A enn i haug B om det ikke finnes noen surjeksjoner A \to B. Til slutt sier vi at det er like mange fisk om det finnes en bijeksjon mellom A og B, altså både en injeksjon og surjeksjon.

Hva forteller alt dette oss? Det første vi kan si, er at heltallene har mye mer struktur enn vi trenger om vi bare skal sjekke om noe har like mange elementer som noe annet. Å sjekke om det finnes en injeksjon/surjeksjon/bijeksjon sier ingenting om hvor mange elementer det er i mengdene, bare om det er færre/flere/like mange. Å telle er en kvantitativ operasjon, mens å sjekke hva slags funksjoner det finnes mellom to mengder er en kvalitativ operasjon.

Men ok, vi har kommet fram til at vi ikke trenger heltallene for å sjekke hvilken mengde som har flest elementer. Men hva er poenget? Hvorfor gjøre det så tungvindt? Vel - nå har vi en mer elementær måte å sjekke størrelse på mengder på, og dette hinter om at vi kanskje kan generalisere definisjonene av "flere/færre enn" til andre mengder enn bare endelige.

For nå, la oss anta at leseren skjønner hva som menes med en uendelig mengde. Et eksempel på en slik mengde er mengden av alle heltall. Det er lett å sjekke at det er flere heltall enn, la oss si, elementer i mengden A=\{1,2,3,4,5\}. Det finnes nemlig ingen surjeksjoner A \to \mathbb{N} (Bevis: om det finnes en slik surjeksjon, finnes også en surjeksjon A \to \{1,2,3,4,5,6\} ved restriksjon. Dette går bare ikke).

Et annet eksempel på en uendelig mengde er mengden av partall, altså tallene E=\{2,4,6,8,\cdots\}. Siden partallene er en ekte delmengde av heltallene (det finnes heltall som ikke er partall), er det naturlig å tro at det er flere heltall enn partall. La oss sjekke med vår definisjon: Kan vi bevise at det ikke finnes noen injeksjoner \mathbb{N} \to E? Svaret er nemlig nei: et eksempel på en injeksjon er funksjonen n \to 2n. Det er lett å sjekke at denne er injektiv, så vi må konkludere (med vår definisjon av "færre enn") at det er færre/like mange heltall som partall. Det er også lett å se at den er surjektiv, så vi er faktisk nødt til å konkludere med at det er like mange partall som heltall, selv om det åpenbart finnes mange heltall som ikke er partall.

Nå blir du kanskje frustrert, river deg i håret, og tenker at matematikere lager helt pussige definisjoner. Er alle mengder like store, bare de er uendelige? Nei, det finnes mange forskjellige "uendeligheter", alle av forskjellige størrelse (det vil si, det finnes ingen bijeksjoner mellom dem). Det kan vi ta i en senere bloggpost.

Posted in Set Theory, Smalltalk | Leave a comment

Beregne volum av kuler

I anvendelser av matematikk har man ofte behov for å regne ut volumer av avanserte geometriske objekter. Som regel går det ikke an å regne ut slikt for hånd eller med pene formler, så matematikere jobber mye med å finne algoritmer som datamaskiner kan utføre for å finne en tilnærmet løsning.

Tenk deg at du har fått i oppdrag å regne ut arealet av en kule i n dimensjoner. Først av alt - hva i all verden mener vi med dette? En sirkel i planet med radius 1 kan beskrives som alle punkter (x,y) i planet slik at  x^2+y^2=1 (hvorfor? hint: Pythagoras' setning). På samme måte kan vi beskrive en kule som alle punkter (x,y,z) i rommet slik at x^2+y^2+z^2=1.

Vi generaliserer, og definerer en  kule i n dimensjoner til å være alle punkter (x_1,x_2,\ldots,x_n) i \mathbb{R}^n slik at \sum_{i=1}^n x_i^2 = 1.

Men la oss nå si at du har lyst å regne ut arealet av en sirkel i planet. Vi kan anta sirkelen har radius 1 og er plassert i origo. Tegn så et kvadrat rundt sirkelen, med diagonaler med lengde 1, som på figuren under:

Enhetssirkelen på innsiden av en firkant.

Siden firkanten har sidelengder på 2, har den arel 4. Her kommer trikset: kast masse "dart-piler" (eller punkter, om du vil) på firkanten slik at de havner tilfeldig spredt omkring. Kall arealet til sirkelen for A. Da vil A/4 av dart-pilene havne på innsiden av sirkelen.  Dermed, for å få arealet av sirkelen, ganger vi dette forholdet med 4.

Fordelen med denne metoden er at det er veldig lett å sjekke om et punkt er på innsiden av sirkelen eller ikke. Vi sjekker bare om x^2+y^2 < 1 eller ikke. Om x^2+y^2 < 1, så er punktet (x,y) på innsiden av sirkelen. Dette generaliserer lett til flere dimensjoner enn 2 og til andre figurer enn sirkler.

Jeg har testet denne metoden på sirkler i Python. Jeg laget et program som jeg kalte for areal_kule.py. Vi tester for sirkelen og med 1000 dart-piler:

Fredriks-MacBook-Air:Python Fredrik$ python areal_kule.py 2 1000
Tilfeldig volum: 3.196
Ekte volum: 3.14159265359
Error: 0.0544073464102

Ikke veldig imponerende, kanskje - vi kastet tross alt 1000 dart-piler! Vi tester med èn million dart-piler i stedet (dette tok litt under 10 sekunder på min maskin):

Fredriks-MacBook-Air:Python Fredrik$ python areal_kule.py 2 1000000
Tilfeldig volum: 3.144456
Ekte volum: 3.14159265359
Error: 0.00286334641021

Nå ble resultatet en god del bedre. La oss prøve å regne ut volumet av en kule:

Fredriks-MacBook-Air:Python Fredrik$ python areal_kule.py 3 1000000
Tilfeldig volum: 4.184968
Ekte volum: 4.18879020479
Error: 0.00382220478639

Ikke dårlig! Denne metoden kalles for Monte Carlo-integrasjon, og det viser seg at slike "tilfeldige" metoder ofte er mer effektivt i høyere dimensjoner.

Når vi først snakker om sirkler, kan man lure på hva som skjer med volumet til sfærer når vi øker dimensjonene. Resultatet er litt kontraintuitivt:

Volum kuler

Vi ser at volumet til kulene øker fram til dimensjon 4, hvor det begynner å falle. Faktisk går kulevolumet i dimensjon n mot null når n går mot uendelig. Dette er fordi diagonallengden på kvadratet rundt kulen blir større og større etterhvert som n øker.

For ordens skyld, her er Python-programmet jeg brukte for å regne ut volumene:

from random import random
from math import pi, gamma, fabs
import sys

if len(sys.argv) == 1:
    sys.exit("Skriv areal_kule d n. d dimensjon, n antall, std n=1000")
if len(sys.argv) == 2:
    d = int(sys.argv[1])
    n = 1000
if len(sys.argv) == 3:
    d = int(sys.argv[1])
    n = int(sys.argv[2])

i = 1
s = 0.
cube_area = 2**d #area of cube in dimension d

while i < n:
    if (sum([random()**2 for j in range(d)])) < 1:
        s += 1
    i += 1

random_area = (s/n)*cube_area
true_volume = pi**(0.5*d)/gamma(0.5*(d+2))

print "Tilfeldig volum: " + str(random_area)
print "Ekte volum: " + str(true_volume)
print "Error: " + str(fabs(random_area-true_volume))
Posted in Smalltalk | 3 Comments

Monty Hall-paradokset

"Monty Hall"-problemet er et statistisk paradoks som ble kjent etter at Marilyn vos Savant skrev om det i et amerikansk blad i 1990. Problemet går som følger:

"Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1 [but the door is not opened], and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?"

Eller på norsk: Du er med på en konkurranse, og skal velge èn av tre dører. Bak en av dørene er det en bil (som er premien), og bak de to andre er det geiter. Om du velger, la oss si, dør nummer 1 - så åpner programlederen en dør, f.eks nummer 3, og bak den er det en geit. Han gir deg nå mulighet til velge dør på nytt. Er det til din fordel?

Intuitivt burde det ikke hjelpe å bytte dør. Du vet fra før at sjansen for at du finner en bil er 1/3. Om programlederen viser deg en dør med geit, vet du at enten er bilen i den du har valgt eller den andre døren som ikke er vist.  Burde det da ha noe å si om du bytter? Det paradoksale (i betydningen at det kan overraske), er at det alltid vil lønne seg å velge ny dør. Hvorfor? Det finnes flere intuitive måter å forklare dette på.

Forklaringen er overraskende enkel: Du taper om du bytter dør hvis og bare hvis du valgte bilen første gang. Sjansen for å velge bil første gang er 1/3. Dermed er sjansen for å vinne med bytting lik 1-\frac{1}{3}=\frac 23.

Eller vi kan teste problemet med empiri (og litt logisk tenking). Jeg programmerte to Monty Hall-funksjoner i SAGE (Python-kode). Den ene funksjonen bytter dør, mens den andre ikke gjør. Så tester vi. Her er koden til funksjonen som bytter dør:

def montyhall_change(choice): # med bytting
   if choice == 1:
       return False
   else:
       return True

Kort forklaring av funksjonen: Vi kan anta bilen ligger bak dør nummer 1. Hvis du velger å bytte, og velger dør nummer 1, taper du. Derfor returnerer funksjonen False. Hvis ikke, viser Monty deg en dør med geit i. Det er bare to dører med geiter, så han må åpne den du ikke valgte. Om du skal bytte, er eneste mulighet å velge døren med bilen, og funksjonen returnerer derfor True.

Vi lager også en funksjon for å ikke bytte dør. Den er naturligvis noe enklere:

def montyhall_keep(choice):
    if choice == 1:
        return True
    else:
        return False

Til slutt simulerer vi konkurransen et stort antall ganger, og ser på tallmaterialet vi får:

k = 10000
s_change = 0
s_keep = 0
for n in range(k):
    random = ZZ.random_element(3)+1
    if montyhall_change(random) == True:
        s_change += 1
    if montyhall_keep(random) == True:
        s_keep += 1

print "Antall forsok: ", k
print "Antall suksess bytte: ", s_change,
      " Antall suksess beholde: ", s_keep
print "Prosent riktig bytte: ", s_change/float(k)
print "Prosent riktig bytte: ", s_keep/float(k)

Koden over kjører konkurransen 10.000 (ti tusen) ganger. For hver gang vi vinner bil, øker s_change eller s_keep med 1, avhengig av hvilken metode vi brukte. Resultatet vises under:

Antall forsok:  10000
Antall suksess bytte:  6721  Antall suksess beholde:  3279
Prosent riktig bytte:  0.6721
Prosent riktig beholde:  0.3279

Dette stemmer godt med utregningene vi gjorde.

Posted in Probability and statistics | Leave a comment