Numb3rs

Jeg lovede mere om spilteori i går aftes. Det kommer her.
Jeg har skrevet om Fangernes Dilemma tidligere på bloggen, men det er kun et af mange eksempler på spilteori.
Overordnet er spilteori en del af anvendt matematik. Man modellerer situationer, hvor flere interessenter, spillere, træffer beslutninger, der er indbyrdes afhængige. Den enkelte spiller er derfor nødt til at overveje de andres mulige strategier for at beslutte sig for sin egen strategi.

Dette overordnede synspunkt beskriver mange situationer i økonomi, og spilteori blev oprindeligt udviklet af John von Neumann (ja, det er også ham med de cellulære automater) og Oskar Morgenstern.
Man kan forestille sig mange forskellige scenarier for sådan et spil:

• Hvor mange spillere er der
• Hvilke strategier har hver enkelt spiller til sin rådighed
• Hvad er udbyttet for de forskellige spillere på forskellige stadier (bliver man fanget, tjener man en masse penge, kommer man i fængsel i 16 år,…)
• Skal alle “flytte” samtidig (er spillet simultant)
• Hvor meget ved hver spiller om de andres strategier, tidligere flytninger etc. (er spillet med perfekt information, fuldstændig information, imperfekt information,…)
• Er det samlede udbytte konstant eller variabelt
• Hvor mange flytninger må man lave, etc.

Hvor er matematikken så? Når man beskriver et spil, kan man f.eks. gøre det ved at lave en funtion, som for hver kombination af strategier eller flytninger for alle spillere giver udbyttet for alle spillere. Man kan beskrive det i et “træ”, med et startpunkt, hvor hver gren udfra startpunktet svarer til en af de flytninger, man kan lave – enten svarer en gren til alle spillere på en gang eller en spiller for hver gren, alt efter hvilken type spil det er.

Matematikspørgsmål er f.eks.

• Er der en Nash-ligevægt for spillet, hvor ingen spillere kan vinde noget ved at skifte strategi, medmindre en eller flere andre også skifter. John Nash fik Nobelprisen i økonomi for at vise, at der for en meget stor klasse af spil altid er mindst en Nash ligevægt.
• Er der andre typer ligevægt – det vil blive for langhåret at komme ind på her, men se Wikipedia
• Hvor lang tid/hvor mange flytninger skal der til, før man når en ligevægt?
• Er der en vindende strategi for en eller flere spillere

I Numb3rs i går omtaltes en artikel “Naive strategies in zero-sum games” af A.Rubinstein, Tversky og Heller, hvor de har lavet eksperimenter med “Hide and Seek” (skjul) spil; de res forsøgskaniner var studerende. Det viser sig, at man ikke kan gå ud fra, at mennesker opfører sig, som de “skal” ifølge spilteorien – og de teoretiske ligevægte giver ikke mening.
Det er endnu et eksempel på, at man skal være varsom med anvendelser, hvor man forsimpler mennesker for meget.
Spilteori bruges idag f.eks. i forskning i kunstig intelligens. Der er der måske også mere styr på, hvilke mål de enkelt har, og hvad de har lyst til at optimere.
Desuden anvendes det f.eks. i økonomi, biologi, sociologi, logik, filosofi og studie af vælgeradfærd.

Hilsen
Lisbeth www.math.aau.dk/~fajstrup
numb3rs@math.aau.dk

Hej Bloggere.

Matematikken spillede helt ærligt ikke en stor rolle i opklaringen denne gang, men Charlie fortalte om spilteori, en enkelt kode og så byggede Larry og Charlie papirflyvere…

Flydesign
Larry og Charlie bygger papirflyvere. Larry vil bygge Verdens bedste papirflyver, som i øvrigt ligner den, min far har lært mig at bygge engang. Han har problemer med den 11’te kritiske fold. Der er meget matematik (og fysik) i at bygge fly, men jeg tror nu, papirfly er udviklet eksperimentelt, som Don også bemærker – i eftersidningstimer på skoler i den ganske verden.
Den matematik, der indgår i design og analyse af flyvinger, er partielle differentialligninger. Det er ligninger, hvor den ubekendte er en funktion af flere variable, og der indgår i ligningen både funktionen og dens afledte mht. de forskellige variable – hvor hurtigt funktionen ændrer sig, hvis man ændrer på en af de variable. I sidste uge var differentialligningerne ikke partielle. Den eneste variable var tiden. Igen er der tale om ligninger, hvor vi typisk ikke kan finde specifikke løsninger. Derfor er det væsentligt at have resultater om,

• Hvorvidt der faktisk er løsninger (eksistens)
• Om der er mere end en løsning (entydighed)
• Om de tilnærmelser til løsninger, vi får ud af diverse computerprogrammer er tæt på den rigtige løsning
• Hvordan man laver den slags computerprogrammer – Marsha Berger samarbejder med NASA om programmer til simulering af aerodynamik omkring fly. Se også programmets hjemmeside.

