Alla inlägg av robert

2018, Vecktraklet

Kartor, grafer och kaffemuggar

2 oktober, 2018 robert Lämna en kommentar

De som har deltagit i gulisintagningen tidigare under hösten känner kanske till muggen ovan. Vid matematikpunkten på Wall Street Bar fick gulisarna till uppgift att med tusch koppla varje hus till varje enhet (el, vatten, gas) utan att förbindelserna korsar varandra. De fick med andra ord lösa det s.k. Three Utilities Problem. Om du vill fundera på problemet själv och undvika spoilers, gör det nu (Eller kolla på 3Blue1Browns video om temat, rekommenderas varmt).

Det väsentliga som gjorde uppgiften lösbar är att en mugg är (topologiskt sett) fundamentalt annorlunda än ett klot eller ett papper. Om man tänker sig att muggen är gjord av lera, kan man utan att bryta den eller slå nya hål forma om den till en donits. Med andra ord är kaffemuggen en torus, en sluten kropp med ett hål. Det visar sig att uppgiften är lösbar på en torus, men inte på ett klot eller ett papper!

Muggproblemet kan förvånansvärt nog ge oss insikt om ett helt annat problem: Om du har en karta där varje land är en sammanhängande region, hur många färger behöver du för att färglägga varje land utan att två grannländer får samma färg? Då kartan är ritad på ett papper eller en boll visar det sig att högst fyra färger behövs; resultatet är känt som Four color theorem.

Kartan över Frankrikes provinser behöver fyra färger

Men om kartan är ritad på en annan slags kropp, t.ex. en torus, räcker fyra färger till? För att förstå denna situation bättre söker vi ett ”renare” sätt att rita vår karta. Vi ersätter först varje region med en punkt. Sedan ritar vi streck mellan två punkter ifall de motsvarande regionerna gränsar till varandra. Det vi får är en graf: en samling noder (punkter) och kanter (streck) mellan dessa. I själva verket är det en planär graf, dvs. den kan ritas utan att två streck korsar varandra.

Det visar sig att varje karta motsvarar en planär graf och vice versa. Så istället för att granska kartor på en torus, kan vi kolla på planära grafer på en torus: Hur många färger behövs för att färglägga noderna så att två grannar inte får samma färg? Men här kommer insikten från muggproblemet in: Grafen som bildas i Three Utilities Problem är inte planär på ett papper (dvs två kanter måste korsa varandra) men den är planär på en torus. Det betyder att mängden av planära grafer på en torus är fundamentalt större!

Kan vi alltså hitta en graf som kräver mer än fyra färger? Grafen i muggproblemet kan färgas med endast två färger. Men t.ex. den kompletta grafen K₅ kräver 5 färger och kan ritas på en kaffemugg utan att två kanter korsar varandra.

K5 ritad på en kaffemugg utan att två kanter korsar

Och vad är det högsta antalet färger vi kan behöva?
https://mathsgear.co.uk/products/7-colour-torus-mug

Det mest spännande inom matematiken är då två koncept som verkar mycket annorlunda egentligen är nära sammankopplade. Många situationer där vi beaktar föremål (länder) och förbindelser mellan dem (gränser) kan uttryckas med hjälp av grafteori. Men en grafs egenskaper hänger inte bara på grafen själv, utan också på kroppen den ritas på. Kaffemuggen är ett intressant topologiskt föremål, inte bara en pryl för att hälla i sig kaffe.

2018, Vecktraklet

Det absolut simplaste beviset att √2 är irrationellt

24 april, 2018 robert Lämna en kommentar

Har du någonsin läst standardbeviset för att √2 är irrationellt och tänkt något av följande?
– ”Usch, delbarhet”,
– ”Fy, motantaganden”, eller
– ”Det här beviset var helt för kort!”
Worry not! Här delar jag med mig mitt favoritbevis, som är så självklart och trivialt att till och med humanister kunde uppskatta dess skönhet!

Vi påminner oss ännu om att ett rationellt tal kan skrivas i formen $\frac{a}{b}$ , där a och b är heltal och b ≠ 0. Ett irrationellt tal kan alltså inte skrivas på detta vis.

Påstående:

√2 är irrationellt.

Bevis:

