Author Archives: Lisbeth Fajstrup

Rumudfyldende kurver – med anvendelser!

Det er gået op for mig, at rumopfyldende kurver – space filling curves i min oversættelse – har anvendelser. Til lagring af data. Her troede jeg, at det var noget, matematikerne kunne have for sig selv, men nej. Det skal da på bloggen.
Man skulle ikke tro, at det er muligt at lave en kurve, som går igennem hvert eneste punkt i et kvadrat i planen, men det er det. Og man kan såmænd også fylde hele planen eller hele rummet eller hele det 17-dimensionale rum Det gav i slutningen af 1800-tallet anledning til, at man måtte skærpe definitioner og ideer om bl.a. kontinuitet. Hvordan ser sådan en kurve mon ud? Tegner man kurven ind, får man malet hele planen, så der må en anden forklaring til og andre illustrationer.

Her er Hilbertkurven:

(Illustration, Byron Mayfield, Wikimedia Commons) Som man kan se, fremkommer kurven som en grænse – kurverne bliver tættere og tættere – rammer flere og flere punkter –  og man må vise, at der faktisk er en grænsekurve – at det giver mening, at denne grænsekurve er kontinuert og at den går igennem ethvert punkt i kvadratet. Der er mange eksempler på rumudfyldende kurver. De kaldes også Peanokurver, fordi Giuseppe Peano gav det første eksempel på en. Jeg holder mig til Hilbertkurven. Her er de første 6 kurver i den følge af kurver, som i grænsen er Hilbertkurven – drejet i forhold til illustrationen ovenfor.

(Billede fra Wikipedia) En beskrivelse af den iterative proces er som følger (leg med det her): 1) Del kvadratet op i fire og lav en kurve mellem centrene bestående af tre linjestykker som i første billede. 2) Opdel hvert af de fire kvadrater i fire, hvor kurven fra step 1 tegnes ind. Nu har vi fire mindre versioner af kurven fra step 1. Kald dem Sydvest, Nordvest,  Nordøst, Sydøst. Roter det syd-vestlige kvadrat 90 grader med uret. Roter det sydøstlige kvadrat 90 grader mod uret. Forbind nu de fra SØ til NØ og fra SV til NV. 3) gentag manøvren i mindre og mindre kvadrater. Se en mere præcis forklaring nedenfor, men lad mig lige sparke anvendelsen ind først: Har man data med to koordinater og vil søge i dem, er det (som jeg forstår det) nyttigt at omsætte til dimension 1, altså at ordne punkterne med 2 koordinater. Det kan man gøre på mange måder, men gør man det ved at følge en passende iteration på vejen til eksempelvis en Hilbertkurve (dem vil jeg også kalde Hilbertkurver nedenfor, selvom det egentlig kun er grænsekurven, der er en Hilbertkurve), så får man følgende sidegevinst:

Punkter, som ligger tæt på hinanden, når man måler langs kurven, ligger også tæt på hinanden i kvadratet. OBS: Ikke omvendt. Det skyldes den iterative konstruktion – man ændrer kurven lokalt, når man laver en iteration mere. Billedet nedenfor er en afbildning af regnbuens farver ordnet langs linjen ind i planen med en Hilbertkurve. Bemærk, at der er bratte overgange svarende til skift af kvadrater (mellem rød og gul for eksempel), men alt med sammen farve er tæt på noget med samme farve.

 