I 1998 fik Cathleen Synge Morawetz “National Medal of Science” som den første kvindelige matematiker. Hun fik den bl.a. for sit arbejde med aerodynamik. Hun viste sidst i 50’erne, at chokbølger er uundgåelige uanset, hvordan flyvingerne er designet. Og derfor arbejder man nu med at minimere effekten af chokbølger i stedet for at forsøge at undgå dem. Når et fly flyver hurtigere, end lydbølgerne kan bevæge sig (over Mach 1), opstår der chokbølger. En lang teknisk forklaring får I ikke – sådan en kan jeg faktisk ikke – men groft sagt handler det om, at lydbølger, som ville bevæge sig i kugleform udfra det sted, hvor de starter, ikke kan bevæge sig fremad i flyets retning – så hurtigt kan de jo ikke bevæge sig. Derfor opbygges der et højere tryk, og en skarp overgang mellem dette tryk og “længere fremme” Denne grænse er chokbølgen. Chokbølgen udbreder sig hurtigere end lydens hastighed. Den aftager ret hurtigt i intensitet og bliver til en lydbølge, som vi kan høre. Læs mere og se billeder på Wikipedia
Den slags forskning sponseres ofte militært – men det kan man næsten sige sig selv.

Kryptering.
Den krypterede meddelelse, Charlie skal bryde, er desværre krypteret ret plat, så den er nem at læse med moderne metoder. Der er brugt en ombytningskode, hvor bogstaverne er byttet rundt efter et eller andet aftalt system. Man kan f.eks. tage sin lange meddelelse og skrive den op med fem bogstaver ad gangen, under hinanden:
Numb3rs er et glimrende program
bliver til
Numb3
rsere
tglim
rende
progr
amaba
(de sidste tre bogstaver er bare fyld.
Så læser man det på den anden led:
Nrt rpa usg erm mel noa bri dgb 3em era
og det er jo ikke lige til at genkende. Man kan også vælge at bytte om på søjlerne, før man skriver det ud som tekst.
For at bryde det, skal man finde længden af rækkerne, og det går her op i længden af teksten, hvilket jo gør det noget nemmere.
Man kan kombinere, så man krypterer den nye tekst en gang til. Det blev brugt af det tyske militær under første verdenskrig, men blev brudt af franskmændene. Under 2. Verdenskrig blev den slags “dobbelt transposition” brugt af den hollandske modstandbevægelse.
Man kan se af teksten, at det er en transposition ved at se på forekomsten af de enkelte bogstaver. Hvis de forekommer lige så hyppigt relativt, som i normal tekst, er det formentlig en transposition. Derefter leder man efter anagrammer i teksten; det kan man nok gøre ret effektivt på en computer. Charlie gør det ved at stirre intenst på teksten og opdage typiske ord fra hans tid i NSA – imponerende.
Denne type kryptering var i brug et stykke ind i 50erne.
Man kan kombinere metoden med f.eks. at skrive teksten i Morse først. Derefter “bytter man rundt” på prikker og streger efter systemet ovenfor. Så bliver det rigtig vanskeligt at bryde.

Jeg har skrevet om andre krypteringer tidligere på bloggen.

Spilteori
Charlie snakkede om topersoners “gemmeleg” efter Rubinstein Heller og Tversky.
Han hentyder her til en artikel, som jeg finder et link til i morgen – det er ved at være sengetid. Men her er Rubinsteins hjemmeside med en alenlang publikationsliste…
Man studerer to personer, som skal hhv. gemme sig og finde. De har hver nogle strategier, de kan vælge, og dem vælger de efter, hvad de mener, den anden vil gøre. Den, der leder, vinder, hvis hun finder den anden, og ellers vinder den, der gemmer sig. Man kan have ligevægte i sådan et spil, hvor den, der gemmer sig, hele tiden flytter sig, inden den, der leder, kommer til gemmestedet.
Charlie foreslår, at man ved at ændre strategi kan få forbryderen til at ændre strategi. Og med den lille krølle, at man bilder forbryderen ind, at man ændrer strategi, og så bliver han fanget ved sin ændrede strategi.
Der er forskellige typer ligevægte, hvor alle i teorien vil blive ved med at bruge samme strategi. For eksempel fordi alle ved, at den strategi, de bruger nu, er den bedste, så længe de andre ikke skifter strategi. (En Nash ligevægt, så vidt jeg husker)
Vi skal vist have noget mere om spilteori på bloggen. Men det bliver ikke nu.

Hilsner
Lisbeth www.math.aau.dk/~fajstrup
numb3rs@math.aau.dk

Hej Bloggere.
Idag brugte Charlie igen betingede sandsynligheder, som jeg skrev om for et par gange siden her på bloggen. Det var sådan, han vurderede sandsynligheden for, at de foreksllige personer havde gjort det. Men der var mere matematik i baggrunden. Der var f.eks. noget om “pruning” af træer – gad vide, om det hedder at styne dem på dansk? Nå, det har jeg ikke noget med om idag. Jeg har valgt at skrive om handel med futures (det var det, morderen havde tjent penge ved) og om vektorfelter, som man bruger til at beskrive noget, der flyder – som vandet på Charlies gulv. Det er nok lettere at læse det om vektorfelterne først, så gør endelig det.

Der var forresten også noget om, at Charlie havde analyseret firmaets regnskab allerede i forbindelse med svindelsagen. Det lyder lidt mystisk, men måske har han brugt et ekspertsystem (som vi også har haft oppe tidligere på bloggen) til at finde steder i regnskabet, hvor det ser uldent ud.

Futures og optioner.
Finansiering er et område, der anvender meget avanceret matematik og beskæftiger mange matematikere. I denne episode var det en del af plottet, at virksomheden havde spekuleret i futures eller optioner. I stedet for at købe (eller sælge) aktier til den kurs, de har idag, kan man købe retten til at købe (eller sælge) aktier til en bestemt pris en bestemt dag – som jeg forstår det, er futures en pligt til at købe/sælge, mens optioner er muligheden for det. Er aktierne så steget til en højere pris end den, man aftalte, har køberen tjent penge – hvis ikke prisen på optionen var for høj.
Hvad skal prisen så være? Ja, der kommer matematikken ind. I 1997 fik Myron Scholes og Robert Merton Nobelprisen i økonomi for Black-Scholes modellen, som er en model for prisfastsættelse af netop optioner. (Fischer Black døde i 1995 – så han kunne ikke få Nobelpris i 97.)
Hvis jeg ejer nogle aktier i et firma, kan jeg have interesse i at sælge købsoptioner for at minimere min egen risiko. Og jeg får penge for at sælge optionerne, så jeg overlader noget af risikoen til den, der har købt optionerne.
Prisfastsættelsen udledes fra en avanceret differentialligning; man vurderer bl.a. hvad ændringen i prisen vil være, hvis aktierne stiger. Og man sammenligner med, hvad man kan få ud af at anbringe de samme penge risikofrit og med fast forrentning. Desuden afhænger prisen af, hvor lang tid der er, til optionen kan/skal indfries. Det er betydelig mere kompliceret – formlen kan ses her.
Differentialligninger, hvor man ved noget om variationer af en funktion og derfra kan sige noget om funktionen, er ikke helt nok. Man skal bruge stokastiske differentialligninger hvor der indgår ikke-deterministiske elementer (f.eks. prisen på aktierne som tiden går) i ligningen. Her er den stokastiske differentialligning for
Black -Scholes.

Vektorfelter
Larry hælder blæk i en vandpyt på Charlies gulv for at se hvad vej, vandet strømmer, hvilket inspirerer Charlie til at “følge pengestrømmen”, eller hvordan det nu var.

Når man skal beskrive, hvordan en væske strømmer, gør man det normalt ved hjælp af et vektorfelt. En vektor er simpelthen en “pil” – en retning og en længde, der repræsenterer, hvor hurtigt det strømmer i den retning. Man skal altså have sådanne pile overalt i væsken, for noget af væsken kan jo f.eks. stå stille, mens andet strømmer rundt om det. Hvis vi nu lader vores væske være ret flad, kan vi tænke på, at der er pile alle steder i (et stykke af) planen. Hvis vi så smider en pind i vandet, kan vi følge pilene og se, hvor den kommer hen.
Her er nogle eksempler på vektorfelter i planen:

(hentet fra Weisstein, Eric W. “Vector Field.” Fra MathWorld–A Wolfram Web Resource. https://mathworld.wolfram.com/VectorField.html)

Den kurve, pinden følger, når vi har smidt den i vandet, er løsning til et system af differentialligninger: Vektorfeltet beskriver tangenter til kurver. Man skal finde kurver, hvis tangenter passer. Pinden flyder langs sådan en kurve.

Man kan få tegnet vektorfelter flere steder på nettet: Her er et af dem. Et vektorfelt i planen beskrives med to funktioner x’ = f(x,y) og  y’ =g(x,y) – vektoren i punktet (x,y) har koordinater (f(x,y),g(x,y))  – det kan man se eksempler på i tegningerne ovenfor. Ved at åbne “PPlane” får man mulighed for at klikke et sted på vektorfeltet (smide en pind i vandet der) og få tegnet, hvor den flyder hen – den kurve, der følger vektorfeltet.

Differentalligninger og systemer af differentialligninger er uhyre anvendelige som modeller for fysik, økonomi, biologi etc. Og selvfølgelig som ren matematik: Hvad skal man vide om et vektorfelt, for at være sikker på, der er kurver, der følger vektorerne? Hvor lange bliver de kurver? Er der stor forskel på, om jeg smider en pind i her eller lige ved siden af? Osv.
Man kan sige meget ved at se på geometrien – ved kvalitative betragtninger, uden at løse ligningerne. Hvilket er heldigt, for vi kan normalt ikke løse dem på pæn form med [tex]x^2[/tex] og sin(x) og andre pæne funktioner.

Hilsen
Lisbeth www.math.aau.dk/~fajstrup

numb3rs@math.aau.dk

Hej Bloggere.
Idag havde Charlie nok at se til, og der var meget matematik på banen: Billedbehandling ved brug af curvelets, positionsbestemmelse udfra billeder af skyggen af en basketkurv, håndskriftsanalyse og nogle bemærkninger om Chvatals galleriproblem.

Positionsbestemmelse via solursprincippet “brugt omvendt”.
Udfra skyggen fra en basketballkurv på to tidspunkter samme dag, bestemmer Charlie, hvor i Verden, basketballkurven befinder sig.
Det er med andre ord udfra solens position på himlen og klokkeslettet, man kan sige noget om, hvor basketballkurven er. Det er det omvendte af, hvad man gør, når man laver solure. Da skal man bruge skyggen til at sige, hvad klokken er, og skyggen afhænger netop af solens position på himlen.

Solens bane henover himlen afhænger af, hvad breddegrad vi er på, og hvilken dag på året det er. Jeg giver en grov forklaring her – mere detaljeret forklaring findes f.eks. på Almanak.
Klik på et sted på Danmarkskortet under linket almanak. Så får man dels de geografiske koordinater (længde og breddegrad) for stedet, og linket “Solens bane og højde” viser bane og højde på netop dette sted. Man kan også vælge hvilken dato, man ønsker banen beregnet for.

I princippet står solen højest på himlen klokken 12, men klokken 12 i Danmark er det tidspunkt, hvor solen står højest ved længdegraden 15 grader. Det kan man se som følger: I England har man den tid, der svarer til længdegrad 0, Greenwich-meridianen. Det tager 24 timer for Jorden at rotere en gang rundt om sig selv, så 360 længdegrader svarer til 24 timer. Altså er en time 15 grader, og 1 grad er 4 minutter. Men vi vil ikke stille på uret, hver gang vi kører en tur mod øst eller vest. Til gengæld passer det ikke, at solen står højest i Aalborg klokken 12. Derfor er der en tidskorrektion. For Aalborg, som ligger på ca. 10 grader længde, er tidskorrektionen -5x4minutter = -20 minutter. Vi ligger 5 grader vest for længdegraden 15 grader. Prøv 3D simulation på linket her. Det viser solens gang over himlen i forhold til en horisontal plan på den koordinat, man har angivet. For Aalborg er breddegraden ca. 57 grader. OBS. Der går lidt tid, før der sker noget, når man skriver “run” – solen skal jo lige stå op først.
På almanakken om soltid er en mere præcis forklaring. Det tager ikke lige lang tid for jorden at rotere fra, at Aalborg vender direkte mod solen til Aalborg vender direkte mod solen igen. Det afhænger af, hvor Jorden er i sin bane omkring solen. Så 24 timer er den tid, det i gennemsnit tager – set henover et år. Læs mere under almanakken – der er også en effekt af, at Jorden er tiltet lidt i forhold til sin bane omkring Solen (ca. 23 grader). Der er forklaringer på mange ting, og beregningerne af solopgang etc. er ikke tabelopslag, men beregnes, når man beder om dem. Den underliggende matematik er f.eks. beskrevet i matlex, hvor man også kan se, hvordan man laver et solur.

Prøv også at vælge timecorrection =0, og vælg Year under 3D-simulation her og lad klokken være 12:00 (når du har åbnet for 3D og year). Det giver en kurve over, hvor solen står på himmelkuglen klokken 12, henover året. Det er ikke i syd hele året, men laver et ottetal.

I programmet lykkes det Charlie at bestemme positionen med en nøjagtighed på 1/100 grad – så må han i hvert fald have styr på sin solursmatematik. Men det har han også, for han og Larry er medlemmer af den amerikanske solursforening. Gad vide, om der er en dansk solursforening.

Matematikken bag regningerne er beregninger på kugleflader. For at vide, hvor skyggen af et basketmål er, skal vi kun kende retningen til solen – afstanden betyder ikke noget. Derfor er solens bane tegnet ind på en (halv)-kugleskal, som repræsenterer alle de retninger, vi kan kigge i fra det punkt på Jorden, hvor vi står. Der er en Nord-Syd akse og en Vest-Øst-akse, og en retning lige opad.
Geometri på kuglefladen er anderledes end den sædvanlige i planen. For eksempel kan man lave trekanter, hvis vinkler allesammen er rette. Og alle trekanter har vinkelsum større end 180 grader. Desuden er omkredsen i en cirkel med radius r mindre end 2 pi r.

Håndskrift og matematik.
At genkende en persons håndskrift er en slags billedgenkendelse. Og det har vi set på tidligere her på bloggen: 9/11-2006 hvor Arne Jensen skrev om Wavelets – eller skvulp. Matematikken bag analyse af håndskrift kan f.eks. være “curvelets”. (Jeg ved ikke, om nogen har et godt dansk ord a la skvulp). I programmet blev curvelets også brugt til billedanalyse. Her er en artikel om klassifikation af gamle manuskripter ved hjælp af curvelets. Ideen er, at der er karakteristiske egenskaber ved hver persons håndskrift, som man kan udkrystallisere ved at beskrive håndskrevne dokumenter som en sum af curvelets. Ligesom man har brugt wavelets til at finde ud af, om et maleri faktisk var af Breughel eller ej. Se lidt om det på bloggen fra 1/11-2006.
Curvelets dyrkes bl.a. på CalTech, hvor matematikerne bag Numb3rs har til huse. Hovedmanden bag curvelets er Emmanuel Candes og hans PhD-vejleder David Donoho. I øvrigt er Charlie’s universitet, CalSci et frit opfundet universitet, men mange optagelser er fra netop CalTech. Man overvejede at lade Charlie arbejde på CalTech, men universitetet forlangte til gengæld at godkende episoderne. Måske er det dårlig PR for et universitet, hvis en TV-serie handler om alt for mange studerende, der tager livet af hinanden eller tilsvarende.

Hilsen Lisbeth www.math.aau.dk/~fajstrup
numb3rs@math.aau.dk

I udsendelsen 7/3 foreslog Amita, at der var brugt 1-dimensionale Cellulære Automater til at generere tilfældige tal (til bilnøglerne) og jeg lovede at skrive lidt om Cellulære automater (CA).
En 2-dimensional CA kan man tænke på, som et uendeligt stort kvadreret stykke papir. Hvert lille kvadrat kaldes en celle, og de kan være enten sorte eller hvide. Man starter med en eller anden farvning af alle cellerne, og så er der spilleregler for, hvordan det udvikler sig. Udviklingen foregår i trin. Og spillereglerne kan f.eks. være: En celles naboer er de 8 celler, der enten deler en side eller et hjørne med cellen. Reglerne for en bestemt CA, nemlig John Conways
Game of Life er:
Kald en sort celle “i live” og en hvid “død”.
1) Hvis en levende celle har to eller tre levende naboer, forbliver den i live. (Har den flere end tre, dør den af overbefolkning; har den kun 1, dør den af ensomhed.)
2) En død celle med præcis tre levende naboer kommer til live.