Vi undersöker talföljder $(a_n)_{n \geq 0}$ med kraven
A) $a_n$ är rationellt för alla $n \geq 0$
B) $a_{n+1} = 2a_n^2 - 1$ för alla $n \geq 0$
C) $a_i = a_j$ för något $i \neq j$

Det visar sig att det finns ett ändligt antal talföljder som uppfyller dessa krav. Vi kan i själva verket lista upp dem alla.

Om $|a_0| > 1$ följer det från krav B att talföljden är strängt växande, dvs inget värde upprepas och krav C uppfylls inte. Vi kan alltså anta $|a_0| \leq 1$

Nu kan man substituera $a_0 = \cos{t}$ för något $t \in [0, \pi]$ . Detta kommer att ge oss en icke- rekursiv formel för talföljden.
Låt oss visa med induktion att $a_n = \cos(2^nt)$ för alla $n \geq 0$ .

Grundsteg:
$a_0 = \cos{t} = \cos{(2^0t)}$

Induktionssteg:
Med hjälp av formeln för dubbla vinklar, $\cos{(2x)} = 2\cos^2{x} - 1$ ,
får vi
$a_n = \cos{(2^nt)} \implies a_{n+1} = 2a_n^2 - 1 = 2\cos^2{(2^nt)} - 1 = \cos{(2^{n+1}t)}$

Påståendet $a_n = \cos(2^nt)$ gäller alltså för alla $n \geq 0$ .
Nu gäller det att hitta passliga värden på $t \in [0, \pi]$ så att $a_n = \cos{(2^nt)}$ är rationellt för alla $a_n \geq 0$ (krav A). I själva verket räcker det, att $\cos{t}$ är rationellt, eftersom (”selvästi nähdään”) då är också $\cos{(2t)}, \cos{(4t)}, \cos{(8t)} \dots$ rationella enligt formeln för dubbla vinklar.

För att krav C ska hålla, måste
$\cos{(2^it)} = \cos{(2^jt)}$ för något $i \neq j$

$\implies 2^it = \pm 2^jt + 2k\pi, k \in \mathbb{Z} \\ \implies t = \frac{2k}{2^i \pm 2^j}\pi$

där täljaren och nämnaren är heltal och nämaren är olika noll.
Talet t måste alltså vara en rationell multipel av pi!

Nu finns ett användbart resultat, Niven’s Theorem, som säger att de enda rationella multiplarna av pi inom $[0, \frac{\pi}{2}]$ vars cosinus också är rationellt är 0, $\frac{\pi}{3}$ och $\frac{\pi}{2}$ . Satsens bevis använder sig lyckligtvis inte av talets √2 irrationalitet.

Med Niven’s Theorem och några trigonometriska identiteter får vi att $t \in \{0, \frac{\pi}{3}, \frac{\pi}{2}, \frac{2\pi}{3}, \pi \}$ , varav följer $a_0 \in \{1, \frac{1}{2}, 0, -\frac{1}{2}, -1 \}$

Alla följder som uppfyller kraven A, B och C är alltså:
1, 1, 1, 1, 1, $\dots$
$\frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}, \dots$
0, -1, 1, 1, 1, $\dots$
$-\frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}, \dots$
-1, 1, 1, 1, 1, $\dots$

Men nu märker vi ju, att talföljden
$\frac{1}{\sqrt{2}}, 0, -1, 1, 1, \dots$
uppfyller kraven B och C, men hittas inte på vår lista. Då måste krav A gå fel, och eftersom 0, -1 och 1 tydligt är rationella tal, måste
$\frac{1}{\sqrt{2}}$ och därmed $\sqrt{2}$ vara irrationellt, Q.E.D.

Funderingar

Det här beviset är ett gott exempel på hur samma matematiska påstående ofta kan bevisas på många olika sätt. Standardbeviset påminner mest om talteori, ofta kallad heltalens matematik. Beviset ovan använder sig mer av algebra (reella tal och deras räkneregler) och analys (förändringens matematik, dvs. talföljder, derivator…).