En anden beskrivelse af kurven i iteration nummer n, altså en kontinuert afbildning f_n:[0,1]\to [0,1]^2 fås ved at fortælle hvilken rækkefølge, kurven går igennem centrum for kvadraterne. De første fire centre nummereres 1,2,3,4 fra nederste venstre center og med uret – SV, NV, NØ, SØ med beskrivelsen ovenfor. Brug intervallet [ (k-1)4^{-n},k\,4^{-n}[ til at give kurven i kvadrat nummer k for kurven f_n.

Den n+1’ste nummerering laves ud fra den n’te som følger: Der er 4^{n+1} kvadrater grupperet med 4^n i hhv. SV, NV, NØ, SØ.

Start i SV. Brug ordenen fra step n – roter 90 grader med uret og brug den omvendte orden. I NV bruges ordenen fra step n, men man begynder med nummer 4^n +1. I NØ bruges igen ordenen fra step n, men begynd med nummer 2\cdot 4^n +1. I SØ nummereres med orden fra step n, der roteres 90 grader mod uret og nummerordenen vendes om – og man lægger 3\cdot 4^n til.

Observer, at både f_n og f_{n+1} afbilder [ (k-1)4^{-n},k\,4^{-n}[ til samme kvadrat – med sidelængde 2^n. Altså er |f_n(x)-f_{n+1}(x)|< 2^n for alle x. Det kan man bruge til at se, at f_n er en Cauchyfølge mht. supremumsafstanden – altså konvergerer følgen og grænsefunktionen er kontinuert. At grænsekurven går igennem alle punkter viser man ved, at der for hvert punkt p\in I^2 og hvert \varepsilon er et punkt på kurven i højst afstand \varepsilon. Brug nu, at I er kompakt, så f(I) er lukket til at konkludere, at p\in f(I).

Vi skal da have en XKCD ind her: Fra IP-adresser – altså noget data på en linje – til et kvadrat via en Hilbertkurve:

Map of the Internet

 

 

 

Grafisomorfialgoritmen er nu rettet.

For kort tid siden skrev jeg, at Helfgott havde fundet en fejl i Babais beregning af tidskompleksiteten for Babais grafisomorfialgoritme. Nu er der igen en kvasipolynomiel grafisomorfialgoritme. Lazslo Babai har rettet algoritmen. Jeg har skrevet om algoritmen. Jeg kan ikke sætte links pænt ind her fra min iPad, men nedenfor er links til det tidligere blogindlæg og nærmere omtale hos Quanta Magazine. Det er ret spændende at kunne følge processen – selvom Babai nok hellere ville have undværet det. Helfgott er nu enig med Babai: Den nye algoritme er kvasipolynomiel.
Tilføjelse 19/1: At et problem er kvasipolynomielt betyder, der findes en løsningsalgoritme, hvis tidskompleksitet T(n), som eren funktion, der giver antal skridt, algoritmen bruger, som funktion af størrelsen af input (antal knuder plus antal kanter i grafen eksempelvis) , er kvasipolynomiel.
En funktion T:\mathbb{N}\to \mathbb{R} er kvasipolynomiel, hvis den for ethvert b\in\mathbb{R}_+ opfylder: Der findes et n_0, så T(n)\leq b^{\log(n)^c} når n>n_0 , hvor c er en konstant.
Problemet er subeksponentielt, hvis der findes en algoritme, som løser problemet og hvis tidskompleksitet opfylder:
Der findes for ethvert b\in\mathbb{R}_+ et helt tal n_0, så T(n) \leq b^{n} når n>n_0
Da den nye (tilrettede) algoritme er kvasipolynomiel, er grafisomorfiproblemet nu kvasipolynomielt.

Helfgott finder fejl i Babais artikel om grafisomorfiproblemet

Graph Isomorphism Vanquished — Again

AAU-matematikere går til filmen.

Gymnasiematematikbøgerne “Hvad er Matematik” ledsages af diverse materiale. Herunder et filmprojekt “10 danske matematikere“.

Opgaven for de 10 er at fortælle om egen forskning og at fortælle om noget matematik, der giver mening for gymnasierne. Det er en vanskelig opgave. Men foreløbig er vi fire, der har vovet pelsen, heraf to fra AAU:

Olav Geil om Fejlkorrigerende Koder. 

 

Lisbeth Fajstrup (yours truly) om Algebraisk topologi – Om deformationer og huller i rummet.

De to andre er Susanne Ditlevsen fra KU om Statistiske metoder i hverdagsliv og neurovidenskab:

og Steen Markvorsen fra DTU om Skumstrukturer og minimalflader.:

 

 

Helfgott finder fejl i Babais artikel om grafisomorfiproblemet

I 2015 troede vi, der var nyt om kompleksiteten af grafisomorfiproblemet. Det skrev jeg om på bloggen (med undertitlen “rygters bureau” – man skulle tro, jeg havde en krystalkugle).

Nyheden var dengang, at Laszlo Babai havde lavet en ny algoritme til at afgøre, om to grafer er isomorfe og at tidskompleksiteten for den nye algoritme er  \exp((\log(n))^c), hvor c er en konstant.

Nu har Harald Helfgott, som er berømt (i visse kredse…) for at have bevist den svage Goldbachformodning, fundet en fejl i Babais artikel. Det viser sig, at kompleksiteten af algoritmen er \exp(\exp(O(\sqrt{\log n \log (\log n))})) og det er ikke quasipolynomielt, som Babai troede, men subeksponentielt (hurtigere end \exp (n^\varepsilon) for ethvert \varepsilon>0) .

Helfgott skriver på sin blog, at han fandt fejlen, da han forberedte sig til at holde Bourbakiforedrag om Babais resultat. I den forbindelse skal man skrive beviset  ud (eller op eller ned), så matematikere fra andre områder også kan læse det –  og der var altså noget, der ikke stemte. Algoritmen virker, men analysen af tidskompleksiteten er forkert. Helfgott skriver, man måske kan forbedre algoritmen. I hvert fald er det klart, hvor problemet er.

Babai skriver på sin hjemmeside  om det nye.

The technical content of the paper remains virtually unchanged. The previous analysis breaks down for one of the recursive steps of the combinatorial “Split-or-Johnson” procedure; but the “Split-or-Johnson” theorem remains valid with the updated timing analysis. All other results are unaffected. I am working on an updated arXiv posting (with a different title) that will also improve the presentation, following comments from several colleagues.

Og så er han en smule sarkastisk: I apologize to those who were drawn to my lectures on this subject solely because of the quasipolynomial claim, prematurely magnified on the internet in spite of my disclaimers. I believe those looking for an interesting combination of group theory, combinatorics, and algorithms need not feel disappointed.

“Prematurely magnified on the internet” – jow jow, bloggen her var ikke den eneste, der løb med en halv vind. Undskyld 🙂 Får man mon tilgivelse, når man har skrevet “rygters bureau”?

Julenørderier.

Sidste år havde vi links til matematiske julekalendere på bloggen. I år bliver det en blandet landhandel:

Sierpinski Juletræ Fra Math Craft

Sierpinski-trekanten er en fraktal, som man næsten kan gætte definitionen af udfra juletræet. Stjernen er et Von Koch snefnug.

Egenfunktioner for Laplaceoperatoren med et juletræ som rand.

Man kan tænke på det som en to-dimensional version af den svingende streng. Højere egenfunktioner svarer til overtoner.

Denne fine Møbiusjulekugle er 3d-printet. Men er man fiks på fingrene, kan man måske skære den ud af en trækugle 🙂

Møbiusbåndsjulepynt. Lavet af Teja Krasek. Jeg har lavet guirlander med Møbiusbånd i min studietid – et godt råd: Brug papir, der er farvet på begge sider…

Der er mange andre julerier derude på det store internet. Nogen hænger bogstavet pi på juletræet… Skåret ud i metal eller med et antal decimaler skrevet på en julekugle. Det gør jeg ikke.

Glædelig Jul og Godt Nytår.

Uafhængighed og noget om plat og krone

Tak til Jesper Møller for ideen til følgende, som egentlig er en opgave i et kursus om Bayesiansk statistik:

Hvornår er to begivenheder/hændelser uafhængige? Det kan man få en lang filosofisk diskussion ud af, men i matematik er der en definition.

To hændelser A og B er uafhængige, hvis sandsynligheden for, at både A og B indtræffer, er produktet af sandsynligheden for A og sandsynligheden for B.

P(A\cap B)=P(A)P(B)

 

Nu slår vi plat og krone med en ærlig mønt (altså en, der giver plat med sandsynlighed 1/2 og krone med sandsynlighed 1/2 – og aldrig lander på kanten…)

Vi slår et antal gange – kald det n. Det er altså et eksperiment: Slå n gange med en ærlig mønt. (Hvis du kun har Mobile Pay, kan du slå plat og krone hos Random.org Du kan endda vælge at gøre det med danske ti-kroner)

A er hændelsen: Der optræder både plat og krone undervejs.

B er hændelsen: Plat optræder højst en gang.

Er A og B uafhængige?

De mulige udfald kan beskrives som følger/ord  PPKPKKP med længde n. Der er altså 2^n mulige udfald af vores eksperiment.

n=1: Mulige udfald er { P, K }

n=2: Mulige udfald er { PP, PK, KP, KK}

n=3: Mulige udfald er { PPP, PPK, PKP, KPP, KKK, KKP, KPK, PKK}

n=4: {PPPP, PPPK, PPKP, PKPP, KPPP, PPKK, PKPK, KPPK, KPKP, KKPP, PKKP, KKKP, KKPK, KPKK, PKKK, KKKK}

og så orker jeg ikke lige mere, men her er fem 10-kroner, i PHPPP.

reverse obverse reverse reverse reverse

Hændelsen A sker netop, når vi ikke har slået plat i alle slag eller krone i alle slag. Så det sker i 2^n-2 tilfælde ud af de 2^n mulige. Sandsynligheden er så P(A)=(2^n-2)/2^n= 1-2^{1-n}

Hændelsen B (højst en plat) sker, når alle n slag er krone KKKK…KK eller når der er en enkelt plat: PKKK…KKK, KPKKKK…KKK, KKPKKK…KKK etc. Der er n muligheder for en enkelt plat og 1 for ingen, så der er n+1 ialt. Vi konkluderer P(B)=(n+1)/2^n=(n+1)2^{-n}.

A OG B indtræffer, hvis vi i mulighederne for B udelukker at have kun krone. Det er der sandsynlighed P(A\cap B)=n/2^n=n\cdot 2^{-n} for.

Svaret på, om (eller for hvilke n) A og B er uafhængige er: Når/hvis P(A\cap B)=P(A)P(B). Altså når n\cdot 2^{-n}=(1-2^{1-n})(n+1)2^{-n}

Reducer ligningen – gang med 2^n og få n=(1-2^{1-n})(n+1) udregne parenteser og reducer til 2^{n-1}=n+1. n=3 er en løsning og der er kun en løsning (venstresiden vokser eksponentielt og højresiden er en linje, så de skærer højst en gang).

De to hændelser er altså uafhængige, når man slår tre gange, men ikke hvis man slår flere gange eller færre!

 

Problemet med lykkelig slutning.

Happy Ending problemet er ikke løst, men to matematikere, Ester Klein og George Szekeres, der arbejdede med det, blev gift. Så derfor kaldte Erdös det “Happy Ending-problemet”.

Det er et af de matematiske spørgsmål, som er let at forstå, men svært at løse – tilsyneladende, eftersom det ikke er løst endnu. Og det er et af dem, der er omtalt i Popular Mechanics – ligesom Collatzformodningen, Sofaproblemet og Eulermursten, som allerede er behandlet her på bloggen.

Spørgsmålet er: Tegn punkter i planen. Der må ikke ligge tre eller flere på linje. Hvor mange skal der være for at man er sikker på at kunne tegne en konveks n-kant, hvis hjørnepunkter allesammen er nogen af dem, vi tegnede? (Konveks betyder, at randen buler udad, alle indre vinkler er højst 180 grader. Tegner man linjestykket mellem to punkter i figuren, så er det indeholdt i figuren.)

ConvexPolygon

Illustration fra MathWorld.

Hvis n=3 er det klart: Har man tre punkter, som ikke er på linje, er de hjørner i en trekant. Og trekanter er altid konvekse.

Kald antallet af punkter, der skal bruges, g(n). Vi ved nu g(3)=3.

HappyEndProblem4

Billedet fra Eric Weissteins MathWorld illustrerer, at g(4) må være større end 4. Der er vist to tilfælde, hvor man ikke kan tegne en konveks firkant. Erdös Szekeres-formodningen siger, at g(n)=2^{n-2}+1. E.Klein viste, at g(4)=5 ved at bevise, at alle konfigurationer af fem punkter er en af de tre (til venstre):

HappyEndProblem

Illustrationen (igen fra MathWorld) til højre viser, at g(5)>8. Faktisk er g(5)=9. Først vist af E. Makai.

At g(6)=17 krævede computerkraft – det resultat er fra 2006.

Hvad med g(7)? Det ved vi ikke! Erdös og Szekeres viste, at g(n) er endeligt. Det overrasker muligvis ikke læseren, men hvis man ændrer problemet en anelse og spørger: Hvad er det mindste antal punkter, man skal have for at man er sikker på, der findes en konveks n-kant som ovenfor, som ikke indeholder nogen af de andre punkter  (en tom konveks n-kant) så ved man, at uanset, hvor stort et N, man vælger, så kan der laves en punktmængde i planen med N punkter, som ikke indeholder nogen tom 7-kant. For en tom 6-kant gælder dette ikke, Der findes et tal, sådan at punktmængder  med det antal punkter altid vil indeholde en tom 6-kant. Man ved også, at det tal er mindst 30… Se mere på Numberphile-videoen her:

 

Collatz-formodningen.

I får endnu et af de matematiske spørgsmål, som er lette at forstå, men indtil videre ikke har kunnet besvares.

Collatz-formodningen.

David Eisenbud forklarer Collatzformodningen. Endnu en rigtig fin video – fra Numberphile.

Collatzformodningen siger, at uanset hvilket helt positivt tal, man starter med, så ender man på et tidspunkt med tallet 1, hvis man følger proceduren og bliver ved:

Hvis n er lige, så divider med 2:  n ->n/2.

Hvis n er ulige, så gang med 3 og læg 1 til: n-> 3n+1

Forfra med det nye tal.

Eksempler: Begynd med n=1. Så får man 1, 4, 2, 1. Altså tilbage igen i et lille loop.

Begynd med 9. Så får man 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Alle de 20 tal, vi passerede for at nå fra 9 til 1 er nu undersøgt – de følger samme tur. Lad os tage et nyt: n=12. Det giver 12, 6, 3, 10 og så rammer vi et, vi har kortlagt, nemlig 10 og følger som ovenfor 10, 5, 16, 8, 4, 2, 1.

Vejen til 1 for små tal

De første 100 tals vej ned til 1 (fra Wikipedia Creative Commons)

De første 100 tals vej ned til 1 (fra Wikipedia Creative Commons)

Naturligvis har Sloanes heltalsfølger, som Ege Rubak har skrevet om på bloggen, forskellige varianter af spørgsmål om “3n+1”-følger, som de også kalde. Begynder man med 27 får man A008884 Listen er på 111 skridt og når helt op til 9232 på vejen.

Hvis det tal, man starter med, er mindre end 10^18, så når man til sidst 1 ved proceduren. Der er lignende problemer, som man ved er uafgørbare. Paul Erdös har efter sigende sagt, at matematikken endnu ikke er klar til at løse Collatzproblemet og Terry Tao er enig. Det er et fint problem, fordi det er let at forklare, man kan selv finde på lignende problemer – hvorfor skal der eksempelvis ganges med 3? hvad sker der, hvis man ganger med noget andet? Hvad er den længste følge af tal, man skal igennem for at nå ned til 1? Hvor langt når man op undervejs? Nok at lege med… Man kan lave heuristiske argumenter: Når n er ulige, så er 3n+1 lige, så det skridt kan erstattes med at gå til (3n+1)/2. Der er altså en omskrivning:

Hvis n er lige divideres med 2. Hvis n er ulige går man til (3n+1)/2.

Den lille analyse bruger Tao og andre til at sandsynliggøre, at man vil ende ved 1. Men det er ikke et bevis. Dog gør det, at Tao tror på formodningen…

Hvis man udvider spørgsmålet og tillader an+b i stedet for 3n+1, og desuden giver flere muligheder, a la hvis 2 går op i x, så…, hvis 3 går op i x, så…, så er spørgsmålet “vil følgen ende i 1” uafgørbart i datalogisk forstand. Det kan I læse om her http://people.cs.uchicago.edu/~simon/RES/collatz.pdf

Men man skal passe på, som xkcd bemærker:

collatz_conjecture

 

 

Retfærdighed og kager.

To australske dataloger har fundet en begrænset algoritme, som deler kager og andet, man vil dele, misundelsesfrit. Det skriver Erika Klarreich om i Quanta Magazine.  Jeg har tidligere skrevet om den type problemer på Numb3rsbloggen, så jeg tillader mig at kopiere mig selv. Opdelinger med forskellige mål for, hvad en ideel deling er, optræder eksempelvis i økonomi – der optræder “nyttefunktioner”, som er mål for, hvor meget mere tilfreds, bestemte personer bliver, hvis de køber dette eller hint. Her deler vi kager, men I må gerne tænke på andre mere økonomiske ting – løn, ferie,…:

Kageudskæringsalgoritmer:

Det handler groft set om at dele noget – en kage eller noget andet – i et antal stykker, så alle bliver tilfredse. Et mere avanceret og kompliceret eksempel er opdeling af landområder efter en krig.

Et eksempel på en kageudskæringsalgoritme er “du deler og din søster vælger først” algoritmen, som forældre i hele verden nok kender. Ideen er, at hvis jeg deler, må jeg mene, begge stykker er lige gode. Og jeg er altså tilfreds, uanset hvilket stykke hun vælger. Omvendt er hun tilfreds, for hun får det stykke, hun selv mener ser bedst ud.

Man forestiller sig, en kage skal deles mellem personer, som har forskellige præferencer; Charlie viste en lagkage med vanille og chokolade og med glasur. Nogen sætter meget pris på glasur, andre mindre, nogen er vilde med vanille, andre med chokolade.

Vi forestiller os altså, at et stykke af kagen kan have forskellig værdi for forskellige personer. Og hele kagen kan være mere værd for en person end for en anden. Lad os sige, der er n personer, der skal dele kagen.

Man kan stille mange forskellige krav til en deling – hvad betyder det, at den er rimelig. Det kunne være

1) Proportionalt – hver person mener, at værdien af deres eget stykke er mindst 1/n af den samlede værdi. (OBS. Hvis nu jeg bedst kan lide vanilje og min søster chokolade og kagen består af halvt af hver, kan vi begge to få mere end halvdelen af det, vi mener er den samlede værdi. Ved at lade mig få den halvdel, der er vanilje og hun får den anden.)

2) Misundelsesfrit: Hver person mener, hun har fået det bedste af de stykker, kagen er delt i. (Ikke en skarp ulighed – det er nok, at der ikke er et andet, hun hellere vil have.)

3) Pareto optimalt:Vi har en opdeling, hvor enhver anden opdeling, hvor en deltager får mere, vil medføre, at en eller flere får mindre. Begrebet er en slags stabilitet overfor ændringer og optræder ofte i økonomi. Hvis jeg skal overbevise de andre om at lave det om, skal jeg overtale en deltager til at få mindre. (Det er det, der starter krige)

4) Ligeligt: Alles stykker har samme værdi. Så værdien af mit stykke for mig, er det samme som værdien af min søsters stykke for hende. Det kræver, at man kender alle deltagernes værdisætning af kagen.