De udregninger (af, om en celle er i live i næste generation eller ej), laves for alle celler, inden der skiftes farve i nogen af dem.
Cellulære Automater blev studeret af John Von Neumann, som ville se på, om man kan lave maskiner, der kan bygge kopier af sig selv – nærmest robotter, der formerer sig. CA’er er en abstraktion fra det oprindelige problem.

En 1-dimensional CA er en ret linie opdelt i intervaller, cellerne. Man laver så regler for, hvad farve en celle har udfra dens egne og de to naboers farver. Lad nu 1 være sort og 0 være hvid. Så er der 8 muligheder for farver på en celle og dens naboer: 000, 001, 010, 011, 100, 101, 110, 111 (Kender man binære tal, ser man, det er tallene fra 1 til 8). En regel for udvikling skal for hvert af de 8 nabolag bestemme, om cellen i midten skal være sort eller hvid i næste generation. Der er altså 2^8=256 forskellige regler.
Nogle spilleregler vil være sådan, at man udfra et mønster af sorte og hvide celler kan se, hvilket mønster, det var i sidste generation – de kaldes reversible.

CA er et eksempel på, at noget kan se tilfældigt ud, selvom det er frembragt af fuldstændigt forudsigelige regler. Bruger man 1 dimensionale CA’er til at frembringe tilfældige tal (binært). Er det altså slet ikke tilfældigt.