Ifall du läser detta stycke och inte har läst beviset, så gör det inte nåt. Alla är inte intresserade av matematik och ska inte heller behöva vara det. Men på samma sätt som en poet gillar att skriva och läsa dikter kan en matematiker bli riktigt begeistrad av ett vackert bevis. Det är alltid bra att ha ett öppet sinne för andras intressen, även om man inte vet vad de talar om. Då kanske det är dags för mig att plocka ner diktboken från hyllan…

2018, Blogg

Allt större flugsmällor för allt mindre flugor

29 mars, 2018 robert 2 kommentarer

Varning: Detta inlägg innehåller extremt dålig Java-kod.
Läs på egen risk.

Den som nån gång har läst Reddit-sidan ProgrammerHumor har kanske lagt märke till tendenserna att hitta på alldeles absurda lösningar till mycket simpla problem eller koncept.
Till exempel, för cirka 9 månader sedan var volume sliders ett återkommande skämt och därav skapades många vackra implementationer, bl.a:

Veva upp ljudnivån
Pumpa upp ljudnivån
Låt användaren demonstrera:

Mer nyligen var temat om hur man ”effektivast” kollar om ett givet heltal är jämnt eller udda. Funktioner som åstadkommer detta är lättare att implementera än volume sliders, så motiverad av mina nyfunna kunskaper i Tira (Tietorakenteet ja algoritmit) bestämde jag mig naturligtvis för att testa några i Java. Metoderna nedan är inspirerade av både ProgrammerHumor och egna idéer. Några av dem kan kräva kunskap om Java eller talteori för att förstå, så en TL;DR i meme- format finns längst ner för dem som inte bryr sig om tekniska detaljer.

Metod 1: Divisionsrest

Kolla talets divisionsrest med 2. Om resten är 0, så är talet jämnt, annars udda.

Tråkig normie lösning
Använder inte ens rekursion

public boolean isEven1(int n) {
    return n % 2 == 0;
}

Metod 2: Sista siffran

Vi undersöker talets sista siffra. Om den är 1, 3, 5, 7 eller 9 är talet udda, annars jämnt. Javas indexOf()- metod för listor returnerar -1 ifall det sökta objektet inte hittas i listan. Då gör vi ju så klart en lista av de udda siffrorna och kollar om metoden ger -1 för talets sista siffra.

Behöver inte utföra nån äcklig aritmetik
Konstant tidskomplexitet, fortfarande helt för effektiv

public boolean isEven2(int n) {
    List<Character> lastDigits
        = Arrays.asList('1', '3', '5', '7', '9');
    String number = Integer.toString(n);
    char last = number.charAt(number.length() - 1);
    
    return lastDigits.indexOf(last) == -1;
}

Metod 3: Induktion

Vi använder oss av matematisk induktion. Allmänt gäller att 0 är ett jämnt tal, efter varje jämnt tal följer ett udda, och efter varje udda följer ett jämnt. Vi bygger alltså iterativt upp en array av booleans tills vi nått det n:te elementet, som vi returnerar. Dock för att undvika en OutOfMemoryError måste vi tyvärr fuska lite och emellanåt skriva över gamla värden.

O(n) tidskomplexitet. Från Tira vet vi ju att O(n) är bra.
Induktionen kräver antagandet att 0 är ett jämnt tal. Detta kan verifieras med en av de andra metoderna.

public boolean isEven3(int n) {
    n = n < 0 ? -n : n;        //gör n positivt
    int idx = 0;
    boolean isCurrentEven = true;
 
    boolean[] evenOdd = new boolean[10000];
    while (idx <= n) {
        if (idx == 10000) {
            idx -= 10000;
            n -= 10000;
        }
 
        evenOdd[idx] = isCurrentEven;
        isCurrentEven = !isCurrentEven;
        idx++;
    }
    return evenOdd[idx - 1];
}

Metod 4: Overflow

Alla vet ju att rekursion är bra, så här har vi en härlig blandning av rekursion och error handling.

Vi antar som baskunskap att Javas Integer.MAX_VALUE,
dvs. 2^31 – 1, är ett udda tal. Detta kan igen verifieras med någon annan metod.
Om n = 2^31 – 1 är n udda. Annars kallar vi rekursivt på funktionen med parametern n + 2. Så klart, om n är ett jämnt tal borde den eventuellt hoppa över 2^31 – 1 och orsaka en OverflowException. Men eftersom Java hanterar den här situationen utan att klaga, måste vi använda Math.addExact()- metoden som explicit ger en Exception ifall vi går över 2^31 – 1.