Lad os begynde med to personer, som har et snit til at dele kagen. Vi vil ikke have en deling, hvor man tillader så mange stykker, at det ender med, at hver får en bunke krummer. Med “du deler, din søster vælger” algoritmen bliver delingen proportional og misundelsesfri men ikke nødvendigvis ligelig og pareto optimal.

Eksempel: Halvdelen af kagen er vanilje, halvdelen chokolade. Jeg er vild med chokolade, min søster med vanilje. jeg skærer og ved ikke, at min søster helst vil have vanilje. Så for en sikkerhedsskyld deler jeg, så begge stykker har halvt chokolade og halvt vanilje. Vi ville begge to have foretrukket delingen hvor jeg fik kun chokolade, og min søster kun vanilje – det er altså ikke pareto optimalt.

Lad os kigge nærmere på betingelserne ligelig og misundelsesfri. Pareto optimal er en lidt pudsig betingelse her, for hvis jeg får det hele, kan min søster ikke forbedre sin situation, uden jeg får mindre, end jeg havde; det er altså Pareto optimalt – og nok er jeg storesøster, men mon ikke FN eller forældre ville gribe ind.

Ligelig opdeling giver kun mening, hvis alle deltagere har samme samlede værdi af kagen, og man antager også, at alle sætter værdien af nok så små stykker højere end 0. Hellere chokolade end slet ingen kage. Lad os sige, den samlede værdi er 1.