På Wikipedias side om CA kan man se eksempler på, hvordan en linie med en celle sort og alle andre hvide, kan udvikle sig, alt efter reglerne.

Der findes diverse steder på nettet, hvor man kan lege med CA. Og mange har et Game of Life som pauseskærm.

Hvis man skriver Cellulær Automat i Google, finder man links om biologi, musik, arkitektur, økonomi, kognitiv sprogvidenskab og meget mere. Der er altså mange steder, hvor den abstraktion giver mening.

Man kan stille mange spørgsmål om CA’er; Kan man lave en enkelt figur, som vil bevæge sig ud “mod uendelig” (Ja, i Game of Life – en “Glider”).
Hvis du har gode danske links (og såmænd også engelske) med f.eks. Java applikationer, så skriv endelig.
Hilsen Lisbeth www.math.aau.dk/~fajstrup
numb3rs@math.aau.dki

I “Bettor or Worse” forklarer Charlie Amita om Farey følger. Det er den slags tal, man finder som odds, men skrevet som brøker, så odds 2:9 skrives 2/9.
Farey følge nummer N, eller Fareybrøkerne af orden N, er uforkortelige brøker på formen r/s, hvor s ligger mellem 1 og N, og de skrives op efter størrelse – en følge er ikke bare en mængde tal, men også en bestemt rækkefølge. Fareyfølgen for N=9 og i intervallet fra 0 til 1, er
0/1,1/9,1/8,1/7,1/6,1/5,2/9,1/4,2/7,1/3,3/8,2/5,3/7,4/9,1/2,5/9,4/7,3/5,5/8,2/3,5/7,3/4,7/9,4/5,5/6,6/7,7/8,8/9,1/1
Skriver man Farey-følgerne op under hinanden:
0/1, 1/1
0/1, 1/2, 1/1
0/1, 1/3, 1/2, 2/3, 1/1
0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1
0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1
0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1