Rekursionen upprepas i värsta fall ca 2^30 gånger, så en StackOverflowError orsakas långt före det. Vid detta skede avbryter vi rekursionen och startar om med en hjälpvariabel som säger hur långt vi kommit förut.

O(2^31 – n) tidskomplexitet. Större tal får snabbare svar.
isEven4(1200000000) svarade true på endast 23 sekunder.

int offset;
 
public boolean increment(int n) {
    if (n == Integer.MAX_VALUE) {
        return false;
    }
    try {
        n = Math.addExact(n, 2);
        offset += 2;
        return increment(n);
    } catch (ArithmeticException e) {
        return true;
    }
}
 
public boolean isEven4(int n) {
    offset = 0;
    while (true) {
        try {
            return increment(n + offset);
        } catch (StackOverflowError e) {
            //inget fel här, moving on...
        }
    }
}

Metod 5: Goldbach

En välkänd hypotes inom talteorin är den s.k. Goldbach Conjecture, som säger att varje jämnt tal större än 2 kan uttryckas som summan av två primtal. Resultatet har inte bevisats för godtyckligt stora jämna tal, men det har verifierats med dator för tillräckligt stora tal för våra ändamål.
Det enda jämna primtalet är 2, dvs det största jämna talet som kan uttryckas som summan av två jämna primtal är 4. Alltså om vårt tal är större än eller lika med 6 söker vi udda primtal vars summa är vårt givna tal. Annars undersöker vi talet med Metod 4.

Hur kan vi då visa att ett givet tal är ett primtal? Vi använder så klart Wilson’s Theorem. Enligt denna sats är n ett primtal om och endast om talets (n-1)! divisionsrest med n är n-1, dvs.
$(n-1)!\ \equiv\ -1 \pmod n$
Till detta ändamål har vi hjälpfunktionerna modFactorial och isPrime.

Antagligen O(n^3) tidskomplexitet. Funktionen modFactorial är O(n) och isEven5 har en dubbel loop.
Körtiden varierar kraftigt mellan udda och jämna tal av ungefär samma storlek:
isEven5(4000) gav true på 2 sekunder och isEven5(4001) gav false på cirka 15 sekunder.
isEven5(10000) gav true efter 30 sekunder. Hur länge tog det för isEven5(10001)?
Använd alltså den här metoden om du redan anar att ditt tal är jämnt!

public int modFactorial(int p, int mod) {
    if (p < 1) {
        return -1;
    }
    long n = 1;
    for (int i = 1; i <= p; i++) {
        n = n*i % mod;
    }
    return (int) n;
}
 
public boolean isPrime(int n) {
    if (n < 2) {
        return false;
    } else {
        return modFactorial(n - 1, n) == n - 1;
    }
}
 
public boolean isEven5(int n) {
    n = n < 0 ? -n : n; //gör n positivt
    if (n < 6) {
        return isEven4(n);
    }
 
    for (int i = 3; i < n; i++) {
        if (!isPrime(i)) {
            continue;
        }
        for (int j = 3; j <= i; j++) {
            if (!isPrime(j)) {
                continue;
            }
            if (i + j == n) {
                return true;
            }
        }
    }
    return false;
}

Här tog kreativiteten och/eller tålamodet slut, för om vi vill kan vi göra godtyckligt ”effektiva” algoritmer, men de är inte nödvändigtvis så intressanta. Men nu har vi ju jobbat under premissen att vår metod ska ge ett svar för just det talet vi stoppar in, och att svaret ska vara rätt. Vad om vi ändrar på spelreglerna lite? En bonusmetod, isEven6, hittas under länken längst ner.

Det här inlägget kunde tolkas både som en uppmuntran och en varning. Avsiktligt dålig kod kan vara väldigt underhållande och lära en tänka på problem på nya sätt (om det här är en bra eller dålig sak är upp till läsarens tolkning). Å andra sidan är dessa metoder det oundvikliga resultatet av att spendera helt för mycket tid på Tira.

TL;DR

https://i.imgur.com/TUYX6Tq.jpg

Spektraklet