En yderligere forsimpling er, at man kun må skære i en på forhånd valgt retning ( Tænk på en langstrakt skærekage, hvor man skærer på tværs – ikke noget med kagemænd, hvor man kan foretrække en af fødderne).

Vi kalder midtpunktet af kagen 1/2 og siger, man kan skære i punkter fra 0 til 1 (kagen er 1 lang). Fra 0 til 1/2 er der chokolade og fra 1/2 til 1 er der vanilje. (Vi antager, at stykker med areal 0, ikke har nogen værd, så det er ligemeget, hvad der er i 1/2.)

Hvis nu A er dobbelt så vild med chokolade som med vanilje, er hans værdisætning 4/3⋅x for et stykke af længde x med chokolade. Den er 2/3⋅ x for et stykke med vanilje. Vi antager, B har det omvendt.

Hvis A skal dele, vil hans strategi være, at det stykke, han ender med, har værdi mindst 1/2. (En minimax strategi – man satser ikke, men sørger for, at få mest muligt ud af det værste, der vil kunne ske.)

Så han deler i punktet p=3/8. Han har kun chokolade på stykket til venstre for p, så det har værdi

3/8 ⋅ 4/3 = 1/2

B vil vælge stykket til højre og få en værdi på 3/4, så det er ikke ligeligt, og A har snydt sig selv.