(her har jeg skrevet fra N=1 til N=6) kan man se, at der er forskellige systemer i galskaben.
Betragter man Farey-følgen for N=9 som succesrate for op til 9 skud på mål, kan man forstå lidt af systemet. Så 5 skud på mål med to succeser repræsenteres som 2/5. Og vi forkorter altid brøkerne.
Har man haft 5 skud og 2 mål og derefter 3 skud og 1 mål, har man ialt haft 8 skud og 3 mål, så man lægger tæller og nævner sammen – forkert brøkregning! 2/5 med 1/3 bliver 3/8. Det kaldes medianten – så det er ikke ulovligt, det er bare ikke summen af brøkerne.
Se på farey følgerne ovenfor. Fra række 3 til række 4 indsætter man 1/4 mellem 0/1 og 1/3. Og 1/4 er netop medianten af 0/1 og 1/3. Det er systemet i at regne den næste følge ud – kig selv efter. Og hvis man har tre på hinanden følgende tal x < y < z i en bestemt Farey følge, så er y medianten af x og z.
Er r/s < a/b to på hinanden følgende brøker i en Farey-følge, da er as-rb=1. Og i øvrigt omvendt: Hvis ad-bc=1, da er a/c og b/d to på hinanden følgende termer i en Fareyfølge. Og det er a/b og c/d også

