5-23 Angels and Demons. Blogindlæg nummer 200!!

OBS: Dette postes inden udsendelsen, da jeg er væk onsdag- torsdag.
Igen en rigtig ubehagelig forbryder – som heldigvis ikke havde forstand på computere. En glimrende replik fra Amita, da hun var fri igen: “My book will be called Three Days with a computer illiterate”. Nemlig – så kan de lære det 🙂
Matematikken var: Angels and demons – et problem i spilteori, som blev løst i 2006. Der var en hel masse matematik bag – f.eks., at man ikke bare kan hacke sig ind i “American Credit Union”, som forbryderen troede – det har vi set før: Sikkerheden bygger på matematikproblemer, som er vanskelige (tager meget lang tid) at løse, selv med en stærk computer. For eksempel faktorisering af et stort tal i sine primfaktorer.
Der var noget om rumlige puslespil – “Burr’s”. Og Larry nævnte Eulerture i en graf.
Engle og dæmoner
John H. Conway stillede i 1982 i bogen Winning ways for your mathematical plays (Conway, Berlekamp og Guy) et spørgsmål, som er nærmere beskrevet i denne artikel fra MSRI-publications.

Dette billede fra Wikipedia illustrerer problemet: En engel placeres på et uendeligt (!) skakbræt. Englen har en vis kraft, på figuren er det 3. En engel med kraft 3 må flytte til et felt i afstand højst 3, hvor afstanden mellem (a,b) og (x,y) er |x-a|+|y-b|, den såkaldte Manhattan afstand, eller taxi afstanden. Den hopper (nå ja, flyver vel), så den kan hoppe over de røde huller, men må ikke lande i dem. Modspilleren, djævlen, spiser felter. Et ad gangen.

Djævlen vinder, hvis den spærrer englen inde. Englen vinder, hvis den lever evigt.
Nu er spørgsmålet: Findes der en strategi for englen, så den altid vinder.
Der er enten en vindende strategi for englen, eller for djævlen, eftersom djævlen skal give en strategi, der spærrer englen inde i løbet af endelig mange træk. Hvis der IKKE er sådan en strategi, vil der altid være et muligt træk for englen. Og det er så englens vindende strategi.
For kraft 1 findes der en vindende strategi for djævlen. Altså en på forhånd fastlagt strategi, som altid vil fange englen. Det viste Berlekamp i 1982.
Conway spurgte, om en engel med stor nok kraft altid kan undslippe. Og svaret er ja. Selv for en engel med kraft 2. Det blev vist i 2006 i fire uafhængige beviser (de fire matematikere har ikke set hinandens beviser – så alle får æren).

Nordmanden Oddvar Kloster og ungareren András Máthé beviste, at en engel med kraft 2 har en vindende strategi – ved at give sådan en strategi og vise, at den virker. Strategierne skal sørge for, at englen ikke flyver ind i en “tunnel”, et hesteskoformet område, hvor djævlen har spist kanterne i en bredde på 2. Hvis englen flyver langt ind i sådan en tunnel, kan djævlen nå at æde udgangshullet, inden englen når tilbage igen.
Oddvar Kloster’s strategi er groft sagt, at englen hele tiden har en plan for fremtiden, kan huske sin fortid og i hvert skridt opdaterer sin fremtidsplan. Denne plan inkluderer en flyverute for englen og et “forbudt område” – vest for flyveruten – hvor englen ikke nogensinde vil komme, og hvor djævlen kan æde alt, hvad han vil. Den første plan er at flyve direkte nord på. Hvis djævlen begynder at æde områder øst for denne nordgående sti, og disse er tæt nok på, vil englen flyve øst om dem. Der er fine tegninger på Klosters hjemmeside af Klosters egen løsning.

The Angel moving

Her er englen fløjet øst om de tre mørke felter, som djævlen har spist. (Billede fra Klosters hjemmeside).

De to andre beviser er for engle med større kraft (Brian Bowditch for kraft 4 og Péter Gács for en meget stor kraft).

Hvis skakbrættet er 3d, er det lettere at give en vindende strategi for englen – det blev vist af B. Bollobás og I. Leader, og desuden i Martin Kutz’ PhD afhandling fra 2004. Men deres strategier kan ikke overføres til dimension 2. Det er en typisk udvikling af et matematikproblem: Man generaliserer (fra 2D til 3D) og løser det der – det giver ofte ideerne til at løse det oprindelige problem, Men omvendt er der også mange geometriske problemer, som er løsbare i visse dimensioner, men stadig uløste i f.eks. dimension 3 eller 4.

This entry was posted in Blog. Bookmark the permalink.