Havde A delt i midten, ville B stadig vælge stykket til højre, begge ville få værdi 2/3, og det ville være ligeligt og misundelsesfrit.

For n = 3 eller flere, kan man vise, at der findes situationer, hvor man ikke med n-1 snit kan lave en misundelsesfri og ligelig deling. Se f.eks. Better ways to cut a cake S. Brams, M.A. Jones og C. Klamler, Notices of the AMS, Vol 53 no. 11. Husk, hvis du går igang med den, at det handler om strategier og algoritmer: Hvordan ser det ud, hvis A ikke er ærlig om sin værdifunktion; er der en udenforstående involveret (FN eller andre) etc.

I How to cut a cake fairly, Walter Stromquist, American Mathematical Monthly, Vol 87, No.8, Oct. 1980, pp 640-644 (findes på Jstor for dem, der har adgang til det), bevises, at der eksisterer en misundelsesfri opdeling med n-1 snit for n deltagere. Men der er ikke en algoritme til at finde den. Det er et meget smukt argument (jo, det er det altså).
En opdeling i n+1 stykker betragtes som en stribe snit x1,x2,…,xn hvor 0 ≤ x1 ≤ x2 … ≤ xn ≤ 1. Det er de steder i intervallet mellem 0 og 1, hvor der skæres. Det tænker man så på som et punkt (x1,x2,…,xn) i et n-dimensionalt rum.
Las os begrænse os til at dele i tre stykker. Punkterne (x1,x2) vil ligge i en trekant i planen med hjørner (0,0), (0,1) og (1,1). Så hvert punkt svarer til en opdeling.
Hjørnepunkterne svarer til, at der to “stykker” uden noget, og et stykke, der er hele kagen. Kald de tre stykker, der kommer ud af opdelingen for nummer 1, 2 og 3 for stykket mellem 0 og x1, mellem x1 og x2 og mellem x2 og 1. Så er (0,0) der, hvor stykke 3 udgør hele kagen. (0,1) er, hvor stykke 2 er hele kagen og i (1,1) er det stykke 3, der er det hele.
På kanten mellem (0,0) og (0,1) er stykke nummer 1 “tomt”, og tilsvarende på de andre kanter.
I et punkt (x1,x2) vil spiller A måske foretrække stykke nummer 1, spiller B nummer 2 og spiller C måske også nummer 1. Der vil være en del af trekanten, hvori A vil foretrække 1, en anden del, hvor A foretrækker 2, og en tredie, hvor han foretrækker 3. (og nogen grænseområder, hvor han er ligeglad). Og tilsvarende for spillerne B og C. Nu skal man vise, at der findes et punkt, hvor spillerne foretrækker hver sit stykke. Og det kan man – med visse forudsætninger, men sådan er det jo i matematik. Ingrediensen i beviset er Brouwers fikspunktsætning, som har forbavsende mange anvendelser. Den siger:
En kontinuert afbildning fra en kugle til en kugle (tænk her på en klump modellervoks, som man kun må ælte og ikke flå) har et fikspunkt. (Et punkt er kommet tilbage, hvor det var)
Som illustration: Hvis man tager en blok papir, tager det øverste stykke af og krøller det sammen og lægger papirkuglen ovenpå blokken. Så vil der være et punkt, der ligger lige præcis lodret over der, hvor det var, før vi rev papiret af blokken.
Jeg vil ikke gengive, hvordan det bliver brugt i kageudskærings eksistensbeviset, men det står i artiklen.