Tæller man antallet af brøker i Farey følge nummer N, så nærmer det tal sig 3(N/pi)^2, jo større N bliver. Så det er et eksempel på en mystisk optræden af pi, som beskrevet tidligere på bloggen.
Der er flere pudsige egenskaber ved farey-følger. se f.eks Wikipedia eller Mathworld

Beviser kan man finde mange steder, men man kan jo også overveje, hvordan det mon skal gribes an. Farey kunne ikke bevise sine påstande, selvom han beskrev mange af dem.

Hilsen Lisbeth www.math.aau.dk/~fajstrup
numb3rs@math.aau.dk

Hej Bloggere.
Matematikken i dette afsnit af Numb3rs var, set fra min udkigspost, Om fjernbetjente bildøre, Farey-følger, cellulære automater, trafikovervågningssystemer og noget med, hvordan bookmakere sætter odds. I får en hel del om bildøre og om Farey-følger, men de cellulære automater og odds må I vente med til en anden gang.

Om fjernbetjente bildøre
Hvad skal en fjernbetjening til bildøre egentlig kunne?
1) Åbne min bil og ikke naboens
2) Hvis jeg opsnapper signalet fra naboens fjernbetjening, kan det ikke genbruges – jeg kan ikke åbne naboens bil ved at sende det signal til den.

Problemet er i kategorien “deling af hemmeligheder”, og “identifikation” (authentication – er den, jeg modtager signalet fra, den rigtige) men det er lidt mere indviklet. Jeg har læst mig frem til, hvordan General Motors gør: Bilen og nøglen har fra starten indkodet to hemmelige tal.
Men dem kan nøglen ikke sende – så er betingelse 2) ikke opfyldt.
I det Lean-systemet, som bl.a. bruges af General Motors, er metoden patenteret i to patenter
Pseodorandom number generation and cryptographic authentication
og
Method of generating secret identification numb3rs
En af dem, der har lavet systemet, Philip Koopman, skrev et indlæg om systemet på vores amerikanske søsterblog her.
Kort fortalt fungerer det sådan:
Nøglen genererer et tilfældigt tal. Det sættes sammen med det ene af de hemmelige tal (foran eller bagved eller de flettes sammen 22222 flettes med 33333 som 2323232323) og det samlede tal krypteres.
Det andet hemmelige tal krypteres og de to krypterede tal sættes sammen – efter hinanden eller flettet.
Så krypteres igen. Resultatet sendes til bilen som en række 0’er og 1’er.
Bilen dekrypterer, finder de to hemmelige tal og det tilfældige tal. Den gemmer det tilfældige tal (hvis ellers de hemmelige tal passer) og låser bilen op.
Næste gang bruges det tilfældige tal, som bil og nøgle nu deler, til at lave det nye (pseudo)tilfældige tal. Man krypterer det, og sætter det sammen med det andet hemmelige tal, og så starter man som ovenfor.

Bilen kan nu genfinde det tilfældige tal fra før, foruden de to oprindelige hemmelige tal.

Krypteringen er ikke så stærk som den, der bruges i bankoverførsler og lignende, og systemet kan altså brydes, hvis man har nøglen og kan se en række af de signaler, den sender. Derfor kan man, så vidt jeg ved, også kopiere nøgler, hvis man er kvik og har det rette udstyr.
I Lean systemet er krypteringen forskellig fra gang til gang, og afhænger af den fra sidste gang, så når bilen dekrypterer, skal bil og nøgle være synkroniserede, altså enige om, hvilken kryptering/dekryptering, der bruges. Det kan bilen ikke vide, hvis nu ungerne har leget med nøglen, eller jeg har sat mig på den og dermed trykket, uden at bilen var i nærheden. Så bilen afprøver de næste 256 dekrypteringsmåder. Hvis ikke de giver et resultat, der matcher, åbner den ikke. (Det tager ialt 1/2 sekund). Virker nøglen ikke, kan man genstarte ved at trykke på to knapper (tror jeg nok), og så starter proceduren forfra. Det samme sker, hvis batteriet er løbet tør.

Og hvor er så matematikken? I kryptering, i generering af tilfældige tal og i generering af de hemmelige tal til bil og nøgle på fabrikken: hvordan sikrer man, at man ikke genbruger dem? Når man samtidig ikke ønsker at have en database med alle de hemmelige tal; den kunne blive stjålet, og så kunne man låse sig ind i alle General Motors biler. Det er det, det andet patent handler om. De hemmelige tal frembringes fra støjen fra en ventilator! Og man bruger en såkaldt hashfunktion (nej, det har intet med hash at gøre) på de to tal. Det tal, man får ud af det, gemmer man. Hvis to nye hemmelige tal giver samme tal i hashfunktionen, kasseres de. Pointen er, at databasen med alle hashværdierne ikke kan bruges til at genfinde de oprindelige hemmelige tal.
I øvrigt er der også matematik involveret, når signalet sendes – der er en fejlkorrigerende kode, som sørger for, at det signal, bilen får, kan rettes til, hvis det er blevet forstyrret på vejen fra nøgle til bil. Læs mere om fejlkorrigerende koder og i øvrigt om deling af hemmeligheder på Olav Geils populariseringsside. Se f.eks. det korte foredrag om fejlkorrigerende koder. Og måske linket til DTU længere nede.

Tilfældige tal kan frembringes på mange måder. Amita nævner cellulære automater, og det er det, der giver Charlie løsningen. Dem må I vente med til en anden dag. Fareyfølgerne er i næste indlæg på bloggen.