Bemærk i øvrigt, problemet kan vendes om, så man skal dele noget, man ikke bryder sig om. Opvask og lignende. Det giver tilsvarende udskæringsalgoritmer “med modsat fortegn” i en vis forstand.

 

Hvad er det nye?

De to australiere har lavet en algoritme, som deler misundelsesfrit i endelig mange skridt. Er man kun 2, vil du deler, din søster vælger, være misundelsesfri. Men er man flere om det, bliver det mere vanskeligt, for den, der vælger sidst, kunne jo misunde en af dem, der valgte først. Den nye algoritme gør, for tilfældet med 3 personer, A,B, C følgende:

C deler i tre dele, X,Y,Z og A og B peger på det stykke, de helst vil have. Er det to forskellige stykker, er alt fint og C får det sidste.

Peger A og B på samme stykke, Z, sker følgende: B skærer så meget af dette stykke, at det, der er tilbage, Z’ er lige så meget værd – for hende! – som det, hun næsthelst ville have – lad os sige Y.

Læg det, der er skåret af til side. Lad A vælge. Hvis A ikke vælger Z’, er B tvunget til at tage det stykke. Vi har nu en misundelsesfri deling af kagen, bortset fra det, vi har lagt til side: A er tilfreds, da hun vælger først. B er tilfreds, da de to stykker, var lige meget værd. C er tilfreds, da de tre oprindelige stykker var lige meget værd. Vi har nu fordelt C fik X, B fik Y og A fik Z’ hvis ikke B blev tvunget til at tage Z’

Nu skal det afskårne deles (eller gives til hunden). Hvis A tog det tilrettede stykke, går det som følger:

B deler i tre dele. A vælger først, derefter C og til sidst B. Det er nu alt i alt misundelsesfrit. C har allerede fået X, der er lige så meget værd som Y og Z og derfor også lige så meget værd som Z’+det stykke A har fået i anden omgang. Derfor er C ikke misundelig på  A. Og C vælger før B og er heller ikke misundelig på hende. B delte og er derfor tilfreds. A valgte først og er derfor glad. (Jeg indser nu, at det nok kan skrives smukt ned med uligheder mellem de forskelliges præferencefunktioner, men det kan I selv filosofere over.)

For flere “spillere”, bliver det en meget lang proces, hvor der skal byttes om på, hvem der vælger, tages hensyn til, om en delmængde af spillerne alle foretrækker samme stykke…

 

 

 

 

 

Sofakonstanten og Euler-mursten.

Mange store uløste matematiske problemer er meget svære at forstå. De drejer sig om matematik, som i sig selv er svært tilgængelig. Fermats problem er let at forstå. Men løsningen kan de færreste læse og forstå.

i denne uge har Popular Mechanics fem eksempler på problemer, som kan forklares, selvom vi ikke kan løse dem. Endnu. Det har jeg ladet mig inspirere af. I får to af problemerne her. Så må de andre komme senere – Cliff hanger…:

Om Euler-mursten og et problem, der ligner Fermat:

En Euler-mursten er en kasse, som opfylder

  1. Længde, bredde og højde er hele tal. a,b,c.
  2. Diagonalerne på sidefladerne er hele tal.

M.a.o. er a,b,c hele tal og det er løsningerne d,e, f til a^2+ b^2= d^2, a^2+ c^2=e^2 og b^2+ c^2 = f^2 også.

Der er uendelig mange tripler a,b,c, som er sidelængder i en Euler-mursten. Det mindste tripel er (a,b,c)= (44,117,240). Diagonalerne har da længde 125,244,267.

Euler-mursten. Fra Wikipedia.

Euler-mursten. Fra Wikipedia.

 

 

 

 

 