Hilsen Lisbeth www.math.aau.dk/~fajstrup
numb3rs@math.aau.dk

Udsendelsen Judgement Call fra 28/2 blev genudsendt søndag 4/3 klokken 21.
Søndag 11/3 kl.20 er der genudsendelse af numb3rsudsendelsen fra 7/3.
Man kan vel antage, at der fremover er genudsendelser om søndagen.

Hilsen Lisbeth www.math.aau.dk/~fajstrup
numb3rs@math.aau.dk

I udsendelsen i går brugte Charlie origami som et eksempel på, at man kan frembringe meget komplekse ting udfra få grundregler.
Origami er den japanske papirfoldningskunst, hvor man starter med et kvadratisk stykke papir, normalt farvet på den ene side, så folder man “nedad eller opad” (bjerge eller dale) og ender med flotte figurer. Men hvilke figurer kan man faktisk folde? Erik Demaine, Martin Demaine og Joseph Mitchell viste, at enhver sammenhængende figur lavet af polygoner, (et polyeder), kan laves som origami. Og ydermere: Hvis man for hver polygon, der indgår, bestemmer, om den skal være hvid eller farvet, kan man lave en origamiopskrift, så man får den farvede side udad på de rigtige steder. De bruger, så vidt jeg kan se ikke et kvadratisk stykke papir – det kan være et rektangel. Beviset er konstruktivt. Der er en algoritme, der giver en foldningsopskrift.

Det lyder jo mildt sagt som temmelig akademisk, men foldning er væsentligt mange steder:
Foldning af airbags, af teleskoper, der skal sende ud i rummet, af proteiner, find selv på mere.

Man har også studeret, hvilke origamifigurer, der kan “trykkes flade” (flatfoldability). Og hvilke mønstre af linier på et stykke origamipapir, der kan komme fra at man har foldet en figur ud igen. Det kender vi godt – når man skal have foldet landkortet sammen igen og helst vil bøje op og ned de samme steder, som det var, da man købte det. Se Erik Demaines When can you fold a map.

Mange af spørgsmålene minder om de klassiske geometrispørgsmål: Hvad kan man konstruere med passer og lineal. Altså, hvis man har grundreglerne, hvad kan man så opnå. I moderne matematik vil man typisk også spørge: Kan man få en computer til det, og hvor vanskeligt er det – altså algoritmiske spørgsmål. Eksempelvis: hvis man giver en computer et knækmønster (streger på et stykke papir) kan den så give en opskrift på en origamifigur, der har netop det mønster? Flatfoldability et NP-fuldstændigt – se Hans Hüttels artikel fra 29/9-06 om P versus NP,

Der er masser af matematik i origami. jeg har sat links ind her til et par artikler og hjemmesider; man finder let flere ved at Google origami og matematik eller mathematics
med undervisningsforslag
Artikel af Barry Cipra
På mathworld – flotte billeder! og man kan se et forslag til axiomerne (grundreglerne) for origami. Der er ikke enighed om, hvad de skal være.

Hilsen Lisbeth Fajstrup. www.math.aau.dk/~fajstrup
numb3rs@math.aau.dk

Hej Bloggere.
Så kom vi endelig igang med sæson 2.
Der var igen en del matematik (og forviklinger i Dons og Charlies forhold til kvinder, men det blander vi os ikke i her på bloggen).
Jeg så noget om eksponentiel vækst, origami, Bayesiansk filtrering og beslutningsstøtte og noget om pi. Eksponentiel vækst har været på bloggen før, så det tager jeg ikke med i aften, men måske senere. Origami venter jeg også med (de utålmodige kan google origami og mathematics sammen – det giver spændende links). Så det bliver noget om Bayes og noget om pi.

Bayes’ formel og beslutninger.
Charlie og Megan Reeves – ny i serien – vil gerne finde de mest sandsynlige mistænkte blandt en lang række, der kunne have motiv til at slå dommerens kone ihjel. Han ved altså, der er begået et mord, og skal finde morderen eller en række personer, som med en vis sandsynlighed har gjort det. Men sagsmapperne siger jo noget andet, i hvert fald i første omgang.
Lad os gøre det meget simpelt, og nej, så simpelt var det ikke i udsendelsen: Hvis Olsen har begået mange mord, eller hvis han er medlem af en bestemt bande, eller har særlig grund til at være vred på dommeren eller hans kone etc. er der en vis sandsynlighed for, at han har gjort det. Man mener måske, at sandsynligheden for, at Olsen begår et mord, hvis Olsen begår noget kriminelt, er 2%. Det er en betinget sandsynlighed: P(M|O), hvor M står for Mord, O står for “Olsen har gjort noget kriminelt”. (Den slags sandsynligheder er selvfølgelig svære at finde, og bygger på diverse skøn, som Megan kan fortælle Charlie om; men nu har jeg jo også forsimplet det ganske enormt her, så vi går lystigt videre). Det er jo omvendt: Vi ved, at der er begået et mord. Vi ved ikke, om Olsen har gjort noget. Og hvad med alle de andre kriminelle.
Faktisk vil vi hellere kende P(O|M), sandsynligheden for, at Olsen har gjort det, givet “det” er et mord.