Når først, man har en løsning, kan man skalere med et helt tal og få endnu en. Derfor har vi allerede nu uendelig mange. Se Wikipedia for mange andre facts om Euler-mursten. Euler fandt to uendelige familier – som ikke bare var lavet ved skalering.

Nå, men det er tydeligvis ikke et uløst problem at finde Eulermursten. Men perfekte/fuldkomne Eulermursten har vi ikke fundet nogen af.

En Eulermursten er perfekt, hvis den opfylder betingelserne ovenfor. Og dens hoveddiagonal også har heltallig længde. Altså

3) a^2+b^2+c^2=g^2 og g er et helt tal.

VI ved ikke, om der findes perfekte Eulermursten. Vi har hverken dundet nogen eller vist, de ikke findes. Naturligvis ved vi, at der ikke findes nogen med små sidelængder. Det kan man sætte en computer til. Hvis der findes perfekte Eulermursten, er en af sidelængderne mindst 10^12 (påstår Wikipedia).

OBS. Den skal BÅDE have heltallige sidediagonaler (d,e,f ovenfor) OG heltallig hoveddiagonal. I Popular Mechanics påstås, at vi ikke ved, om der finde heltallige løsninger til 3) I så fald skal jeg have skrevet en artikel om, at 1^2+2^2+2^2=3^2. Men det tror jeg nu alligevel ikke, jeg skal…

Sofakonstanten.

For en del år siden arbejdede projektgrupperne på 1.semester med “klaverflytning”. ( Som jeg husker det, var det Hans Huttels ide.) Hvor stort et klaver kan man få igennem en smal gang, der knækker? Det kom der fine projekter ud af – de fleste fokuserede på det plane problem, hvor man skubber klaveret rundt uden at måtte dreje det undervejs, de så på idealiserede klaverer – trekantede, kvadratiske, rektangulære,…

Leo Moser er efter sigende ophavsmand til Sofaflytningsproblemet: Hvad er det største areal, en plan figur kan have, hvis den skal kunne skubbes gennem en gang med bredde 1 og et 90 graders knæk. ( Det er underforstået, at gangen er lang på begge sider af knækket og at figuren er stiv.) Dette største areal kaldes sofakonstanten.

Jopseph L. Gervers sofa (fra 1991 – artiklen er her ) er bygget af 18 kurvestykker – antydet på figuren. Den har det største areal af alle de sofaer, vi kender, som kan skubbes gennem en gang som ovenfor.

Gervers Sofa.

Gervers Sofa.

 

 

 

 

Arealet af Gervers Sofa er ca. 2,2195. Det præcise tal og integralet, der regner det ud, kan man finde på MathWorld og i artiklen ovenfor. VI ved altså, at sofakonstanten er større end eller lig med arealet af Gervers sofa.

Gervers Sofa. Fra Dan Romik på UC Davis. Der er flere animationer og mere om sofaproblemet.

Mange matematiske geometriske problemer har “pæne” løsninger. Et område i planen, som kan hegnes ind af et hegn med længde L har størst areal, hvis det er en cirkel. Det tilsvarende problem i rummet giver en kugleflade. Så vi bliver lidt skuffede, når der er grimme løsninger. Og Gervers sofa er grim… 18 randkurver, hvor 3 er linjestykker og resten er løsninger til nogle differentialligninger, han opstiller. Det er ikke kønt. Før Gerver, havde vi Hammersleys sofaer:

Hammesleys Sofa. Fra Dan Romik.

Hammersleys Sofa. Fra Dan Romik.

Hammersleys sofaer har, som man kan se, en halvcirkel i midten, to kvarte cirkler som en del af sofaryggen og linjestykker for resten. HAn konstruerede dem ved at lave en halvcirkel med radius 1 og sætte et rektangel ind i midten – det skal der så klippes en mindre halvcirkel ud af, hvis det hele skal kunne skubbes om hjørnet. Hammersley viste, at den facon er optimal, hvis den midterste halvcirkel, som er klippet ud, har radius 2/\pi . Det er egentlig  en meget smukkere konstruktion end Gervers. Men arealet er 2/\pi+\pi/2 altså ca. 2,2074. Hammersley fandt også en øvre grænse for sofakonstanten på 2\sqrt{2} (ca. 2,82). Jeg har ikke læst argumentet for det, så det vil jeg ikke udbrede mig om, men interesserede kan som altid Google.

Uanset, om den er grim vil det give ny indsigt, hvis Gervers sofa faktisk er optimal. Differentialligningerne, der indgår i hans konstruktion bygger på antagelser om en form for stabilitet af den måde, man skubber sofaen igennem. Måske er der ny viden at hente i disse antagelser.

Senere får I noget om Collatz-formodningen og den lykkelige slutning. Og måske også noget om indskrevne kvadrater.