Lad os sige, at der kun er tre kriminelle i denne verden, Olsen, Hansen og Jensen. Fra deres tidligere gerninger har vi sandsynlighederne for, at det, de har begået, hvis de har begået noget kriminelt, er er et mord; ADVARSEL – her kommer formler- spring over dem, hvis det er for meget-
P(M|O)=2%=0,02
P(M|H)=2%=0,02 og
P(M|J)=3%=0,03
Vi ved måske også noget om sandsynligheden for, at de hver for sig begår en forbrydelse
P(O)=1/2
P(H)=1/4
P(J)=1/4
(Samlet 1, for vi ved, der er begået noget.)
Sandsynligheden, for at Olsen begår et mord, er P(M|O)P(O)=0,02×0,5=0,01
Sandsynligheden, for at Hansen begår et mord, er
P(M|H)P(H)=0,02×0,25=0,005
og for Jensen får vi
P(M|J)P(J)=0,03×0,25=0,0075

Så sandsynligheden for, at der bliver begået et mord, er
P(M)=0,01+0,005+0,0075=0,0225
Jamen der ER jo begået et mord, så hvad skal vi bruge det til? Jo, Bayes’ formel siger, hvordan man “vender det om”:
P(O|M) er sandsynligheden for, at det er Olsen, der har gjort det, givet “det” er et mord.
Den finder man ifølge Bayes’ formel som
P(O|M)=P(M|O)P(O)/P(M)=0.01/0,0225=4/9

Tilsvarende har vi
P(H|M)=0,005/0,0225=2/9
P(J|M)=0,0075/0,0225=3/9
Så det er mest sandsynligt, at Olsen har gjort det. (Eksemplet her er planket fra min amerikanske blogkollega, se link til højre – så slap jeg for at regne…)

Man kan jo ikke gå ud og anholde Olsen på det grundlag; en udregning af denne type (eller rettere en kombination af en hel masse udregninger) indgår i et beslutningsstøttesystem. Man kan bruge den slags systemer som en støtte, men de kan naturligvis ikke stå alene.

Beslutningsstøttesystemer bruges mange steder. At finde sandsynlige årsager ud af en stribe mulige årsager er forbavsende nyttigt: Hvorfor hoster patienten? Er det lungebetændelse, forkølelse, tuberkulose, rygerlunger,… Vi ved noget om hvor mange patienter med lungebetændelse, der hoster, hvor mange (procentdel) der har lungebetændelse (og forkølelse…) Og vi skal have vendt det om. Det kan være meget mere indviklet med en lang stribe: A kan forårsage B, som kan forårsage C… og der er andre mulige årsgaer til B, C,… (Charlie tegnede en figur med pile mellem diverse cirkler – pilene indikerer hvad der kan forårsage hvad). Man kan læse mere om især landbrugets brug af beslutningsstøtte i en artikel fra Naturens Verden fra 1998. Steffen Lauritzen, som er den ene af forfatterne, lavede sammen med David Spiegelhalter en algoritme, som gør, at Bayesianske beslutningsstøttesystemer virker. I princippet skal computerne bare regne og bruge Bayes’ formel rigtig mange gange, men hvis ikke det organiseres intelligent, tager det alt alt for lang tid, selv for en hurtig computer. Steffen var professor i statistik i Aalborg indtil 2004, hvor han blev professor i Oxford.
Bemærk, hvordan den matematik, der bruges til beslutningsstøtte, er den samme i landbrug, af FBI, i retsgenetik,… Det er da smart!

Om pi og dets opdukken mange steder
Charlie snakker om, at pi (det græske bogstav, men det kan man ikke skrive i bloggen) dukker op i uventede sammenhænge. Pi er jo forholdet mellem omkreds og diameter af en cirkel, men det ses mange andre steder. Charlie nævner Buffons nåleproblem.
Spørgsmålet er simpelt: Hvis man har et bræddegulv med 10 cm brede brædder og man kaster en 10 cm lang pind. Hvad er sandsynligheden for, at den lander, så den krydser fra et brædt til et andet? Svaret er 2/pi. Eller sagt på en anden måde: 2(antal kast)/(antal gange, man rammer stregen mellem to brædder) nærmer sig pi, jo flere gange, man kaster.
Martin Bøgsted Hansen har skrevet om en anden synsvinkel på det samme i denne pdf-fil, “Et party trick”. Der kan I også læse om praktiske anvendelser – jo, sådan nogen findes skam. Man kan jo vende problemet om: hvis man smider pinden 10 gange, og den så skærer stregerne 7 af gangene, hvor lang er den mon så? Hvad nu, hvis det ikke er en pind, men et langt DNA-molekyle, man kigger på i et mikroskop, og det er krøllet, men man har lagt det oveni et linieret net, kan man så finde ud af, hvor langt det er, ved at se, hvor mange gange det skærer linierne? Ved at “smide det linierede net” 17 gange tilfældigt og tælle skæringspunkter med DNA’et hver gang?
I øvrigt er det ikke specielt mystisk, at pi optræder her – der er jo klart noget med vinkler involveret – hvis pinden rammer parallelt med gulvbrædderne vil den jo ikke krydse mellem to.
Man kan læse mere om, hvordan man finder sandsynligheden 2/pi, her: http://www.mste.uiuc.edu/reese/buffon/buffon.html

Hilsner
Lisbeth www.math.aau.dk/~fajstrup
numb3rs@math.aau.dk
Husk, man kan ikke efterlade kommentarer direkte – I skal sende en mail.